当前位置: 首页 > news >正文

6-2 分治法求解金块问题

description

老板有一袋金块(共n块,2≤n≤100),两名最优秀的雇员每人可以得到其中的一块,排名第一的得到最重的金块,排名第二的则得到袋子中最轻的金块。

输入一个正整数N(2≤N≤100)和N个整数,用分治法求出最重金块和最轻金块。

本题要求实现2个函数,分别使用分治法在数组中找出最大值、最小值。

函数接口定义:
int max(int a[ ], int m, int n);
int min(int a[ ], int m, int n);
递归函数max用分治法求出a[m]~a[n]中的最大值并返回。

递归函数min用分治法求出a[m]~a[n]中的最小值并返回。

裁判测试程序样例:
#include <stdio.h>
#define MAXN 101

int max(int a[ ], int m, int n);
int min(int a[ ], int m, int n);

int main(void)
{
int i, n;
int a[MAXN];

scanf ("%d", &n); 
if(n >= 2 && n <= MAXN-1 ){for(i = 0; i < n; i++){ scanf ("%d", &a[i]); }printf("max = %d\n", max(a, 0, n-1));printf("min = %d\n", min(a, 0, n-1));
}else{printf("Invalid Value.\n");    
}return 0;

}

/* 请在这里填写答案 */

输入样例:

6
3 9 4 9 2 4

输出样例:

max = 9
min = 2

solution

/* 请在这里填写答案 */
int max(int a[ ], int m, int n){if(m == n) return a[m];else{int mid = (m + n) / 2;int lMax = max(a, m, mid);int rMax = max(a, mid + 1, n);if(lMax > rMax) return lMax;else return rMax;}
}
int min(int a[ ], int m, int n){if(m == n) return a[m];else{int mid = (m + n) / 2;int lMin = min(a, m, mid);int rMin = min(a, mid + 1, n);if(lMin < rMin) return lMin;else return rMin;}
}

相关文章:

6-2 分治法求解金块问题

description 老板有一袋金块&#xff08;共n块&#xff0c;2≤n≤100&#xff09;&#xff0c;两名最优秀的雇员每人可以得到其中的一块&#xff0c;排名第一的得到最重的金块&#xff0c;排名第二的则得到袋子中最轻的金块。 输入一个正整数N&#xff08;2≤N≤100&#xff…...

A062-防火墙安全配置-配置Iptables防火墙策略

实验步骤: 【教学资源类别】 序号 类别 打勾√ 1 学习资源 √ 2 单兵模式赛题资源 3 分组对抗赛题资源 【教学资源名称】 防火墙安全配置-配置安全设置iptables防火墙策略 【教学资源分类】 一级大类 二级大类 打勾√ 1.安全标准 法律法规 行业标准 安全…...

Java包装类

在Java中不能自己定义基本数据类型对象&#xff0c;为了将基本数据类型视为对象进行处理&#xff0c;并能连接相关方法&#xff0c;Java为每个基本数据类型都提供了【包装类】如int型数值的包装类【Integer】,boolean型数值的包装类【Boolean】,这样就可以把这些基本数据类型转…...

常用字符字符串处理函数

isdigit、isalnum、isalpha、islower、issupper都是C/C 语言中判断字符的一些函数&#xff0c;灵活利用在刷题中可以节省我们的一部分时间。下面c统一为char类型字符 1.isdigit 若参数c为十进制数字0~9&#xff0c;则返回非0值&#xff0c;否则返回0。 其中isxdigital判断是…...

【汇编语言特别篇】DOSBox及常用汇编工具的详细安装教程

文章目录 &#x1f4cb;前言一. ⛳️dosbox的介绍、下载和安装1.1 &#x1f514;dosbos简介1.2 &#x1f514;dosbox的下载1.2.1 &#x1f47b;方式一&#xff1a;官网下载(推荐)1.2.2 &#x1f47b;方式二&#xff1a;网盘安装包 1.3 &#x1f514;dosbox的安装1.4 &#x1f5…...

【牛客网刷题(数据结构)】:环形链表的约瑟夫问题

描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数&#xff0c;报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后&#xff0c;只剩下一个人&#xff0c;问最后留下的这个人编号是多少&#xff1f; O(n) 示例1 好环形链表的约瑟夫问题是一个经典的问…...

虾皮印尼买家号如何注册

虾皮&#xff08;Shopee&#xff09;是一个流行的电子商务平台&#xff0c;想要注册虾皮印尼买家号&#xff0c;可以按照以下步骤进行操作&#xff1a; 1、访问虾皮印尼站点&#xff1a;打开浏览器&#xff0c;输入虾皮印尼官网 2、点击"注册"&#xff1a;在网站的…...

