分治算法实验报告

1、算法分析与设计实验报告第1次实验姓名学号班级时间10.17上午地点四合院102实验名称分治算法实验（用分治法查找数组元素的最大值和最小值）。实验目的通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。实验原理在满足分治法的条件下， 根据不同的输入用例， 能准确的输出用例中的最 大值与最小值。并计算出程序运行所需要的时间。分治法的基本思想是将一个规模为 n的问题分解为k个规模较小的子问 题，这些子问题互相独立且与原问题相同。 递归地解这些子问题， 然后将各子 问题的解合并得到原问题的解。实验步骤 先解决小规模的冋题，如数组中只有1个兀素或者只有两个兀素时候的情况。 将问题分解，如果

2、数组的元素大于等于3个，将数组分为两个小的数组。 递归的解各子问题，将（中分解的两个小的数组再进行以上两个步骤 （最后都化为小规模问题。 将各子问题的解进行比较最终得到原问题的解。关键代码void SelectMaxMin(int *a,int i,int j,int &max,int &min) if(i=j)max= ai;min =ai; return;elseint mid=(i+j)/2;int maxi,maxj,mini,minj;SelectMaxMi n( a,i,(i+j)/2,maxi,mi ni);SelectMaxMi n(a,(i+j)/2)+1,j,maxj,mi

3、nj);测试结果if(maximaxj) max=maxi; else max=maxj;if(mi nivminj) min=mini;elsemi n=minj;return;sran d( un sig ned in t)time(NULL);cout 随机产生的数据(0-100): for(i nt i=0; i： S2 5? 41 74 38 25 49 21maDc = 82Access exited with 1-etun ualue 0 pess ani key to contlnme _ _ .实验心得由于本次实验的算法思想之前数据结构课程就有了解，相对来 说难度不是很大，通

4、过本次实验，加深了对分治法算法的理解，同 时再次巩固了之前所学的随机数的产生的使用。实验中，更加明确 了如何分析具体的问题，以及具体写算法思想以及步骤。要想更好 的掌握还得要理论与实践结合！我懂得，程序、工程都是由一个个 细节堆码起来的，不能忽视任何一个小问题，要想熟练地写代码， 还是要扎扎实实的练习！实验得分助教签名附录：完整代码SelectMaxMi n.cpp:#in elude #in elude #in elude #i nclude #in clude using n amespace std;void SelectMaxMin(int *a,int i,int j,int &ma

5、x,int &min) if(i=j)max= ai;min =ai;return;elseint mid=(i+j)/2;int maxi,maxj,mini,minj;SelectMaxMi n( a,i,(i+j)/2,maxi,mi ni);SelectMaxMi n(a,(i+j)/2)+1,j,maxj,minj);if(maximaxj)max=maxi;elsemax=maxj;if(mi nivminj) 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 m;int am;srand(unsigned int)time(NULL);cout 随机产生的数据 (0-100) ： ; for(int i=0; im; i+) ai = rand()%100;for(int i=0; im; i+)cout ai ;cout endl;int max,min;SelectMaxMin(a,0,m-1,max,min);cout max = max en