loading算法分析与设计实验报告
第 1次实验
姓名 时间 实验名称 秦宇峰 10.17上午 学号 地点 201308010104 四合院102 班级 计科1301 分治算法实验（用分治法查找数组元素的最大值和最小值） 实验目的 通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。 实验原理 在满足分治法的条件下，根据不同的输入用例，能准确的输出用例中的最大值与最小值。并计算出程序运行所需要的时间。 ① 先解决小规模的问题，如数组中只有1 个元素或者只有两个元素时候的情况。 ②将问题分解，如果数组的元素大于等于3 个，将数组分为两个小的数组。 ③递归的解各子问题，将(中分解的两个小的数组再进行以上两个步骤 ((最后都化为小规模问题。 ④将各子问题的解进行比较最终得到原问题的解。 void max_min(int *array,intl,intr,int&nmax,int&nmin) { if(l==r)//数组只有一个元素时 { nmax = array[l]; nmin = array[l]; return; } if(l+1 == r)//数组有两个元素时，比较大小并赋值 { if(array[l]>=array[r]) { nmax = array[l]; nmin = array[r]; return ; } else if(array[l] 附录：完整代码 #include #include voidmax_min(int *array,intl,intr,int&nmax,int&nmin) { if(l==r)//数组只有一个元素时 { nmax = array[l]; nmin = array[l]; return; } if(l+1 == r)//数组有两个元素时，比较大小并赋值 { if(array[l]>=array[r]) { nmax = array[l]; nmin = array[r]; return ; } else if(array[l] nmax = array[r]; nmin = array[l]; return ; } } int m = (l+r)/2; intrmax,rmin; max_min(array,l,m,rmax,rmin);//递归求左边的最小值 intlmax,lmin; max_min(array,m,r,lmax,lmin);//递归求右边的最大值 nmax = max(lmax,rmax); nmin = min(lmin,rmin); } int main () { inti,j=0; double k=0.0; clock_tstart,end,over; start=clock(); end=clock(); over=end-start; start=clock(); //my test ofstreamfout(\int r; for(int bb=0;bb<=100000;bb++) { r = rand(); //cout<< r< } fout.close(); int a[100000]; ifstream fin(\intdd,Datalen=-1; while( ! fin.eof() ) { //cout< fin>>a[Datalen]; } fin.close(); intmnum,nnum; max_min(a,0,Datalen,mnum,nnum); cout< printf(\system(\return 0; }