SpringBoot WebService服务端客户端使用教程

服务端&#xff1a; 依赖 <!-- webservice相关依赖--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web-services</artifactId></dependency><dependency><groupId&…...

【Python 千题 —— 基础篇】字符串长度

题目描述 题目描述 获取字符串长度是编程过程中常用的操作之一。编写一个程序&#xff0c;输入一个字符串&#xff0c;然后输出字符串的长度。 输入描述 输入一个字符串。 输出描述 程序将输入的字符串的长度输出。 代码讲解 下面是本题的代码&#xff1a; # 描述: 输…...

AIGC - 入门向量空间模型

文章目录 向量和向量空间向量的运算什么是向量空间&#xff1f;向量空间的几个重要概念向量之间的距离曼哈顿距离&#xff08;Manhattan Distance&#xff09;欧氏距离&#xff08;Euclidean Distance&#xff09;切比雪夫距离&#xff08;Chebyshev Distance&#xff09; 向量…...

python中使用xml.dom.minidom模块读取解析xml文件

python中可以使用xml.dom.minidom模块读取解析xml文件 xml.dom.minidom模块应该是内置模块不用下载安装 对于一个xml文件来说比如这个xml文件的内容为如下 <excel version"1.0" author"huangzhihui"><table id"1"><colum id&qu…...

计算机网络第一章补充整理(计算机网络体系结构)

前言&#xff1a;以下整理内容&#xff0c;参考《计算机网络自顶向下》和哈工大的计网慕课 目录 计算机网络的体系结构的一些概念为什么采用分层结构&#xff1f;分层结构的优点分层结构的缺点 开放系统互连&#xff08;OSI&#xff09;参考模型物理层功能数据链路层功能网络层…...

2023_Spark_实验十七:导入招聘大数据(项目)

一、爬虫爬取的招聘网站数据 二、在MySQL中创建空表 SET FOREIGN_KEY_CHECKS0;-- ---------------------------- -- Table structure for jd_jobs -- ---------------------------- DROP TABLE IF EXISTS jd_jobs; CREATE TABLE jd_jobs (job_name text,job_date text,minSale…...

小程序无感刷新

下载wechat-http依赖 npm install wechat-http封装请求拦截器和相应拦截器&#xff0c;借助refreshToken实现无感刷新 // 导入 http 模块 import http from wechat-http // 基础路径&#xff0c;同时需添加合法请求域名 http.baseURL https://live-api.itheima.net // 配置请…...

Unity C#随笔:简述String和StringBuilder的区别

1.、String&#xff1a; 不可变性&#xff08;Immutability&#xff09;&#xff1a; String对象一旦被创建&#xff0c;就不能被修改。每次对String对象进行操作时&#xff0c;实际上是创建了一个新的String对象&#xff0c;然后对象的引用重新指向这个新的对象。性能&#x…...

图论相关算法

一、迪杰斯特拉(Dijkstra)算法 迪杰斯特拉算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。这是一个贪心算法。 1.核心思想 &#xff08;1&#xff09;每次选中一个点&#xff0c;这个点满足两个条件&#xff1a; 未被选过距离最短 &#xff08;2&#xf…...

Python人工智能需要学什么

Python语言在人工智能开发领域有非常广泛的应用&#xff0c;随着人工智能平台的落地应用&#xff0c;未来采用Python语言来开发行业智能产品会是比较常见的选择。 然而进行人工智能开发仅凭Python语言是不够的&#xff0c;学习Python人工智能需要学习哪些知识呢? 一、Python…...

Java 获取请求真实IP

获取IP地址为 127.0.0.1, 或者内网地址 Nginx配置, 只有 proxy_pass 时只能获取到 127.0.0.1 location / {proxy_pass http://127.0.0.1:8080; }修改为 location / {#保留代理之前的host 包含客户端真实的域名和端口号proxy_set_header Host $host; #保留代理之前的真实客…...

Python突破浏览器TLS/JA3 指纹

JA3 是一种创建 SSL/TLS 客户端指纹的方法&#xff0c;一般一个网站的证书是不变的&#xff0c;所以浏览器指纹也是稳定的&#xff0c;能区分不同的客户端。 requests库 Python requests库请求一个带JA3指纹网站的结果&#xff1a; import requestsheaders {authority: tls…...

web安全之XSS攻击

什么是XSS攻击 XSS&#xff08;Cross-Site Scripting&#xff09;又称跨站脚本&#xff0c;XSS的重点不在于跨站点&#xff0c;而是在于脚本的执行。XSS是一种经常出现在 Web 应用程序中的计算机安全漏洞&#xff0c;是由于 Web 应用程序对用户的输入过滤不足而产生的。 常见…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...