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

实验一 分治与递归算法的应用一、实验目的1掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。3学会利用分治算法解决实际问题。二、问题描述题目四：金块问题老板有一袋金块（共n块，n是2的幂（n2）,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。三、算法设计（一）、数据结构与核心算法的设计描述数据结构：#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 aMax;coutn;cout它们的标号分别为0n-1endl;cout请输入对应金块的重量:;for(int i=0;iai;maxmin(0,n-1,a,max,min);cout最轻的金块重量为：minaj?左半边递归调用，得到lmax,lmin;右半边递归调用，得到rmax,rmin是否max=ajmin=ai;max=aimin=aj;lmaxrmax?lminrmin?max=rmaxmin=rminmax=lmaxmin=lmin程序清单：#include#define Max 100void maxmin(int i,int j,float a,float &max,float &min);void main()int n;float max,min;float aMax;coutn;cout请输入对应金块的重量:;for(int i=0;iai;maxmin(0,n-1,a,max,min);cout最重的金块重量为：maxendl;cout最轻的金块重量为：minaj)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.但是如果用分治法的话，平均比