《分治与递归算法实验》由会员分享，可在线阅读，更多相关《分治与递归算法实验（8页珍藏版）》请在装配图网上搜索。
1、实验二 分治与递归算法的应用一、实验目的1掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。3学会利用分治算法解决实际问题。二、实验内容1. 问题描述：题目一：线性时间选择给定n个元素和一个整数k,要求用O（n）时间找出这n个元素中第k小元素。题目二：金块问题老板有一袋金块（共n块，n是2的幂（n2），最优秀的雇员得到其中最 重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望 用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。【输入输出样例】ch:DocueTi,ts and. Settin
2、.gs.Ad&iThi3t ratorDebug44. eze请输人金块的数蚤n 输入映金子的重量3_45_6344.52.51.17.9星董全坦是7 - ? 最轻仝块是1 1Pfgee anyto cont inue题目三：求最大两个数和最小两个数 利用分治法求一组数据中最大的两个数和最小的两个数。2. 数据输入：个人设定，由键盘输入。3. 要求：1）上述题目任选其二。上机前，完成程序代码的编写2）独立完成实验及实验报告三、实验步骤1.理解算法思想和问题要求；2. 编程实现题目要求；3. 上机输入和调试自己所编的程序4. 验证分析实验结果；5. 整理出实验报告。一实验目的二问题描述三算法设计
3、包含：数据结构与核心算法的设计描述、函数调用及主函数设计、 主要算法流程图等1. 金块问题： 考虑到可能输入数据有一个或者两个这种情况， 所以解决问题时分三种情况考虑，然后通过函数调用来实现寻 找最大最小的数值。 复杂性分析：当 n 是 2 的幂时，即对于 某个正整数k, n等于2的k次方，可以证明，任何以元素比 较为基础的找最大和最小元素的算法，其元素比较下界均为 3n/2-2 次。因此，过程 maxmin 在这种意义上是最优的。 T(n)=2T(n/2)+22.最大最小两个数：与金块问题类似，这是寻找最大最小的两个 数。利用循环嵌套条件语句进行判断，选择出最大最小的两个 数。四. 程序调试
4、及运行结果分析1) 有五个金块，其重量分别为2.3，1.3 ，6.9， 2， 1成功运行程序后输出最重和最轻的金块的重量。會输入金块的数量；青输入吕块金子的重量G.3 1.3 6.9 2 1 畏重金块是6.9最轻金块是1Press any key 七o con七inue2) 如下图所示，输入六个数分别为：5,9,12,3,16,2 成功运行后 输出最大的 2 个元素 16，12 最小的 2 个元素 2,3。庐要输入几个数?:青分别输入：5 9 12 3 16 g騷入的数虫曇大的2元畫为：16 12 騎入的数覆小的讣元秦为；2 3Press anp key to contztniw.五. 实验总
5、结通过本次实验，我学会了如何运用分治法将整个问题分解成若干个小 问题后分而治之，使其产生出方便求解的子问题，必要时逐步合并这 些子问题的解，从而得到问题的解。在实验中我观察了相关算法结合 老师上课讲解的，我觉得这类问题实际可以用一个递归方程来表示， 通过递归逐步求解问题。同时，通过本次实验我也发现递归算法的重 要性，自己对递归算法还不能熟练的应用。所以，在课下我会继续努 力掌握这种算法，以便能在以后熟练的应用它。通过第三题明白了眼 过千变不如手动一遍，上课是听懂了.课下我又仔细的上网看了研究 了一下，但是今天敲出来还是有一些问题，我觉得一些问题是值得注 意的.附录：程序清单(程序过长，可附主要
6、部分)1) 金块问题程序如下：#includeusing namespace std;int i，n;float a100;void maxmin(int i，int j，float &fmax，float &fmin)int mid;float lmax，lmin，rmax，rmin;if(i=j)fmax=ai;fmin=ai;else if(i=j-1)if(airmax)fmax=lmax;elsefmax=rmax;if(lminrmin)fmin=rmin;elsefmin=lmin;int main()cou t请输入金块的数量：endl;cinn;cou t请输入n块金子的重量
7、endl;for(i=1;i=n;i+)cinai;float max,min;maxmin(1,n,max,min);cou t最重金块是max最轻金块是minendl;return 0;2) 求最大两个数和最小两个数#includeiostreamusing namespace std;int a100;void _maxmin(int i,int j,int *max1,int *min1,int *max2,int *min2) int max,min,minmax,minmin;if(i=j)*max1=*min1=*min2=*max2=ai;elseif(i=j-1)if(aia
8、j)*max1=*min2=aj;*min1=*max2=ai;else*max1=*min2=ai;*min1=*max2=aj;elseint m=(i+j)/2;_maxmin(i,m,max1,min1,max2,min2); _maxmin(m+1,j,&max,&min,&minmax,&minmin); if(*max1max)*max2=*max1;*max1=max;if(max!=minmax)if(*max2minmax)*max2=minmax;elseif(*max2min)*min2=*min1;*min1=min;if(min!=minmin)if(*min2minmin)*min2=minmin;elseif(*min2min)*min2=min;int main()int n,i,m,max2,min2;cout你要输入几个数？ endl;cinn;cou t请分别输入：endl;for(i=0;in;i+)cinm;ai=m;_maxmin(0,n-1,&max0,&min0,&max1,&min1);max1endl;c o u t 输入的数中最大的2个元素为： max0 min1endl;cout输入的数中最小的2个元素为：min0 return 0;
分治与递归算法实验
