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 老板有一袋金块(共n块,2≤n≤100),两名最优秀的雇员每人可以得到其中的一块,排名第一的得到最重的金块,排名第二的则得到袋子中最轻的金块。 输入一个正整数N(2≤N≤100ÿ…...
A062-防火墙安全配置-配置Iptables防火墙策略
实验步骤: 【教学资源类别】 序号 类别 打勾√ 1 学习资源 √ 2 单兵模式赛题资源 3 分组对抗赛题资源 【教学资源名称】 防火墙安全配置-配置安全设置iptables防火墙策略 【教学资源分类】 一级大类 二级大类 打勾√ 1.安全标准 法律法规 行业标准 安全…...
Java包装类
在Java中不能自己定义基本数据类型对象,为了将基本数据类型视为对象进行处理,并能连接相关方法,Java为每个基本数据类型都提供了【包装类】如int型数值的包装类【Integer】,boolean型数值的包装类【Boolean】,这样就可以把这些基本数据类型转…...
常用字符字符串处理函数
isdigit、isalnum、isalpha、islower、issupper都是C/C 语言中判断字符的一些函数,灵活利用在刷题中可以节省我们的一部分时间。下面c统一为char类型字符 1.isdigit 若参数c为十进制数字0~9,则返回非0值,否则返回0。 其中isxdigital判断是…...
【汇编语言特别篇】DOSBox及常用汇编工具的详细安装教程
文章目录 📋前言一. ⛳️dosbox的介绍、下载和安装1.1 🔔dosbos简介1.2 🔔dosbox的下载1.2.1 👻方式一:官网下载(推荐)1.2.2 👻方式二:网盘安装包 1.3 🔔dosbox的安装1.4 ǵ…...
【牛客网刷题(数据结构)】:环形链表的约瑟夫问题
描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少? O(n) 示例1 好环形链表的约瑟夫问题是一个经典的问…...
虾皮印尼买家号如何注册
虾皮(Shopee)是一个流行的电子商务平台,想要注册虾皮印尼买家号,可以按照以下步骤进行操作: 1、访问虾皮印尼站点:打开浏览器,输入虾皮印尼官网 2、点击"注册":在网站的…...
SpringBoot WebService服务端客户端使用教程
服务端: 依赖 <!-- webservice相关依赖--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web-services</artifactId></dependency><dependency><groupId&…...
【Python 千题 —— 基础篇】字符串长度
题目描述 题目描述 获取字符串长度是编程过程中常用的操作之一。编写一个程序,输入一个字符串,然后输出字符串的长度。 输入描述 输入一个字符串。 输出描述 程序将输入的字符串的长度输出。 代码讲解 下面是本题的代码: # 描述: 输…...
AIGC - 入门向量空间模型
文章目录 向量和向量空间向量的运算什么是向量空间?向量空间的几个重要概念向量之间的距离曼哈顿距离(Manhattan Distance)欧氏距离(Euclidean Distance)切比雪夫距离(Chebyshev Distance) 向量…...
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…...
计算机网络第一章补充整理(计算机网络体系结构)
前言:以下整理内容,参考《计算机网络自顶向下》和哈工大的计网慕课 目录 计算机网络的体系结构的一些概念为什么采用分层结构?分层结构的优点分层结构的缺点 开放系统互连(OSI)参考模型物理层功能数据链路层功能网络层…...
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封装请求拦截器和相应拦截器,借助refreshToken实现无感刷新 // 导入 http 模块 import http from wechat-http // 基础路径,同时需添加合法请求域名 http.baseURL https://live-api.itheima.net // 配置请…...
Unity C#随笔:简述String和StringBuilder的区别
1.、String: 不可变性(Immutability): String对象一旦被创建,就不能被修改。每次对String对象进行操作时,实际上是创建了一个新的String对象,然后对象的引用重新指向这个新的对象。性能&#x…...
图论相关算法
一、迪杰斯特拉(Dijkstra)算法 迪杰斯特拉算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。这是一个贪心算法。 1.核心思想 (1)每次选中一个点,这个点满足两个条件: 未被选过距离最短 (2…...
Python人工智能需要学什么
Python语言在人工智能开发领域有非常广泛的应用,随着人工智能平台的落地应用,未来采用Python语言来开发行业智能产品会是比较常见的选择。 然而进行人工智能开发仅凭Python语言是不够的,学习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 客户端指纹的方法,一般一个网站的证书是不变的,所以浏览器指纹也是稳定的,能区分不同的客户端。 requests库 Python requests库请求一个带JA3指纹网站的结果: import requestsheaders {authority: tls…...
web安全之XSS攻击
什么是XSS攻击 XSS(Cross-Site Scripting)又称跨站脚本,XSS的重点不在于跨站点,而是在于脚本的执行。XSS是一种经常出现在 Web 应用程序中的计算机安全漏洞,是由于 Web 应用程序对用户的输入过滤不足而产生的。 常见…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
