分治法求集合最大元
2018-06-17 23:43:43来源:未知 阅读 ()
题目:输入n 然后输入n个整数,用分治法求这n个数中的最大元;
思路:把这列数分成两半,递归下去,到只剩一个数时停止,返回这个数,如果不是一个数则返回分成的两段数最大值的较大者;
实验提示:在规模为n的数据元素集合中找出最大元。当n=2时,一次比较就可以找出两个数据元素的最大元和最小元。当n>2时,可以把n个数据元素分为大致相等的两半,一半有n/2个数据元素,而另一半有n/2个数据元素。 先分别找出各自组中的最大元,然后将两个最大元进行比较,就可得n个元素的最大元
代码如下:
#include <iostream> #include <algorithm> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <set> #include <queue> #include <vector> using namespace std; int calc(int a[],int l,int r) { if(l==r) return a[l]; return max(calc(a,l,(l+r)/2),calc(a,(l+r)/2+1,r)); } int main() { int a[1005]; int n; cout<<"数列长度: "<<endl; scanf("%d",&n); if(n==0) {puts("数列长度不能为0!"); return 0;} cout<<"请输入数列: "<<endl; for(int i=0;i<n;i++) scanf("%d",&a[i]); printf("这个数列的最大元为: %d\n",calc(a,0,n-1)); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:线性筛法(欧拉筛法)求素数
- STL之set 2020-04-28
- 动态规划:最大子串和 2020-01-30
- 最小割最大流定理&残量网络的性质 2019-12-17
- 剑指offer64:滑动窗口的最大值 2019-08-31
- Qt无边框窗体-最大化时支持拖拽还原 2019-08-27
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash