分治算法实验报告

算法分析与设计实验报告

第 1 次实验

姓名 时间 实验名称 10.17上午 学号 地点 四合院102 班级 分治算法实验（用分治法查找数组元素的最大值和最小值）。 实验目的 通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。 在满足分治法的条件下，根据不同的输入用例，能准确的输出用例中的最大值与最小值。并计算出程序运行所需要的时间。 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 ①先解决小规模的问题，如数组中只有1 个元素或者只有两个元素时候 的情况。 ②将问题分解，如果数组的元素大于等于3 个，将数组分为两个小的数 组。 ③递归的解各子问题，将(中分解的两个小的数组再进行以上两个步骤 ((最后都化为小规模问题。 ④将各子问题的解进行比较最终得到原问题的解。 void SelectMaxMin(int *a,inti,intj,int&max,int&min) { if(i==j) { max= a[i]; min =a[i]; return; } else { int mid=(i+j)/2; intmaxi,maxj,mini,minj; SelectMaxMin(a,i,(i+j)/2,maxi,mini); SelectMaxMin(a,((i+j)/2)+1,j,maxj,minj); 实验原理 实验步骤 关键代码 if(maxi>maxj) max=maxi; else max=maxj; if(mini

附录：完整代码

SelectMaxMin.cpp:

#include #include #include #include #include using namespace std;

void SelectMaxMin(int *a,inti,intj,int&max,int&min) {

if(i==j) {

max= a[i]; min =a[i]; return; } else {

int mid=(i+j)/2;

intmaxi,maxj,mini,minj;

SelectMaxMin(a,i,(i+j)/2,maxi,mini); SelectMaxMin(a,((i+j)/2)+1,j,maxj,minj);

if(maxi>maxj) max=maxi; else

max=maxj;

if(mini