《分治与递归算法的应用》由会员分享，可在线阅读，更多相关《分治与递归算法的应用（4页珍藏版）》请在金锄头文库上搜索。
1、实验一 分治与递归算法的应用一、实验目的1掌握分治算法的基本思想（分-治-合） 、技巧和效率分析方法。2熟练掌握用递归设计分治算法的基本步骤（基准与递归方程） 。3学会利用分治算法解决实际问题。二、问题描述题目四：金块问题老板有一袋金块（共 n 块，n 是 2 的幂（n2） ）,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。三、算法设计（一）、数据结构与核心算法的设计描述数据结构：#define Max 100 /设置存放金块的数组的最大上限void maxmin(int i,in
2、t j,float a,float /递归求最大最小元素核心算法描述：本算法为分治算法中的二分法，可以用较少的比较次数解决金块问题。算法描述如下：1）将数据等分为两组（两组数据可能差 1） ，目的是分别选取其中的最大和最小值2）递归分解直到每组元素发的个数n;coutai;maxmin(0,n-1,a,max,min);cout#define Max 100void maxmin(int i,int j,float a,float void main()int n;float max,min;float aMax;coutn;开始判断 i 和j 的关系max=aimin=ai;max=aimi
3、n=aj;aiaj?max=ajmin=ai;mid=(i+j)/2;左半边递归调用，得到lmax,lmin;右半边递归调用，得到rmax,rminlmaxrmax?lminai;maxmin(0,n-1,a,max,min);coutaj)max=ai;min=aj;elsemax=aj;min=ai;elseint 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,比前者要好一点，最重要的是递归算法的空间效率和运行效率都是比较低的。这也提醒我们，实际应用中不能仅仅根据时间复杂性选择算法。
