分治算法实验报告

第 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（maxi>maxj) max=maxi； else max=maxj； if（mini附录：完整代码

SelectMaxMin.cpp:

＃include ＃include ＃include 〈cstdio> #include ＃include 〈cstdlib〉 using 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（maxi〉maxj) max=maxi; else

max=maxj;

if(minielse

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; i〈m; i++） a［i] = rand（)％100； for(int i=0； i〈m; 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）; ｝