算法设计技巧与分析答案

算法设计技巧与分析参考答案第1章算法分析基本概念1.1(a)6(b)5(c)6(d)61.4算法执行了7+6+5+4+3+2+1=28次比较1.5(a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。(b)算法MODSELECTIONSORT执行的元素赋值的最多45332445121224124545454545454533333333333333242424242424454545454545121212121212121212121224242424121212121212122424244524121212次数是3(1)2nn,元素已按非升序排列的时候达到最小值。1.7由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。1.11由上图可以得出比较次数为5+6+6+9=26次。1924751917131211815458111317219134811151271571217521119517248137151221719513114815127比较均为1次，共5次比较为3次，2次，1次比较为6次比较9次431256729344444333334121212121212555556667724321次9761次2次2次6次2次2次1.13FTF,TTT,FTF,TFF,FTF1.16(a)执行该算法，元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。(b)执行该算法，元素比较的最多次数是(1)2nn。元素已按非升序排列时候达到最大值。(c)执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。(d)执行该算法，元素赋值的最多次数是3(1)2nn。元素已按非升序排列时候达到最大值。(e)n用O符号和符号表示算法BUBBLESORT的运行时间：2()tOn，()tn(f)不可以用符号来表示算法的运行时间：是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。1.27不能用关系来比较2n和2100n增长的阶。∵221lim0100100nnn2n不是2(100)on的，即不能用关系来比较2n和2100n增长的阶。1.32(a)当n为2的幂时，第六步执行的最大次数是：12,2kknj时，11[log]lognniiknnn(b)由(a)可以得到：当每一次循环j都为2的幂时，第六步执行的次数最大，则当33,22kkmnj（其中32k取整）时，11[log(31)]log(1)nnkiiimnn(c)用符号表示的算法的时间复杂性是(log)Onn已证明n=2k的情况，下面证明n=2k+1的情况：因为有21222kk所以n=2k+1时，第六步执行的最大次数仍是nlogn。(d)用符号表示的算法的时间复杂性是()n。当n满足/2jn取整为奇数时，算法执行的次数是n次，其他情况算法执行次数均大于n。(e)O更适合表示算法的时间复杂性。因为本算法时间复杂性从()n到(log)Onn，而是表示精确阶的。1.38对n个数进行排序。第5章归纳法5.3（本题不仅有以下一个答案）1.max(n)过程：max(i)ifn=1returna[1]t=max(i-1)ifa[i-1]treturna[i-1]elsereturntendif5.6最多次数：0,1()(1)(1),2nCncnnn1(1)()2njnnCnj最少次数：2,1)1(1,0)(nnCnnCC(n)=n-15.7参考例5.15.14(a)不稳定，例如：可见SELECTIONSORT中相等元素的序在排序后改变。(b)(c)(d)(f)稳定5.17(a)利用10()()nnPxxPxa取3x，543210(3)(3)(3)(3)(3)(3)PPPPPP21100(3)3*(3)437(3)3*(3)211(3)3PPPPP324354(3)3*(3)1112(3)3*(3)2338(3)3*(3)51019PPPPPP5.18(a)(2,5)(2,2)(2,1)(2,0)pppp2224*2241*21yyyy第6章分治6.3输入：A[1,2,…n]12454524124545244545241245452412输出：max,min1.fori=1tomid2.j=high-i3.ifa[i]a[j],thenexchangea[i],a[j]4.endfor5.fori=lowtomid6.ifa[i+1]a[low],thenexchangea[low],a[i+1]7.endfor8.fori=mid+1tohigh9.ifa[i+1]a[high],thenexchangea[high],a[i+1]10.endfor6.5输入：一个整数数组A[1,2,…,n]输出：sum1.ifhigh-low=1then2.sum=a[low]+a[high]3.else4.mid=(low+high)/25sum1=sum(low,mid)6sum2=sum(mid+1,high)7.sum=sum1+sum28.endif9.returnsum算法需要的工作空间为36.10.32151415111725513214151525111415151725325114151532111751112517513215153214151415111711172551255132321515141415151111171725255151122519171537184532512212151817514532252219371225191732511537184522122517193251184522153712251719513218452237151212252517191951513245451818223715121725195132453718152212172519513222184537151225195145186.31彩色代表i,j所指的数字j总在i前6.3627133118451617532753133118451617275313311845161753272713183145161753131831451617532731131816453117534527131718161753131816274531233227184511631219162552141418111219162332452725526314181112191612111418191612111112181618191619111116161919324527255263632527324552252725272727455263455263526352636363111214161819232527325263456.42Quicksort不是稳定的。6.43bcefg均为适应的，a、h不是适应的。第7章动态规划7.1(c),算法BOTTOMUPSORT7.5字符串A=”xzyzzyx”和B=”zxyyzxz”的最长公共子序列长度为4，共有6个最长公共子序列，分别是：①zyyx②zyzz③zyzx④xyyx⑤xyzz⑥xyzx7.9C[1,5]=C[1,1]+C[2,5]+r[1]*r[2]*r[6]=307C[1,5]=C[1,2]+C[3,5]+r[1]*r[3]*r[6]=252C[1,5]=C[1,3]+C[4,5]+r[1]*r[4]*r[6]=372C[1,5]=C[1,4]+C[5,5]+r[1]*r[5]*r[6]=260所以最优括号表达式为（M1M2）((M3M4)M5)7.151000[,]min{[,],[,1][1,]}DijDijDiDj4051312091134021620D107160944021820D2111[,]min{[,],[,2][2,]}DijDijDiDj207160944021820D3222[,]min{[,],[,3][3,]}DijDijDiDj3051313091144021620D4333[,]min{[,],[,4][4,]}DijDijDiDj4051312091134021620D7.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23当物品体积为负值时，运行算法会发生溢出错误。第八章贪心算法8.12由算法从s到t要选择先到a然后到t,其结果为4，而从s到t距离为2，所以探索不总是产生从s到t的距离sta1328.138.23（共有4棵最小生成树，此处仅举一例）1326549121215134543132654912151345431326549121513454313265491215134543132654912151345431326549121513454349999204884161328816131212121212281348.24（共有4棵最小生成树，此处仅举一例）1234561234561234561234561234561234561234561234561234561234561234561234568.31每一个二叉树都取左边为0，右边为1则最优编码为a:10b:001c:0001d:0000e:01f:11注意：编码不唯一回溯法12cbafe22101697383255d