分治与递归算法的应用.docVIP

实验一 分治与递归算法的应用 一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二、问题描述 题目四：金块问题 老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三、算法设计 （一）、数据结构与核心算法的设计描述 数据结构： #define Max 100 //设置存放金块的数组的最大上限 void maxmin(int i,int j,float a[],float max,float min);//递归求最大最小元素 核心算法描述： 本算法为分治算法中的二分法，可以用较少的比较次数解决金块问题。算法描述如下： 1）将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大和最小值 2）递归分解直到每组元素发的个数=2,可简单的找到最大（小）值。 3）回溯时合并子问题的解，在两个子问题的解中大者取大，小者取小，即合并为金块问题的解 （二）、函数调用及主函数设计 void main() { int n; float max,min; float a[Max]; cout请输入金块的个数：; cinn; cout它们的标号分别为0~n-1endl; cout请输入对应金块的重量:; for(int i=0;in;i++) cina[i]; maxmin(0,n-1,a,max,min); cout最轻的金块重量为：minendl; } （三）、主要算法流程图及程序清单 分治算法流程图： i=j i=j-1 else 是 否 程序清单： #includeiostream.h #define Max 100 void maxmin(int i,int j,float a[],float max,float min); void main() { int n; float max,min; float a[Max]; cout请输入金块的个数：; cinn; cout请输入对应金块的重量:; for(int i=0;in;i++) cina[i]; maxmin(0,n-1,a,max,min); cout最重的金块重量为：maxendl; cout最轻的金块重量为：minendl; } void maxmin(int i,int j,float a[],float max,float min) { if(i==j) { max=a[i]; min=a[i]; } else if(i==j-1) { if(a[i]a[j]) { max=a[i]; min=a[j]; } else { max=a[j]; min=a[i]; } } else { int mid; float lmax,lmin,rmax,rmin; mid=(i+j)/2; maxmin(i,mid,a,lmax,lmin); maxmin(mid+1,j,a,rmax,rmin); if(lmaxrmax) max=lmax; else max=rmax; if(lminrmin) min=lmin; else min=rmin; } } 四.程序调试及运行结果分析 程序调试：刚开始的时候把赋值符号“=”和比较符号“= =”弄混了，所以第一次运行时老出错，不过改正过来以后，就运行通过了。 运行结果： 五.实验总结 通过这次实验，我对算法的意义又多了一些认识，一个好的算法真的很重要，特别是当数据量很大的时候。就比如本题中的金块问题，如果用蛮力法，对金块逐个进行比较，平均比较次数是3（n-1）/2.但是如果用分治法的话，平均比较次数为1.5n-2,比前者要好一点，最重要的是递归算法的空间效率和运行效率都是比较低的。这也提醒我们，实际应用中不能仅仅根据时间复杂性选择算法。 a[i]a[j]? max=a[i] min=a[i]; 判断i和j的关系 开始 max=a[i] min=a[j]; max=a[j] min=a[i]; mid=(i+j)/2; 左半边递归调用，得到lmax,lmin;右半边递归调用，得到rmax,rmin lmaxrmax? lminrmin? max=lmax min=lmin max=rmax min=rmin