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 应用程序对用户的输入过滤不足而产生的。 常见…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
Vue3中的computer和watch
computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...
路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...
