算法设计与分析实验报告：分治算法实验

算法分析与设计实验报告

第 1次实验

姓名 时间 实验名称 秦宇峰 10.17上午 学号 地点 201308010104 四合院102 班级 计科1301 分治算法实验（用分治法查找数组元素的最大值和最小值） 实验目的 通过上机实验，要求掌握分治算法的问题描述、算法设计思想、程序设计。 实验原理 在满足分治法的条件下，根据不同的输入用例，能准确的输出用例中的最大值与最小值。并计算出程序运行所需要的时间。 ① 先解决小规模的问题，如数组中只有1 个元素或者只有两个元素时候的情况。 ②将问题分解，如果数组的元素大于等于3 个，将数组分为两个小的数组。 ③递归的解各子问题，将(中分解的两个小的数组再进行以上两个步骤 ((最后都化为小规模问题。 ④将各子问题的解进行比较最终得到原问题的解。 void max_min(int *array,intl,intr,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 ; } else if(array[l]

附录：完整代码 #include

#include #include #include using namespace std;

voidmax_min(int *array,intl,intr,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 ; }

else if(array[l]

nmax = array[r]; nmin = array[l]; return ;

} }

int m = (l+r)/2; intrmax,rmin;

max_min(array,l,m,rmax,rmin);//递归求左边的最小值

intlmax,lmin;

max_min(array,m,r,lmax,lmin);//递归求右边的最大值

nmax = max(lmax,rmax); nmin = min(lmin,rmin); }

int main () {

inti,j=0;

double k=0.0;

clock_tstart,end,over; start=clock();

end=clock(); over=end-start; start=clock(); //my test

ofstreamfout(\int r;

for(int bb=0;bb<=100000;bb++) {

r = rand();

//cout<< r<

}

fout.close(); int a[100000];

ifstream fin(\intdd,Datalen=-1; while( ! fin.eof() ) {

//cout<

fin>>a[Datalen]; }

fin.close(); intmnum,nnum;

max_min(a,0,Datalen,mnum,nnum); cout<

printf(\system(\return 0; }