实验一分治与递归算法的应用一、实验目的
1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。

2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。

3．学会利用分治算法解决实际问题。

二、算法问题要求
老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。

并对自己的程序进行复杂性分析。

三、算法设计
在n个元素的集合中寻找最大和最小值元素。

(1)将集合一分为二，变为两个集合，目的是在较小的两个集合中分别找最大、最小元素。

(2)递归分解较小集合，直到每个集合中的元素个数≤2，然后找出小集合的最大、最小元素。

（3）合并（回溯）：自低向上把子问题的解合并，大元素中取最大者，小元素中取最小者，最后得到元问题的解。

四、验证分析实验结果
图1.1 运行界面
图1.2 运行结果五、程序
#include <stdio.h>
int a[100];
maxmin(int i,int j,int &fmax,int &fmin){
int mid ;
int lmin,lmax,rmin,rmax;
if (i==j){
fmax=a[i];
fmin=a[i];
}
else if (i==(j-1)){
if (a[i]<a[j])
{
fmax=a[j];
fmin=a[i];
}
else{
fmax=a[i];
fmin=a[j];
}
}
else {
mid=(i+j)/2;
maxmin(i,mid,lmax,lmin);
maxmin(mid+1,j,rmax,rmin);
if ( lmax>rmax) fmax=lmax;
else fmax=rmax;
if ( lmin<rmin) fmin=lmin;
else fmin=rmin;
}
}
int main (){
int n,i,j,max,min;
printf ("输入金块总数：");
scanf("%d",&n);
printf ("输入一组金块质量");
for (i=1;i<=n;i++){
scanf("%d",&a[i]);
}
i=1;
maxmin(i,n,max,min);
printf("%d\n %d\n",max,min);
return 0;
}
六、实验总结
二分法通过分析时间复杂度和占用空间。

而二分法的思想是通过把大问题逐
步分解为小问题，直到可解的小问题，最后把小问题的分解部分合并，最终得到大问题的解。

但是二分法的内存消耗大。