《算法设计与分析C++语言描述(陈慧南版)课后答案》由会员分享，可在线阅读，更多相关《算法设计与分析C++语言描述(陈慧南版)课后答案（11页珍藏版）》请在装配图网上搜索。
1、第一章1-3.最大公约数为1。快1414倍。主要考虑循环次数，程序1-2的我hile循坏体做了10次，程序1-3的while循环体做了14141次（14142-2循坏）若考虑其他语句，则没有这么多，可能就601倍。第二章2-&（1）画线语句的执行次数为log”。O（log）。划线语句的执行次数应该理解为一格整体。（2）画线语句的执行次数为iJ(+1)(+2)6（3）画线语句的执行次数为|_而_|。0（亦）。（4）当n为奇数时画线语句的执行次数为（+1）（+勺,4当n为偶数时画线语句的执行次数为卩7一。0（/?2）。42-10.(1)当n1时，5n2-8/?+25/?2,所以，可选c=5,；70
2、=1对于nnQ,/(?7)=5n2-Sn+28时，5/?2-8/?+25n2-n2+24n2,所以，可选c=4,n0=8o对于nnQ,/(77)=5；72-877+24/?2,所以，57?2-8h+2=Q(772)o(3) 由(1)、(2)可知，取q=4,c2=5,nQ=8,当nn0时，有cjr5n2-Sn+2c2n2所以5772-87?+2=0(772)o2-11.(1)当n3时，lognnlog3n,所以/(?)=20/+logn2n。可21选c=,4=3。对于nn0,f(n)4时，lognnlog2n,所以f(n)=if/lognn2。可选c=1,幵o=4。对于nnQff(n)n2cg(
3、n)f即/(?)=O(g(n)(3) 因为f(n)=(log/z)log/,=771OS(1OS，,g()=7?/logn=nlog”2。当n4时，f(n)=n,g(h)=niog;12n所以,可选c=1,n0=4对于幵nnQ,f(ti)cg(h),即f(n)=G(g()。第二章2-17.证明：设n=2,则i=log/o丁何吨)+2/?log7?=22T+2/?log/?=2T(今+2(logn一log2)+2nlogn=2,T(今+2x2log”-2=222T+2xxlog+2x2/?logn-2n=237今+2(logn-log4)+2x2logn-2n=TTIL2訂丿=2kT+3x2/7
4、logn一2n-4+2knlogn-2n-4n2n(k_l)=2lT(2)+2(i-l)nlogn-2n-4n2n(i-2)=中x4+2nlogn(log7?-l)-(/-2)(/-l)n=2n+2nlog2n-2/7logn-(log2n-3logn+2)=77log2n+nlogn当/?2时，T(/?)2Hlog27?o所以，r(/z)=0(/?log2/?)o第五章54SolutionTypeDaiidCl(mtleft.mtright)while(!SmallQeftnght)&leftnght)mtm=Dhdde(left,right);if(xPm)left=m+l;elseret
5、urnS(P)5-7.templatemtSortableList:BSearch(constT&x,intleft.iiitright)constif(left=iight)liltm=(iight+left)/3;if(xlm)retiunBSeairh(x,m+lfright);elsereturnm;return-1;第五章9.证明：因为该算法在成功搜索的情况卞，关键字之间的比较次数至少为log71J,至多为Llog/J+lo在不成功搜索的情况下，关键字之间的比较次数至少为LlognJ+1，至多为|_10列+2。所以，算法的最好、最坏情况的时间复杂度为O(log/7)o假定查找表中任何
6、一个元素的概率是相等的，为丄，那么，nF不成功搜索的平均时间复杂度为&(/?)=0(log/?),+1成功搜索的平均时间复杂度为As(n)=2/+/?=-l=O(log/?)onnn其中，/是二叉判定树的内路径长度，是外路径长度，并且E=I+2n.11.步数012345初始时11111111111OO211111OO311111OO411111OO排序结果11111OO步数01234567初始时5583432814233585823234585833234585842334585852334588排序结果2334558812. (1)证明：当”=0或“=1或n=2时，程序显然正确。当n=rig
7、ht-left+12时，程序执行卞面的语句：mtk=(right-left-rl)/3;StoogeSort(lefl,nght-k);StoogeSort(left+k,right);StoogeSort(lefl,nght-k); 首次递归StoogeSort(lefl,nght-k);时，序列的前2/3的子序列有序。 当递归执行StoogeSort(left+k,right);时，使序列的后2/3的子序列有序，经过这两次递归排序，使原序列的后1/3的位置上是整个序列中较人的数，即序列后1/3的位置上数均人于前2/3的数，但此时，前2/3的序列并不一定是有序的。 再次执行StoogeSor
8、t(leff,iight-k);使序列的前2/3有序。经过三次递归，最终使序列有序。所以，这一排序算法是正确的。(2)最坏情况发生在序列按递减次序排列。zz/9nT(O)=T(l)=O,T(2)=l,T(7?)=3T+1。i3丿T(/?)=3T17?1+1=33T(-h|+1亠叫树+3+1=21_1=3,T(2)+-log33x/冒泡排序最坏时间复杂度为O(，)，队排序最坏时间复杂度为0(/7log/?),快速排序最坏时间复杂度为0(/7log/?)3所以,该算法不如冒泡排序，堆排序,快速排序。13. templateselect(T&x,intk)if(inn)swap(m,n);if(m-
9、rnk|k=0)coutHOutOfBounds11;retiimfalse;mt*p=newten超k;mtmidJeft=O,right=ii-l,cnt=Oj=0,i-=0;fbr(mti=0;i0)doniid=(left+iight)/2;if(aimdbi)nght=mid;elsecnt=nud;break;wlule(leftright-1)if(aleftcnt)if(cnt0)for(j=0;jcnt;j+)tempj=ar;r+;lefl=cnt;k-=cnt;elsetempj=bi;left=O;k-Selsefor(j=0;jk;j-H-)tempj=ar;r+;l
10、eft=cnt;k-=cnt;retiuiitempk-l;第六章1由题可得:oAAA=22?2兰2wQ，w2，vr3，些Mg%丿(2，3，5，7i4j(2所以，最优解为(x0,xpx2,x3,x4,x5,x6,)=1三丄(M丄121最人收益为10+5x+15+6+18+3=55。33第六章6-9.普里姆算法。因为图G是一个无向连通图。所以n-l=m=ii(n-1)/2;O(n)=m=O(n2);克鲁斯卡尔对边数较少的带权图有较高的效率，而加=0(十99卜0(),此图边数较多，接近完全图,故选用普里姆算法。6-10.T仍是新图的最小代价生成树。证明：假设T不是新图的最小代价生成树，r是新图的最
11、小代价生成树，那么cost(r)vcost(T)。有cost(T5)-c(n-l)8)=iiiinc(6,8)-Bcost(46)5c(78)+Bcost(47)=inin7+93+9=122.向后递推的计算过程如上题所示向前递推过程如下：cost(5,8)=0cost(4,6)=7,cost(4,7)=3cost(3,3)=minl+cost(4,6),4+cost(4,7)=7,cost(34)=min6+cost(4,6),2+cost(47)=5cost(35)=min6+cost(4,6),2+cost(47)=5cost(2,l)=min3+cost(3,3)3+cost(3,5)
12、=8cost(2,2)=min6+cost(3,3),8+cost(3,5),5+cost(3,4)=10cost(l0)=min5+cost(2,l),2+cost(22)=12所以，d(4,6d(4,7)=8,d(3,3)=d(3,4)=d(3,5)=7,d(2,l)=5,d(2,2)=4,d(l,0)=2从s到t的最短路径为(0,d(l,0)=2,d(2,2)=4,d(3,4)=7,d(4,7)=8),路径长为12。第七章9.charA8=x,z,_000000001111011112011222011223011223011233012233(a)ciU所以，最长公共字串为第七章00_
13、001102220122023301340134024402(x,y,z,z)o000000_133313222131211222222131222121211222122212(b)siUJ11.voidLCS:CLCS(niti,intj)if(i=0|j=0)retiini;if(cij=ci-lj-l+l)CLCS(i-lj-l);Coutai;elseif(ci-lj=cij-l)CLCSelseCLCS(ij-1);12.intLCS:LCSLengthQfor(iiiti=1;i=in;i-H-)ciO=O;for(i=1;i=n;i+)cOi=O;for(i=1;iv=m;i+
14、)for(mtj=1;j=cij-l)cij=ci-lj；elseci|j=cij-l;retimicmn;15.SJ(0,0),S：=(10,2),S。=(0,0),(10,2),S；=(15,5),(25,7),S1=(0,0),(10,2),(15,5),(25,7),Sf=(6,8),(16,10),(2U3),(3U5),S=(0,0),(6,8),(1610),(2113),(3115)S；=(9,1),(15,9),(25,11),(30,14),(40,16),=(0,0),(6,8),(15,9),(16,10),(21,13),(30,14),(3M5)8-1.状态空间：描
15、述问题的各种可能的情况，一种情况对呀状态空间的一个状态。显示约束：用于规定每个Xi取值的约束条件称为显示约束隐式约束：用于判定一个候选解是否为可行解的条件问题状态：在状态空间树中的每个节点称为一个问题状态解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点扩展结点：算法从X出发，访问X的摸个后继结点y,则X被称为扩展结点约束函数：一个约束函数是关于部分向量的函数Bk(x0,x
16、l.xk),它被定义为：如果可以判定Y的子树上不含任何答案状态,则Bk(x0,xlxk)为false,否则为true.剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态节点数，他们统称为剪枝函数8-2boolplace(intk,int,I,int*x)For(intj=0,jk,j+)If(xj=i)|(abs(xjj)=abs(jk)Returnfalse;Returntrue:Voidnqueens(intk,intn,int*x)(For(inti二0;in;i+)If(place(k,I,x)Xk二I;If(k=n-lFor(i二0;in;i+)coutxEiendl;Return;Elsenqueens(k+1,n,x)Voidnqueens(intn,int*x)Nqueens(0,n,x);
算法设计与分析C++语言描述(陈慧南版)课后答案
