算法分析与设计实验报告
第 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);
实验原理
实验步骤
关键代码