分治算法实验(用分治法查找数组元素的最大值和最小值).doc

算法分析与设计实验报告第 一 次实验姓名学号班级时间10.17上午地点工训楼309 实验名称分治算法实验（用分治法查找数组元素的最大值和最小值）实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理使用分治的算法，根据不同的输入用例，能准确的输出用例中的最大值与最小值。并计算出程序运行所需要的时间。程序思路：利用分治法，将一个数组元素大于2的数组分成两个子数组，然后对每一个子数组递归调用，直到最小的子数组的元素个数为1个或者是2个，此时直接就能得出最大值与最小值，然后合并子数组，比较2个子数组的最大值与最小值，依次进行下去，知道找到整个数组的最大值与最小值。实验步骤1. 先解决小规模的问题， 如数组中只有 1 个元素或者只有两个元素时候 的情况。2. 将问题分解，如果数组的元素大于等于 3 个，将数组分为两个小的数 组。3. 递归的解各子问题，将中分解的两个小的数组再进行以上两个步骤最后都化为小规模问题。4. 将各子问题的解进行比较最终得到原问题的解。关键代码/分治法处理整个数组，求出最大值与最小值void merge(int a,int left,int right,int &Max,int &Min)int max1=0,min1=0,max2=0,min2=0;if(right-left2) /当数组中元素个数大于3时，才实行分治法int mid=(right+left)/2;merge(a,left,mid,max1,min1); /左半边递归调用自身，求出最大值与最小值，分别保存在max1,min1中merge(a,mid+1,right,max2,min2);/右半边递归调用自身，求出最大值与最小值，分别保存在max2,min2中if(max1=max2)Max=max1; /子序列两两合并，求出最大值与最小值elseMax=max2; /分别保存在Max与Minif(min1=min2)Min=min1;elseMin=min2;else /当数组中元素个数少于2时，直接赋值处理Max=compmax(a,left,right);Min=compmin(a,left,right);测试结果利用分治法（递归实现）： 非递归实现： 实验心得通过这次实验，加深了我对分治法的理解，明白了分治法到底是怎样的一个过程，在代码实现分治法的时候，也使我加深了对于自己构造函数的理解，明白了分治法利用代码是怎样实现的，以及构造函数的传参与返回值等等地方需要注意的东西，是我认识到我的编程能力的不足，更加加深了我要好好学习，多做练习的想法，总体收获很大。实验比较观察上面两个不同的实现方法所花费的时间，我们可以看到，采用非递归的方法实现，所花费的时间比利用分治法花费的时间多，为什么会出现这样的结果，我们可以知道在分治法需要比较的次数比非递归方法多，甚至是多得多，所以它所花费的时间也多，所以对于这种求最大值最小值的问题，利用非递归的方法相对会好一点。实验得分助教签名附录：完整代码（分治法）#include#include#includeusing namespace std;/当数组中的元素个数小于3时，处理最大值int compmax(int A,int start,int end)int max;if(startend) /有两个元素if(Astart=Aend)max=Aend;else max=Astart;else /有一个元素max=Astart;return max;/当数组中元素的个数小于2时，处理最小值int compmin(int A,int start,int end)int min;if(startend) /有两个元素if(Astart2) /当数组中元素个数大于等于3时，进行分治int mid=(right+left)/2;merge(a,left,mid,max1,min1); /左半边递归调用自身，求出最大值最小值，分别保存在max1,min1中merge(a,mid+1,right,max2,min2); /右半边递归调用自身，求出最大值最小值，分别保存在max2,min2中if(max1=max2) /子序列两两合并，求出最大值与最小值，保存在Max与Min中Max=max1;elseMax=max2;if(min1=min2)Min=min1;elseMin=min2;else /数组中元素个数小于3时的情况，直接赋值Max=compmax(a,left,right);Min=compmin(a,left,right);void ran(int *input,int n) /随机生成数组元素函数int i;srand(time(0);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=clock();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); /显示运行时间system(pause); /停止运行窗口 return 0;完整代码（非递归方法）#include#include#includeusing namespace std;void ran(int *input,int n) /随机生成数组元素函数int 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;ima