分治与递归算法实验.doc

实验二 分治与递归算法的应用 一、实验目的 1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。 二、实验内容 1.问题描述： 题目一：线性时间选择 给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。 题目二：金块问题 老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 【输入样例】 题目三：求最大两个数和最小两个数 利用分治法求一组数据中最大的两个数和最小的两个数。 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目任选其二。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。 一．实验目的 二．问题描述 三．算法设计 包含：数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流程图等 金块问题： 考虑到可能输入数据有一个或者两个这种情况，所以解决问题时分三种情况考虑，然后通过函数调用来实现寻找最大最小的数值。 复杂性分析：当n是2的幂时，即对于某个正整数k，n等于2的k次方，可以证明，任何以元素比较为基础的找最大和最小元素的算法，其元素比较下界均为[3n/2]-2次。因此，过程maxmin在这种意义上是最优的。T(n)=2T(n/2)+2 最大最小两个数：与金块问题类似，这是寻找最大最小的两个数。利用循环嵌套条件语句进行判断，选择出最大最小的两个数。 四.程序调试及运行结果分析 有五个金块，其重量分别为2.3，1.3 ，6.9， 2， 1成功运行程序后输出最重和最轻的金块的重量。 如下图所示，输入六个数分别为：5,9,12,3,16,2 成功运行后，输出最大的2个元素16，12最小的2个元素2,3。 五.实验总结 通过本次实验，我学会了如何运用分治法将整个问题分解成若干个小问题后分而治之，使其产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。在实验中我观察了相关算法结合老师上课讲解的，我觉得这类问题实际可以用一个递归方程来表示，通过递归逐步求解问题。同时，通过本次实验我也发现递归算法的重要性，自己对递归算法还不能熟练的应用。所以，在课下我会继续努力掌握这种算法，以便能在以后熟练的应用它。通过明白了眼过千变不如手动一遍,上课是听懂了.课下我又仔细的上网看了研究了一下,但是今天敲出来还是有一些问题,我觉得一些问题是值得注意的 附录：程序清单 （程序过长，可附主要部分） 金块问题程序如下： #includeiostream using namespace std; int i,n; float a[100]; void maxmin(int i,int j,float fmax,float fmin) { int mid; float lmax,lmin,rmax,rmin; 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(lmaxrmax) fmax=lmax; else fmax=rmax; if(lminrmin) fmin=rmin; else fmin=lmin; } } int main() { cout请输入金块的数量：endl; cinn; cout请输入n块金子的重量endl; for(i=1;i=n;i++) cina[i]; float max,min; maxmin(1,n,max,min); cout最重金块是max 最轻金块是minendl; return 0; } 求最大两个数和最小两个数 #includeiostream using namespace std; int a[100]; void _maxmin(int i,int j,int *max1,int *min1,int *max2,int *min2