《分治算法实验(用分治法查找数组元素的最大值和最小值)》由会员分享，可在线阅读，更多相关《分治算法实验(用分治法查找数组元素的最大值和最小值)（10页珍藏版）》请在金锄头文库上搜索。
1、分治算法实验（用分治法査找数 组元素的最大值和最小值）算法分析与设计实验报告第一次实验姓名时间10.17 上午学 号 地 点工训楼309班 级实验名称目的分治算法实验（用分治法査找数组元素的 最大值和最小值）通过上机实验，要求掌握分治算法的问题 描述、算法设计思想、程序设计。使用分治的算法，根据不同的输入用例， 能准确的输出用例中的最大值与最小值。 并计算出程序运行所需要的时间。实验原理,=J程序思路：利用分治法，将一个数组元素 大于2的数组分成两个子数组，然后对每 一个子数组递归调用，直到最小的子数组 的元素个数为1个或者是2个，此时直接 就能得出最大值与最小值,然后合并子数 组，比较2个子
2、数组的最大值与最小值， 依次进行下去，知道找到整个数组的最大 值与最小值。先解决小规模的问题，如数组中只有 1个元素或者只有两个元素时候的 情况。实验步骤将问题分解，如果数组的元素大于等于 3个，将数组分为两个小的数 组。递归的解各子问题，将中分解的两个小 的数组再进行以上两个步骤最后都化 为小规模问题。4.将各子问题的解进行比较最终得到原问题的解。分治法处理整个数组，求出最大值与最小值void merge(int a, int left, int right, int &Max, int &Min) int max1=0,min1=0,max2=0,min2=0;if (rightTef t
3、2)当数组中元素个数大于3时，才实行分治法int mid=(right+left)/2; merge(a,lef t,m id,max1,min1);关键左半边递归调用自身，求出最大值与最小值，分别保存在m ax1,min 1中merge(a,mid+1,righ t,max2,min2);代码右半边递归调用自身，求出最大值与最小值，分别保存在m ax2,min2中if (max1=max2)Max=max1;子序列两两合并，求出最大值与最小值elseMax=max2;分别保存在Max与Minif (min1=min2)Min=min1;elseMin=min2;当数组中元素个数少于2时，直接
4、赋值处理elseMax=compmax(a,lef t,righ t);Min=compmin(a,lef t,righ t); 利用分治法（递归实现）:非递归实现:测试结果s f：算vol E 91 BiSfiMl EnnjijAIH *0-07B0-0240-0050.0酹请按任青输入数据规模;100000032767 3The time is 100000 3276? 0The time is100003276? 0The time is1000 32767 0The time is100 32767 0 The time is通过这次实验，加深了我对分治法的理解，明白了分治法到底是怎样
5、的一个过实验程,在代码实现分治法的时候，也使我加心得深了对于自己构造函数的理解，明白了分治法利用代码是怎样实现的，以及构造函数的传参与返回值等等地方需要注意的东西，是我认识到我的编程能力的不足, 更加加深了我要好好学习，多做练习的想 法，总体收获很大。实验比较观察上面两个不同的实现方法所花费的 时间，我们可以看到，采用非递归的方法 实现,所花费的时间比利用分治法花费的 时间多，为什么会出现这样的结果，我们 可以知道在分治法需要比较的次数比非 递归方法多，甚至是多得多，所以它所花 费的时间也多，所以对于这种求最大值最 小值的问题,利用非递归的方法相对会好 一点。得分助教签 名附录: 完整代码（分
6、治法）#include #include #include using namespace std;当数组中的元素个数小于3时，处理最大值int compmax(int A, int start,int end)int max;辻(start end)有两个元素if (As tart =Aend)max=Aend;elsemax=Astart;else有一个元素max=Astart;return max;当数组中元素的个数小于2时，处理最小值int compmin(int A, int start, int end)int min;if (startend)有两个元素if (Astar t2)
7、/当数组中元素个数大于等于3时，进行分治int mid=(right+left)/2;merge(a,left,mid,maxl,minl);左半边递归调用自身，求出最大值最小值，分别保存在maxl,minl中merge(a,mid+1,righ t,max2,min2); /右半边递归调用自身，求出最 大值最小值，分别保存在max2,min2中if(max1=max2)/子序列两两合并，求出最大值与最小值，保存在Max与Min中Max=max1;elseMax=max2;if (min1=min2)Min=min1;elseMin=min2;else数组中元素个数小于3时的情况，直接赋值Ma
8、x=compmax(a,left,righ t);Min=compmin(a,lef t,righ t);void ran(int *input, int n)随机生成数组元素函数int i;srand(time(O);for(i=0;in;i+)inputi=rand();inputi =0;int a1000000;定义全局变量用来存放要查找的数组int main()int n;int i;int max;int min;cout请输入要查找的序列个数：endl;for(i=0;in;ran(a,n);clock_t start ,end,over;计算程序运行时间的算法start=clo
9、ck();end=clock();over=end-start;start=clock();merge(a,0,n-1,max,min);调用分治法算法coutmax minendl; end=clock();printf(The time is %6 3f,(double)(end-start-over)/CLK_TCK);显示运行时间sys tem(pause);停止运行窗口return 0;完整代码（非递归方法）#include #include #include using namespace std;随机生成数组元素函数void ran(int *input, int n) int
10、i; srand(time(0); for(i=0;in;i+) inputi=rand();inputi =0; int a1000000;int main()int max=a0,min=a0;int i,j,n;cout请输入数据规模：endl; for(j=0;jn;ran(a,n);clock_t start, end,over;计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();for(i=1;imax) max=ai;if(aimin) min=ai;coutmax minendl; end=clock();printf(The time is %6.3f,(double)(end-start-over)/CLK_TCK); / 显示运行时间system(pause);return 0;
