算法分析与设计实验报告
第 1 次实验
姓名 秦宇峰 学号
2013080101
04
班级 计科 1301
时间 10.17 上午 地点 四合院 102
实验名称 分治算法实验(用分治法 查找数组元素的最大值和 最小值)
实验目的 通过上机实验,要求掌握分治算法的问题描述、算法设计思想、程序设计。
实验原理
在满足分治法的条件下,根据不同的输入用例,能准确的输出用例中的最大
值与最小值。并计算出程序运行所需要的时间。
实验步骤
① 先解决小规模的问题, 如数组中只有 1 个元素或者只有两个元素时候
的情况。
② 将问题分解,如果数组的元素大于等于 3 个,将数组分为两个小的数
组。
③ 递归的解各子问题,将(中分解的两个小的数组再进行以上两个步骤
((最后都化为小规模问题。
④ 将各子问题的解进行比较最终得到原问题的解。
关键代码
void max_min(int *array,int l,int r,int &nmax,int&nmin)
{
if(l==r)//数组只有一个元素时
{
nmax = array[l];
nmin = array[l];
return;
}
if(l+1 == r)//数组有两个元素时,比较大小并赋值
{
if(array[l]>=array[r])
{
nmax = array[l];
nmin = array[r];
return ;
}