分治算法实验报告.docx

算法分析与设计实验报告第 1 次实验姓名学号班级时间10.17上午地点四合院102 实验名称分治算法实验（用分治法查找数组元素的最大值和最小值）。实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理 在满足分治法的条件下，根据不同的输入用例，能准确的输出用例中的最大值与最小值。并计算出程序运行所需要的时间。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。实验步骤① 先解决小规模的问题，如数组中只有1 个元素或者只有两个元素时候的情况。② 将问题分解，如果数组的元素大于等于3 个，将数组分为两个小的数组。③ 递归的解各子问题，将(中分解的两个小的数组再进行以上两个步骤((最后都化为小规模问题。④ 将各子问题的解进行比较最终得到原问题的解。关键代码void SelectMaxMin(int *a,int i,int j,int max,int min){if(i==j){max= a[i];min =a[i];return;} else { int mid=(i+j)/2; int maxi,maxj,mini,minj; SelectMaxMin(a,i,(i+j)/2,maxi,mini); SelectMaxMin(a,((i+j)/2)+1,j,maxj,minj); if(maximaxj) max=maxi; else max=maxj; if(miniminj) min=mini; else min=minj; return; }}srand((unsigned int)time(NULL));cout 随机产生的数据(0-100)：; for(int i=0; im; i++)a[i] = rand()%100;测试结果实验心得由于本次实验的算法思想之前数据结构课程就有了解，相对来说难度不是很大，通过本次实验，加深了对分治法算法的理解，同时再次巩固了之前所学的随机数的产生的使用。实验中，更加明确了如何分析具体的问题，以及具体写算法思想以及步骤。要想更好的掌握还得要理论与实践结合！我懂得，程序、工程都是由一个个细节堆码起来的，不能忽视任何一个小问题，要想熟练地写代码，还是要扎扎实实的练习！实验得分助教签名附录：完整代码SelectMaxMin.cpp:#include iostream#include ctime#include cstdio#include iomanip#include cstdlibusing namespace std;void SelectMaxMin(int *a,int i,int j,int max,int min){if(i==j){max= a[i];min =a[i];return;} else { int mid=(i+j)/2; int maxi,maxj,mini,minj; SelectMaxMin(a,i,(i+j)/2,maxi,mini); SelectMaxMin(a,((i+j)/2)+1,j,maxj,minj); if(maximaxj) max=maxi; else max=maxj; if(miniminj) min=mini; else min=minj; return; }}int main(){clock_t start,end,over;start=clock();end=clock();over=end-start;start=clock();//freopen(in.txt,r,stdin); //freopen(out.txt,w,stdout);int m;cout Please input the number : ; cin m;int a[m];srand((unsigned int)time(NULL));cout 随机产生的数据(0-100)：; for(int i=0; im; i++)a[i] = rand()%100;for(int i=0; im; i++)cout a[i] ;cout endl;int max,min;SelectMaxMin(a,0,m-1,max,min);cout max = max endl;cout min = min endl;end=clock();printf(The time is %6.3f,(double)(end-start-over)/CLK_TCK);}