金块问题实验报告.docVIP

PAGE  PAGE 19 金块问题实验报告 篇一：算法设计金块问题 算法实验报告一分治法实验 金块问题 问题描述： 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块 算法思想： 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。 问题分析: 一般思路：假设袋中有n 个金块。可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。 分治法：当n很小时，比如说， n≤2，识别出最重和最轻的金块，一次比较就足够了。当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法 程序设计 据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n lt; 1，则程序返回f a l s e，否则返回t r u e。 当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。 首先处理n≤1的情况。若ngt;1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。 在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值，这个工作对应于3 )。for 循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [ M a x ]进行比较，根据比较结果来修改M i n和M a x（如果必要）。 复杂性分析 注意到当n为偶数时，在for 循环外部将执行一次比较而在f o r循环内部执行3 ( n / 2 - 1 ) 次比较，比较的总次数为3 n / 2 - 2。当n 为奇数时，f o r循环外部没有执行比较，而内部执行了3(n-1)/2次比较。因此无论n 为奇数或偶数，当ngt;0时，比较的总次数为「3n/2ù-2次。 源程序 #includelt;iostreamgt; #includelt;string.hgt; #includelt;algorithmgt; using namespace std; float max(float g1,float g2)//比较找大值 { return(g1gt;g2?g1:g2); } float min(float g1,float g2)//比较找小值 { return(g1lt;g2?g1:g2); } float Search_Max(float g[],int left,int right)//用二分法递归找最大值 { if(left==right) //当只有一个数时，直接返回该值 { float max; max=g[right]; return max; } if(right-left==1) { float LM,RM; LM=g[left]; RM=g[right]; return(max(LM,RM)); } if(right-leftgt;1) { float LM,RM; int mid=(left+right)/2;//取中点 LM=Search_Max(g,left,mid); RM=Search_Max(g,mid,right);//左