25分治算法

分治算法问题1：找出伪币给你一个装有16枚硬币的袋子。16枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。方法1任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。方法2将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。方法3分析上述三种方法,分别需要比较15次,8次,4次,那么形成比较次数差异的根本原因在哪里?方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较方法2:每一枚硬币只进行了一次比较方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。问题2：金块问题有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。方法1假设袋中有n个金块。可以用for循环经过2n-2次比较找出最重、最轻的金块。算法如下：max=a[1];min=a[1];for(i=2;i=n;i++)//2n-2次比较{if(a[i]max)max=a[i];if(a[i]min)min=a[i];}方法2：n≤2，识别出最重和最轻的金块，一次比较就足够了。n＞2，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA与LA，以此类推，B中最重和最轻的金块分别为HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法。分治过程HA:10LA:8HB:4LB:2HA:5LA:3HB:9LB:1HA:10LA:2HB:9LB:1101比较过程分析从图例可以看出，当有8个金块的时候，方法1需要比较14次，方法2只需要比较10次,那么形成比较次数差异的根本原因在哪里?其原因在于方法2对金块实行了分组比较。对于N枚金块，我们可以推出比较次数的公式：假设n是2的次幂，c(n)为所需要的比较次数。方法1：c(n)=2n-2方法2：c(n)=2c(n/2)+2。由c(2)=1,使用迭代方法可知c(n)=3n/2-2。在本例中，使用方法2比方法1少用了25％的比较次数。证明令n=2kC(2K)=2C(2K-1)+2=2[2C(2K-2)+2]+2=22+2+22C(2K-2)=22+2+2[2C(2K-3)+2]=23+22+2+23C(2K-3)……=2K-1+2K-2+…+2+2K-1C(2)=2K-1+2K-2+…+2+2K-1=2K-2+2K-1C(n)=3n/2-2分治思想分治(divide-and-conquer)就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。其三个步骤如下；1.分解(Divide)：将原问题分成一系列子问题。2.解决(Conquer)：递归地解各子问题。若子问题足够小，则可直接求解。3.合并(combine)；将子问题的结果合并成原问题的解。分治思想问题S问题S问题SS的解问题S1……问题S2问题Si问题Sn……S1的解……S2的解Si的解Sn的解……问题的分解子集解的合并子问题求解问题3:归并排序问题4:快速排序简单定义：在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在哪个部分中并调整集合上下界，重复直到找到目标元素。问题5：二分查找算法例子：//x：待查找的元素，n：数组集合大小，num数组单调递增intlow=0,high=n,mid,res=-1;//low，high：数组边界while(low=high){mid=(low+high)/2;//mid:将集合分割为两部分if(num[mid]==x)//查找到符合元素x{res=mid;break;}elseif(num[mid]x)//x在右边部分，调整集合下界low=mid+1;else//x在左边部分，调整集合上界high=mid-1;}//若未找到x，则res=-1参考程序问题6：求an方法一：循环做n-1次乘法，如38方法二：3X3=99X9=8181X81=6561只需要做三次乘法快速幂n是偶数n是奇数38343231•am+n=am*an如：25=22*23递归代码intpow(inta,intn){if(n==1)returna;intt=pow(a,n/2);if(n%2==1)returnt*t*a;elsereturnt*t;}非递归写法an=a=a*a*………*a*a*a比如：311=3=3*3*3*32n*tn+2n-1*tn-1+……+22*t2+21*t1+20*t023*1+22*0+21*1+20*12n*tn2n-1*tn-122*t221*t120*t023*122*021*120*1求：ann=2n*tn+2n-1*tn-1+……+22*t2+21*t1+20*t0(ti取0,1)前一项是后一项的平方tntn-1…..t2t1t0是n的二进制形式非递归代码intpow(inta,intn){intans=1;while(n0){if(n%2==1)ans=ans*a;//ti等于1时，将a累乘到ans上n=n/2;a=a*a;//a20,a21,a22,a23,……..,a2n}returnans;}1130:二分查找1131:高次幂取模1211:转圈游戏1249:麦森数1237:一元三次方程求解1220:瑞士轮1219:聪明的质监员1251:跳石头