算法设计与分析基础习题参考答案.docx

习题1.15.证明等式gcd(m.n>=gcd(n.mn(1.n)对每一对正整数m.n都成立.Hint:根据除法的定义不难证明：如果d整除U和V.那么d一定能整除u±v;加果d整除U.那么d也能修整除U的任何整数倍ku.对于任意一对正整数m,n,辑设d能整除m和nJE么d一定能整除n和r=mmodn=m-qn:显然，假设d能整除n和r,也一定能整除n=r+qn和n.数对(m.n)和(n.r)具有相同的公约数的有限非空集，其中也包括了最大公约数.故gcd(111.n)=gc<1.(n.r)6.时于第一个数小于第二个数的一对数字,欧几里得打法利会如何处理?该尊:法在处埋这种输入的过程中,上述情况最多会发生几次？Him：对于任何形如(K=mvn的一对数字.Euc1.id算法在第一次登代时交换m和n.即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.Za.对于所有IWm.n这10的输入.Euc1.id算法最少要做几次除法?(1次)b.对于所有IWmmWIO的输入,Euc1.k1.亢法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)PggPWgWPwcucPwgcPwgcw、cPwcCPgcgPgP-农夫W狼G山羊C一白菜2.(过桥问题)7,1.22/,2.5,105.1(1/,1.2.5.10(。)，.;，13)(15)7,12-17)/,1.2.5.105f1.()/,1.5,101125.10-分别代表4个人.J手电筒4 .对于任意实系数a.b.c.某个算法能求方程ax2÷bx+c=0的实根,写出上述算法的伪代码(可以假设Sqrt(x)是求平方根的函数)算法QUadra1.iC(a.b.c)“求方程ax2+bx+c=()的实根的算法“4ft入:实系数ahc"输出;实根或者无解信息IfaOD-b*h-4*acIfDX)temp*-2*ax1.-(-b+sqrt(D)tempx2(-b-sqrt(D)>'tcmpreturnx1.,x2e1.seifD=Oreturn-M2*a)e1.serc(um"norea1.Isme1.se/a=f1.ifb0return-cbe1.se/a=b=Oifc=0return,fcnrea1.numbers*e1.sereturn,wnorea1.roots”5 .描述将十进制整数表达为.进制整数的标准算法必用文字描述b.用伪代码描述解答:今将十进制整数转换为：进制整数的修法输入：一个正整数n输出，正整数n相应的二进制数第一步：用n除以2.余数赋给Ki(i三<M2.),商赋给n第二步；如果n=0,那么到第三步，否那么重或第一步第三步：将Ki按照i从高到低的Itfi席输出b.伪代码眸法DecoBin(n)“将I进制整数n转换为二进制整数的算法陷入:正整数nMfi出:该正整数相应的二进制数,该数存放于数组BinU.n中i=1.whi1.en!=4)do(Bini=n%2;n=(int)n2;i+：>whi1.ei!=()doprintBini;i9.考虑下面这个算法.它求的是数组中大小相差最小的两个元素的差(算法略)对这个究法做尽可能多的改良.算法MinDistance(O.n-1)“输入:数组A(0.n-1.)"输出:thesma1.1.estdistancedbetweentwoofitse1.ementsdmin<fori<0ton2doforJ4i+1.ton-Idotemp44ijiftemp<dmindmin-tempreturndmin习题1.3考虑这样一个排序算法,该算法对于待持序的数组中的姆一个元素,计算比它小的元素个数,然后利用这个信息.将各个元素放到有序数祖的相应位置上去.foriOton1doCounti*Ofort<Oton-2doforj<i÷1ton-1doifi<AjCcnntjCountj+1e1.seCountiCounti+1for£Oton1doSCunfi<Aia.应用该算法对列表”60,3531.98.14.47”排序b.该和法稳定吗？C,该算法在位吗？解：a.该算法对列表”60.35.81.98.14.4T排序的过程如下所示:Initia1.1.yCountAfterpassi=OCountAfterpassi1CountAfterPaSSi=2CountAfterPaSSi=3CountAfterpassi=4CountFina1.stateCountArray0.5ArrayS0.5OOOOOO3O11OO122O143O15O1O23145O2I6()3581I981447I14I35476()I819Kb该算法不杨定.比方对列表“2.2*”排序C该辞法不在位.额外空间fbrSa1.Count1.1.4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现以下对数组的操作.使得操作时间不依敕数组的长发.a删除数组的第i个元素(1.<=i<=n)b.州除有序数祖的第i个元素(依然有序)hints:a. Rep1.acetheithe1.ementwiththe1.aste1.ementanddecreasethearraysizeof1b. Rep1.acetheithC1.CmCntwihaspecia1.symbo1.thatCanno1.beava1.ueofthearray'sc1.emcn(c.g.,0foranarrayofpositivenumbers)tomark(heithpositionisenp<y.(*1.az>de1.e<ion">习题2.1欧几里得竟法的时间复杂度欧几里得笄法,又称混转相除法.用于求两个自然数的最大公约数.算法的思想很简单,基于卜面的数论等式gc<1.(a,b)=gcd(b,amodb)其中gcd(a,b)表示a和b的班大公约数,mod是模运獴,即求a除以b的余数.算法如下：输入：两个整数&b输出:a和b的最大公约数functiongcd(a,b:intcgcr):intcgcr;ifb=0returna;e1.sereturngc<i(b.amodb):endfunction欧几里得究法是最古老而般典的宛法，埋解和掌提这一尊法并不难，但要分析它的时间及杂度却并不容易,我们先不考虑模运算本身的时间经杂度(算术运算的时间发杂度在Knu1.h的TAOCP中有详细的讨论).我们只考虑这样的问题：欧几里得算法花球坏情况卜所需的模运蚌次数和添入的a利b的大小有怎样的关系？我们不妨设Qb>=1.(假设a<b我们只需多整一次模运算.假设b=0或a=b模运豫的次数分别为。和1).构造数歹Jun:UO=a.u1.=b.uk=uk-2moduk-1.(k>=2).显然.假设算法需要n次模运算.那么行Un=SCd(a.b).un+1.=O.我们比拟数列un)和班波那奥数列Fn,R)-<=un,F1.=1.<=un-1,又因为由Ukmoduk+1.=uk+2,11IfJuk>=uk+1.+uk+2,由数学归嗨去容易得到uk>=Fnk.于是得到a=uO>=Fn,b=uO>=Fn1.,也就是说如果欧几里得以法需要做n次模运算,班么b必定不小于Fn-1.换句话说,假设b<Fn-1.那么算法所需模运算的次数必定小于n.根据菲波那契数列的性质，有Fn-ii.618>n/Sqrt(5).即b>(1.618)nsqrt(5),所以模运算的次数为O(Igb)以b为底数=O(Ig(2)b)一以2为底数，输入规模也可以看作是b的bh位数.习题2.27.对以下新古进行证明:(如果是错误的,请举例a.如果Nn)Wo(g(n),那么g(n)O(t(n)b.>0.(g(n)=(g(n)解：a.这个断古是正确的.它指出如果t(n)的增长率小于或等于g(n)的增长率,那么g(n)的培氏率大于或等于(三)的增长率由t(n)cg(n>fora1.1.nn.wherec>0(一)/(«)g(")那么：CIbraHnNnOb.这个断言是正确的.只需证明(ag()u(g(MRg5)U<9(砥5)。设f(nC6(g(n)JE么有：f(n)cag(n)fora1.n>=n0.c>0f(n)ctg(n)ftwa1.1.n>=Mc1.=c0>0即：f(n)(g(n)又设f(n)6(g(n).那么有：/()cg()fora1.1.n>=nO.c>Of()-ag(n)=c1.ag(n)afora1.1.n>=11.c1.=c0>0UP：f(n)¢-)(tg(n)8.证明本节定理对于以下符号也成立：&Q符号b.。符号证明:a«weneed(oproof(hatifti(n)0(g1.(n)andc2(n)Q(g2(n),then(1(n)÷<2(n)(max(g1.(n)g2(n)«由t1.(n)WQ(g1.g)ti(n)c1.g1.(n)fora1.1.n>=n1.,wherec1.>0由c2(n)Q(g2(n),T2(n)c2g2(n)fora1.1.n>=n2fcwherec2>0那么取c>=minc1.c2).当n>=maxn1.n2)Bf:t1.(n>÷<2(n>>c1.g1.(n>+c2g2(n>>cg1.(n)+cg2(n)>c(g1.(n>+g2(n)NCmaX1.g1.(n),g2(n)所以以命遨成立，bU(n)+2nW电(max(g】(),g2()证明：由大的定义知.必须确定常数c1.、c2和n«.使得对于所有n>=n.有：C1.maX他1(”).g2(”)”()+t2(n)<max(g1.("),g2(")由存在非负整数a1.*和id使：a1.4g1.(n)<=t1.(n><=a2*'g1.(n>-(1)由I2(n)"(g2(n)知.存在非负整数b1.,b2和n2使：b1*g2(n)<=t2(n)<=b2*g2(n)“(2)(1.)+<2):a1.g1.(n)+b1.g2(n)<=t1.(n)+t2(n)V=a21*g1.(n)+b2*g2(n)令c1.=nin(a1.,b1.),c2=max(a2,b2).那么C1.*(g1.+g2)<=t1.(n)+t2(n)<=c2(g1.+g2)-(3)不失一般性假设11ux(g1.(n).g2(n)=g1.(n).显然.gI(n)+g2(n)<2g1(n).即g1.+g2<2max1.g2)又g2(n)>0.g1.(n)+g2(n)>g1.(n),Wg1.+g2>max(g1.,g2).那么(3)式转换为:CPnax(gi.g2)<=t1.(n)+t2(n)v=c2*2max(g1.g2)所以当C1.=min(a1.b1.Ac2=2c2=2max(c1.1c2).nOmax(n1.n2)SJ.当n>=n时上述不容式成立.证毕.10.切忌算法走的步数和人真实走的步数的区别,算法是不需要走回头路的习题2.4解以下递推关系(ftab).V()=X(ZI-I)+5当n>1.时-V(I)=O解：a. x(n)=z(n-1)+5forn>1,x(1.)=0x(n)-xn-1)+5=x(n-2)+5+5=x(n-2)+52=x(n-3)+5+52=x(n-3)+53=.=(n-»)+5t=H(I)+5(n1)=5(n1).b. (n)=3(j-I)当n>1.时X(I)=4解：b.x(n)=3x(n1)forn>1,x(1.)=4x(n)=3x(n-1)=33x(n-2)=32x(11-2)=3*3r(n3)=33x(n3)=31.x(ni)=3n1x(1.)=43n1.对于计算n1的递IU修法Kn),建立其递仃调用次数的递推关系并求解.解：2. C(n)=C(n-1)+1,C(O)=1(thereisaca1.1.hutnomu1.tip1.icationswhenn=0).C(n)=C(n-1)+1=C(n-2)+1+1=C(n-2)+2=.=C(n-i)+i=.=C(O)+n=1+n.考虑以下递归算法，该律法用来计算前n个立方的和：S(n)=1.3+23+.+n3,算法S(n)“输入：正整数n场出:前n个立方的和ifn=1.returnIe1.sereturnS(n-1.)+n*nna.建立该算法的根本操作次数的递推关系并求解b.如果将这个算法和直截r当的非递打算法比.你做何评价？幅a.a. 1.etAf(n)bethenunberofnni1.tip1.icatioiisna<1.ebyt1.ea1.gorithm.Wchavethefo1.1.owingrecurrencere1.ationforit:f(n)=f(n-1)+2,f(1.)=0.V'ecanSoIVeitIbackwards1.v>titntions:f(n)=(n-1)+2=(n-2)+2+2=f(n-2)+2+2=(n-3)+2+2+2=(n-3)+2+2+2=.=(n-i)+2i=.=(1.)+2(n-1.)=2(n-1).6 .汉诺塔的非迷以何胆请见F:worN维续教团算法设计与分析根底7 .a.请基于公式2n=2n1.+2n1.,设计一个递归算法,当n是任意非负整数的时候,该算法能够计算2n的值。b.建立该算法所做的加法运算次数的递推关系并求解c.为该算法构造一棵递归园用树然后计算它所做的递归网用次数.d.对于该问理的求解来说，这是一个好的算法吗？解：a.算法POWer(n)“基于公式2n=2n-1.+2n-1.,计算2n输入:非负整数n“输出:2n的值Ifn=()return1E1.sereturnpowcr(n-1.)+powcr(n-1.)b. (n)=2A(n-1)+1,4(0)=0.A(n)="2A(n1)÷1=22½(n-2)+1+1=22A(n-2)+2+1=222A(n-3)+1÷2+1=23(n-3)+22+2÷I=.=2iA(n-i)+2i1.+2i-2+.+I=2n(0)+2n-1.+2n-2+.+1=2",+2n-2+.+1=2n-1.whi1.ej>0andj1.>vdocoun1.-coun1.+iA+IJ-Af(j÷1.*-vreturncount比拟计数涔是否辅在了正确的位置?如果不对,请改正.解:应改为:算法Sf1.Ana1.ysis(A(0.n-1)"inpu1.：包含n个可排序元索的一个数组A0.m1)仇H1.tput:所做的关健比拟的总次数count-0fori*-1.(oivIdov-A(i)jf1whi1.ej>=0andAj>vdaCOunI-COim+1.A(j+H-A(j)j-j-1.ifj>=0count-count÷I(j÷1.*-vreturnCoUn1.7.bgcd(m.n)切法性能破坏情况下为两个整数为斐波居很数列,即k时间最长时，最小的整数时必定为斐波那锲数列。9 .我认为埃拉托色尼筛的效率为根号n.10 .gcd(a.b)熨杂性估计c=a%b：c<i2:在算法中即表现为n(余数)每两次循环至少战少为原来的一半，所以该舞法时间复杂度估算为21.ogn=O(1.ogn)：由于能力有限,更精确及杂的时间红朵度的计算还没有掌握.在最坏的情况下(如m和n是两个相邻的斐波居契数时)可以稍默改良成1.441ogn欧几里侬算法在平均情况下的性能需要大眼箭幅的海度亚杂的数学分析，其迭代的平均次数约为(121n21nn)pi2+1.47t在最差情况下在平均情况下.假设成功查找的概率是p(O<=p<=1.)Hints:Cworst(n)=n÷1在成功i找下,对F任意的I.第次匹配发生在第i个位置的可能性是Pd比拟次数是i,在荏找不成功时.比拟次数是n+1.可能性是IPC(W夕(m1+21.+i2+Ti勺+(九+1)(1p)nnnn1.1+2+.+i+.411+(111)(1p)71孑吟斗(IP)=(2-P)(n+1)4此座翻译有向题，原题类似与:前一段时间看到一道Goog1.e的面试题在各大论坛被炒得很火题目如下:“有一个100层SS的大厦.你手中有两个相同的玻璃图根子.从这个大厦的某一层扔下胭棋了就会砰，用你手中的这两个玻璃困根子，找出一个足优的策略，来得知那个临界层面，”题目虽然看起来简单，但是仔细想想，此遨中然含的算法道珅以及实用价值还是很值得好好研究-卜.石头在网上也看到了不少热心朋友的解法(CSDN、ChinaUnix).行过之后感觉还是接有启发的.于是总结一下,主要的算法行以下几种：<1>等分段来最小伯：这种算法先假设把大楼分成等岛的X段，这样在最差的情况下，要确定临界段，我们需要投掷100.次，确定了临界段之后要确定临界层，我们需要再投掷X-I次。这样，问SS就成了求函数Rx)=<100x-1.Hx-1.)的最小值问题。由于f(x>存在球小值且只有一个驻点，所以当x=10时ftx)取得最小值,最小值为18.<2>假设投掷次数是均匀分布的.那么为门史最坏情况的投掘数最小,我们希里无论临界段在现里.总的投掷数屈不变(也就是说将投掷数均匀分布).这样我们就可以收设第一次投掷的层数是f,转化成数学模型，可以得到如下方程式f+(f1)+.+2+>=99,即f<f+iV2>=99的最小整数解，斛出结果等于14,程序算法如下：按结果分析看来，方法一的最小值确实比拟小(10)但是问题是最大值无法确定(比方假设临界层在第99层那么需要仍19下)：而方法二的算法好在能得出个固定的临界层tft这样便于一些问咫的处理.总的来说，石头认为两种方法各有所长，虽然方法：看起来确实更接近出巡者的本意，但是如果将板子木身俄碎的概率也考虑iS去就不一定了(当然，一般来说层数越高破碎的概率应该越大,但是我们试想一下如果假设根干破碎的几率是和层数成反比,那么使用方法一是否会有更好的效果呢？).然而不管出题井的意图是什么.我觉得这个时日所引出的数学模型还是很有实用意义的，特别在一些数据挖掘应用中.我猜测这些口法是不是与Goog1.e数据库的技术内幕有什么岷系呢前几天和一个业内的前辈谈起下一代互联网的技术.电势，说到了所谓的“算法时代”的话题，看来关注一线有趣的算法也不错呢不知不觉时间又晚了，还是先休息吧：)6 .给出一个长度为n的文木和长度为m的模式何成的实例,它是童力字符申匹配算法的一个最差输入.并指出,对于这样的输入需要做多少次字符比拟运尊.Hints:文本:由n个。组成的文本模式:前m-1个是0,最后一个字符是I比拟次数：m(n-m+1.)7 .为蛮力字符匹配算法写一个伪I尊J指定的模式,它能够返回给定的文本中所有匹配子串的数tA1.gorithmsBFS<ringmatchC11O.n-1.P0.m-11)“童力字符匹配输入:数如TO.n-1.)-长度为n的文本.数加P0.m-1.-长度为11的模式“输出:在文本中匹配成功的子申数Mcoun1.<-0for1-0ton-mdoj-0whi1.ej<mandP(j=Ti+j1.j+ifj=mcount*-count+1NIUmcount8 .如果所要搜索的模式包含一些英语中较少见的字符.我Q应该如何修改该蛮力算法来利用这个信息.Him:每次都从这些少见字符开始比拟,如JK匹配，那么向左边和右边进行其它字符的比拟.习题3.3奇数派问遨：证明如下：容易验证当n=3时成立：假设n=k时如果成立，那当n=k+2时,k+2个人记为点A1.A2,A(k+2),d=min(AiA)不妨设A(k+1.)A(k+2)的距离为d,那么A(k+1.)和A(k+2)相互是距离近的点，收到彼此的派：如果A(k+1.)和A(k+2)还收到其他人的派，其他k个人至多有k-1个流.利用抽展原理,其他k个人中必有个人没有流：如果A(k+1.)和A(k+2)没有收到其他人的派.其他k个人相互在掷海,利用归纳假设,其他k个人中必有一个没有温，n=k+2时命遨成立.7.凸包问题找那些x、y坐标最小或拧被大的10.该问题可以用以卜图表示：该问造即转化为把3x+5y这条直线平行移动，越在上面k值越大,即弼为求阴影局部的某个极点,习题3.4注意该时的假设（所以不需要排列组合算法再去生成旅行线路）,只需要对每条线路求出殿短路径的长度再比拟这些路径，所以,该问题的根本操作为加法。下而谈谈排列组合的递归和非递打算法：（一时兴起,与此题无关）全界列的递归除法给定数字1n,输出从中选出m个数的排列和组合。为了简单起见.采用递IU算法来描述,首先解决排列何起：这个算法不太漂亮，用到了两个全局变麻：intRR（j=（1.23.4.51:用来输出的全局缓冲区iniPERM.1.EN;/排列的长度voidPCnnutation<intarr.intn.intm）inti：if(m=O)fbr(i=<);i<PERMJ.EN;+i)priittR"%d"RR(iJ):printf<"n");return:for(i=0;i<n:+i)swap(a11ti,arrO);pcmutation(arr*1.n-1.m-I);swap(atfi.a11O);算法比拟简单，不详细说明了.祖令的递归算法voidco11b（inin.int11.in（bu1.Y）.intcount）if(m=O)“递归退出条件,打印回车fur(inii=0zi<cou11U+i)printf('"id".buff1.i)：PrintfCW);return;=2k-1.C(2)+2k-1.+2k-2+.+2/C(2)=I=2k-1+2k-1.+2k-2+.+2/后面局部为等比数列求和=2k-1.+2k-2/2(k-1.)=t2,2k=n=n2+n-2=3V2-2b.蛮力法的算法如下：算法SimpIcMaxMin(A11.r)"用蛮力法斛到数组A的最大伯和最小值"输入:数值数组A1.1.H"输出：最大值MaX和j"小值MinMax=Min=AU|:fori=1.÷IIordoifAi>MaxMax-Ai);e1.seifi<MinMinIAireturnMax.Min时间复杂度(n>=2(n-1.)算法MaXMin的时间处杂度为3M22SimpIeMaxMin的时间曳杂度为2n2都属于)(n),但比拟一下发现.MaXMin的速发要比SimpIcMaxMin的快一些.3自己写了个求a的n次方的java实现pub1.icstaticin(DF1.Oof(加a.intn)intresu1.t=0;if(n=1.)returna;Iif(n%2=0)(intnf1.oor=nHr(a.n2);resu1.t=(int)Math.)w(nf1.oor,2);Sys(em.ou(.print1.n(Nnevenais+noor+"*"÷nf1.oor);Sys1.ern.ut.prin1.1.n(*,resu1.1.isf,+resu1.t):returnresu1.t;1e1.se(ininf1.oor1.=nF1.oor(a.(n1)/2);ininf1.or2=nI1.oorPa;resu1.t=nf1.oor1.4,nt1.r2:Sys(cm.ou(.print1.nCanis÷n÷,'noddais,÷nf1.oor1.÷"f',÷nf1.oor2);returnresu1.t;显然，柒法次数递推式为f(n)=f(M2)+1.或者f(n)Mi(8W2)+2:简单看作最坏情况卜为f<n)=f(n2)÷2;最好情况(列表升序或降序)下：CbcsKn)=2Cbes1.(112)+11,2forn>1.(n=2k)Cbcst(I)=OC6(2)=20>(2fc-,)+2*-1=22Ct(2fc-2)+2fc-2+2fc,=22Cfc(2*2)+2,+2fc,=222C6(2fc3)+2k-3+2fc1.+2fc1=23<7b(2fc3)+2k1.+2fc1+2fc1=2iCb(2k-i)+i2k-1=2*C6(2*-fc)+k2k-1.=k2k-1.=Iogn.键做比拟次数M(n)M(n)=2M(n2)+2nforn>1.M(I)=O9.修诙合并排序，在B、C两个数殂合并时，一但比拟时发现B的元素小于C,站在C的角度考虑，C后面的元索都大于B.假设前面的元素都考虑过了，那么此处没有导致情况，假设B的元素大于C那么必定对于C这个元素来说,B前面的所有元素都比C中那个元索小,不形成对置.B后面的所有元家郎大于C.那么B后面的所有元索与C中被比拟的您个元素形成倒置.这些对置形成了包含C中那个元素的所有对田，当B元素和C比拟后，C元素指针变为下一个元素，这样，包含C当前指针前面的所有元泰的倒置都考虑过了，我们只要考虑C元素后面的情况就可以了,由于对于。举个例子.一次合并过程中,现在数组B元素为2389.C元素为1457.这样假设B和C本身中所含的倒盥为b利c.那么合并后的C数组的导致为：s初始为1.>÷c23891457(1.)2>1.时倒置为Q1)(31)(81)(91)S=S+48>4时倒置为(84)(94)S=S+2(3)8>5时倒置为(85)(95)S=S+2:(4)8>7时倒置为(87)(97)S=S+2;那么s=b+c+!0IO当n=1.时，很显然是成立的.当n=2时,HP为4*4的期盘，可以分成4个2*2的期盘,可以分成两种情况.第种情况：己域充块在中间(黄色)Ti1.ingfinished1情况的的红色局部或第二种情况的蓝色局部.显然.剁下的局部都能给1.填满.假设n=2"K时，含有I块填充的”K2稣期盘能够被填满,就么含有n=2八（k+1.）必定得棋盘能够分成4个2K*2k,I块己埴充局部落在4块其中的1块，那么选择其他三块形成一个1.型，那么4块期盘分别变成n=2"k的问电。由于n=27C结论成立,那么己有I个填充块的2"（k+1.）*2Nk+1.）的期盘必定能够被的1.型填满。所以给定该题用分治法解决如下：如果n=2;即为2*2的己埴充1个方格的方块，显然，剩余的局部形成1.型.否那么（2）设n=k（k>2）把”M2小的方块分成4块.分别充紫墙充不含已填充方格的1.型.递归解决n=k-1.的问即习题4.21.应用快速排序对序列E.X.A.M,P.1.E按字母顼序排序I100ItOIIIIOIOIOIOII1(X)11000这种遍历顷序作为一种涮玛方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码它的应用范围很广.比方，n阶的Gray码相当于在n维立方体上的H;Imi1.gn1.可路，因为沿岩立方体上的边走一步，n维坐标中只会有一个值改变。再比方，Gray玛和Hanoi塔问题等价。Gmy码改变的是第几个数，HanOi塔就该移动哪个盘干.比方，3阶的Gray码每次改变的元素所在位置依次为I-2-1.3-I-2-1,这正好是3阶Hanoi塔每次移动盘子编号。如果我的可以快速求出Gray码的第n个数是多少，我们就可以箱出任意步数后Himoi塔的移动步骤，现在我告诉你，Gray码的第n个数（从0算起）是nxor（nshr1.）,你能想出来这是为什么吗？先自己想想吧.（考虑没有进位和有1进位两种情况）卜面我们把二进制数和Gray码都写在下面，可以看到左边的数异或自CJ右移的结果就等于右边的数.二进制数Gniy码000OoO(X)I(X)I010O1.1.Oi1.010I(X)110IOII1.1.HOIO1.I1.1.10010 .从n个元素中找出k个分型的组合可以这样找。给n个元案分别娘号为am.an.这样从n个元素中找k个分fit变为找设小编号为i的k个元素予集，i=1.2,.n-k+1.,所有这些k个元素的子集趾成了从n个元素的子集.而当i=1.时，该问题就转变成了从其它ni个元素中找k-1.个元素，加上i,构成k个元素的子集。i=2同理，用F（am.n.k）衣示从am.an个元素中找k个元素的组合当这块坏巧克力位于角上时，这个向SS转化为可以从一堆数玳为n的机子中拿走以多n-1个棋子，从数盘为m的板子中拿走最多In-I个机子，最后(1.1)为败局,显然,根据文中所说，当不等于n时.先走的人是胜局.每一步走后，都使向下的行数等于列数.同理.当n等于n时,先走的人是败局.更股化，当这块巧克力在中间时,如图:然巧克力被分成4局部(这里有些里更,但不影响解遨)，上、下、左、右其中他们的行数分别为k1.k2k3k4,如上图k1.=3k2=4k3=4k4=2.这些就转化为可以对应到四堆机子，分别为k1.、k2、k3、k4个朋一次就对应到可以分别从其中某一堆取走1个或所右机子.使用书上拈游戏的二进制解法即可，谁先走好在于k1.k2k3k4的二进制值.11 .算法过程如下：假设薄饼的数I1.为n,而薄饼目前的排列为PanCakg.n,其中，假设PanCakC5为最后1块，而PanCake1为最上面的-块.CakeSiZe1.n分别对应PanCake数组，为薄饼大小“k=n;3i1.e<k<0)whi1.e(isMax(cakesizck)k：m-findMax(cakesizek)Hip):f1.ip(k):其中isMax(cakesizek)判断CakeSiZek是否是cakesize1.k中最大尺寸.findMax(cakesizek)为从CakeSiZe1.k中找出最大尺寸,返回pancake的数组下标f1.ip(m)是把福板PanCakem往上物.这样最大的叫就到川上面了。再从第k个往上融，这样见大的就到k上去了。当k从n变化到0.所有就有序了.习SS6.1hintsortthe1.istandIhcnsimp1.yrcumthen2the1.ementsof和叶ted1.ist.效率：fiX设排序算.法的效率是OfnIogn).那么该算.法的效率是OfnIogn)+9(1)=Ofn1.ogn)3.hinta.初始化C-B-foreveye1.enn1.uiinAdo(1.<=i<=n)foreverye1.ementbjinB(1.<=<=m)Ifai=bjaddaitoCde1.etebjf11>mB最差情况:C为空.比拟的次数是nm.b.方法一：排序集合AForeverye1.ementbjinB用二分查找的方法在A中查找与bj相匹配的元素aIf查找成功Adda<oC效率分析：假设排序的效率是(NnIogn)JE么该算法效率0(n1.ogn)+110(1.ogn)=(n+m)0(1.ogn)方法二：首先对A和B都分别排序.然后对A和B应用合并排序,只愉出它们的公有元素.效率分析：假设排序的效率是O(Nogn),那么该算法效率OinIogn>+O(m1.ogm)+(n+m>=O(s1.ogs)wheres=11ax(n,11)方法三：首先将A和B合并为1.排序1.从左至右成对扫描1.If1.i=1.i+1Add1.iIoCi-i+2效率分析：假设排序的效率是O(nk>gn).那么该算法效率0(n+m(1.ogn)+(n+m)=O(s1.ogs)wheres=maxn.m4.hinta.持序数组.然后返回它的第一和最后元素假设排序的效率是O(n1.ogn)JE么该算法效率O(n1.ogn)+8(1)+6(D=O(n1.ogn)b蛮力和分治都是线性的,所以优于基于预排序的算法习KS6.32.b.A1.orithnBrutcForcePo1.ynomia1.Eva1.uationPO.n,x)/,hca1.gorithmcomputestheja1.cofPO1.ynOmia1.Patagivenpoint,x/1.n,theuhighestto1.owest.term"brt(yforcea1.gorithm/Input:AnarrayP().njofthecoefficientso