算法设计与分析C++语言描述(陈慧南版)课后答案

第一章1-3.最大公约数为1。快1414倍。主要考虑循环次数，程序1-2的while循环体做了10次，程序1-3的while循环体做了14141次（14142-2循环）若考虑其他语句，则没有这么多，可能就601倍。第二章2-8.（1）画线语句的执行次数为logn。(log)n。划线语句的执行次数应该理解为一格整体。（2）画线语句的执行次数为111(1)(2)16jniijknnn。3()n。（3）画线语句的执行次数为n。()n。（4）当n为奇数时画线语句的执行次数为(1)(3)4nn，当n为偶数时画线语句的执行次数为2(2)4n。2()n。2-10.（1）当1n时，225825nnn，所以，可选5c，01n。对于0nn，22()5825fnnnn，所以，22582()nnn。（2）当8n时，2222582524nnnnn，所以，可选4c，08n。对于0nn，22()5824fnnnn，所以，22582()nnn。（3）由（1）、（2）可知，取14c，25c，08n，当0nn时，有22212582cnnncn，所以22582()nnn。2-11.(1)当3n时，3loglognnn，所以()20log21fnnnn，3()log2gnnnn。可选212c，03n。对于0nn，()()fncgn，即()(())fngn。注意：是f(n)和g(n)的关系。（2）当4n时，2loglognnn，所以22()/logfnnnn，22()loggnnnn。可选1c，04n。对于0nn，2()()fnncgn，即()(())fngn。（3）因为loglog(log)()(log)nnfnnn，()/loglog2ngnnnn。当4n时，log(log)()nfnnn，()log2ngnnn。所以，可选1c，04n，对于0nn，()()fncgn，即()(())fngn。第二章2-17.证明：设2in，则login。22log2nTnTnn2222log2log222nnnTnn2222loglog22log2nTnnnn22222log22nTnnn2322222log22log2222nnnTnnn3322loglog422log22nTnnnnn33232log242nTnnnn22log24212kknTknnnnnk12221log2422iTinnnnni1242loglog121innniin2222log2loglog3log2nnnnnnnn2loglognnnn当2n时，22logTnnn。所以，2logTnnn。第五章5-4.SolutionTypeDandC1(intleft,intright){while(!Small(left,right)&&leftright){intm=Divide(left,right);if(xP(m)right=m-1;elseif(xP[m])left=m+1;elsereturnS(P)}}5-7.templateclassTintSortableListT::BSearch(constT&x,intleft,intright)const{if(left=right){intm=(right+left)/3;if(xl[m])returnBSearch(x,left,m-1);elseif(xl[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}第五章9．426351701234567-10证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为logn，至多为log1n。在不成功搜索的情况下，关键字之间的比较次数至少为log1n，至多为log2n。所以，算法的最好、最坏情况的时间复杂度为logn。假定查找表中任何一个元素的概率是相等的，为1n，那么，不成功搜索的平均时间复杂度为log1uEAnnn，成功搜索的平均时间复杂度为21logsInEnnEAnnnnn。其中，I是二叉判定树的内路径长度，E是外路径长度，并且2EIn。11.步数012345初始时111111[11]1[11]∞2[1]11[11]∞3111[11]∞4111[1]1∞排序结果11111∞步数01234567初始时5583432∞1[4233]5[85]∞2[323]45[85]∞3[32]345[85]∞4[2]3345[85]∞523345[5]8∞排序结果2334558∞12.（1）证明：当0n或1n或2n时，程序显然正确。当n=right-left+12时，程序执行下面的语句：intk=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);①首次递归StoogeSort(left,right-k);时，序列的前2/3的子序列有序。②当递归执行StoogeSort(left+k,right);时，使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较大的数，即序列后1/3的位置上数均大于前2/3的数，但此时，前2/3的序列并不一定是有序的。③再次执行StoogeSort(left,right-k);使序列的前2/3有序。经过三次递归，最终使序列有序。所以，这一排序算法是正确的。（2）最坏情况发生在序列按递减次序排列。010，21，2313nn。设322in，则log1log31ni。2431331139nnn49319n122333313iiiin31322ii31322ilog1log31312222nnlog3log313nlog3log31n冒泡排序最坏时间复杂度为2n，队排序最坏时间复杂度为lognn，快速排序最坏时间复杂度为lognn。所以，该算法不如冒泡排序，堆排序，快速排序。13.templateclassTselect(T&x,intk){if(mn)swap(m,n);if(m+nk||k=0){coutOutOfBounds;returnfalse;}int*p=newtemp[k];intmid,left=0,right=n-1,cnt=0,j=0,r=0;for(inti=0;im;i++){while(k0){do{mid=(left+right)/2;if(a[mid]b[i])left=mid;elseif(a[mid]b[i])right=mid;else{cnt=mid;break;}}while(leftright-1)if(a[left]b[i])cnt=left;elsecnt=left-1;if(kcnt){if(cnt0){for(j=0;jcnt;j++){temp[j]=a[r];r++;}left=cnt;k-=cnt;}else{temp[j]=b[i];left=0;k--;}}else{for(j=0;jk;j++){temp[j]=a[r];r++;}left=cnt;k-=cnt;returntemp[k-1];}}}}第六章1.由题可得：012345601234561051576183,,,,,,,,,,,,2357141ppppppp，所以，最优解为01234562,,,,,,,1,,1,0,1,1,13xxxxxxx，最大收益为211051561835533。8.17240765625232815169182018783第六章6-9.普里姆算法。因为图G是一个无向连通图。所以n-1=m=n(n-1)/2;O(n)=m=O(n2);克鲁斯卡尔对边数较少的带权图有较高的效率，而1.992mnn，此图边数较多，接近完全图，故选用普里姆算法。6-10.T仍是新图的最小代价生成树。证明：假设T不是新图的最小代价生成树，T’是新图的最小代价生成树，那么cost(T’)cost(T)。有cost(T’)-c(n-1)cost(t)-c(n-1)，即在原图中存在一颗生成树，其代价小于T的代价，这与题设中T是原图的最小代价生成树矛盾。所以假设不成立。证毕。第七章1.Bcost(1,0)=0;Bcost(2,1)=c(1,1)+Bcost(1.0)=5Bcost(2,2)=c(1,2)+Bcost(1,0)=2Bcost(3,3)=min{c(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)}=min{6+2,3+5}=8Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7Bcost(3,5)=min{c(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)}=min{3+5,8+2}=8Bcost(4,6)=min{c(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)}=min{1+8,6+7,6+8}=9Bcost(4,7)=min{c(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)}=min{4+8,2+7,6+8}=9Bcost(5,8)=min{c(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)}=min{7+9,3+9}=122.向后递推的计算过程如上题所示向前递推过程如下：cost(5,8)=0cost(4,6)=7,cost(4,7)=3cost(3,3)=min{1+cost(4,6),4+cost(4,7)}=7,cost(3,4)=min{6+cost(4,6),2+cost(4,7)}=5cost(3,5)=min{6+cost(4,6),2+cost(4,7)}=5cost(2,1)=min{3+cost(3,3),3+cost(3,5)}=8cost(2,2)=min{6+cost(3,3),8+cost(3,5),5+cost(3,4)}=10cost(1,0)=min{5+cost(2,1),2+cost(2,2)}=12所以，d(4,6)=d(4,7)=8,d(3,3)=d(3,4)=d(3,5)=7,d(2,1)=5,d(2,2)=4,d(1,0)=2从s到t的最短路径为(0,d(1,0)=2,d(2,2)=4,d(3,4)=7,d(4,7)=8),路径长为12。第七章9.charA[8]={‘0’,’x’,’z’,’y’,’z’,’z’,’y’,’x’}B[8]={‘0’,’z’,’x’,’y’,’y’,’z’,’x’,’z’}