当前位置: 首页 > 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 应用程序对用户的输入过滤不足而产生的。 常见…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...