《算法设计及分析课后习题解答.pdf》由会员分享，可在线阅读，更多相关《算法设计及分析课后习题解答.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章第一章3.最大公约数为 1。快 1414 倍。程序 1-2 的 while 循环体做了 10 次，程序 1-3 的 while 循环体做了 14141 次（14142-2 循环）8.（1）画线语句的执行次数为nlogn。(logn)。ij（2）画线语句的执行次数为1i1j1 k1n(n1)(2n1)3。(n)。6（3）画线语句的执行次数为n。(n)。（4）当 n 为奇数时画线语句的执行次数为(n1)(n1)，4n(n2)2当 n 为偶数时画线语句的执行次数为。(n)。42210.（1）当n 1时，5n 8n2 5n，所 以，可 选c 5，n01。对 于n n0，f(n)5n28n2 5n
2、2，所以，5n28n2 (n2)。2222（2）当n 8时，5n 8n2 5n n 2 4n，所以，可选c 4，n08。对于n n0，f(n)5n28n2 4n2，所以，5n28n2 (n2)。222（3）由（1）、（2）可知，取c1 4，c2 5，n08，当n n0时，有c1n 5n 8n 2 c2n，所以5n 8n2 (n)。11.(1)当n 3时，logn n log n，所以f(n)20nlogn 21n，g(n)nlog n 2n。可选3322c 21，n0 3。对于n n0，f(n)cg(n)，即f(n)(g(n)。222222logn n log n，（2）当n 4时，所以f(n
3、)n/logn n，g(n)nlog n n。可选c 1，n0 4。对于n n0，f(n)n2 cg(n)，即f(n)(g(n)。（3）因为f(n)(logn)lognlog(logn)nlog(logn)，g(n)n/logn nlogn2。n，当n 4时，f(n)ng(n)nlogn2 n。所以，可选c 1，n0 4，对于n n0，f(n)cg(n)，即f(n)(g(n)。第二章第二章2-17.证明：设n 2i，则i logn。Tn 2T 2nlogn 22T22log2nlogn2222n n n n 22T n 2nlognlog22nlogn22 n 22nlogn2n22 22T
4、n nn 22T322log222nlogn2n2222 23T n 2nlognlog422nlogn2n32 n 32nlogn2n4n32 23T 2kTi1 n 2knlogn2n4nk22nk 1 2 T22i1nlogn2n4ni12ni2 242nlognlogn1i2i1n 2n2nlog2n2nlogn log2n3logn2 n nlog nnlogn当2n 2时，Tn 2nlog2n。所以，Tn nlog2n。第五章第五章5-4.SolutionType DandC1(int left,int right)while(!Small(left,right)&leftrigh
5、t)int m=Divide(left,right);if(xPm)left=m+1;else return S(P)5-7.template int SortableList:BSearch(const T&x,int left,int right)constif(left=right)int m=left+(right-left+1)/3;if(xlm)return BSearch(x,m+1,right);else return m;return-1;7m=left+(right-left+1)/3不能用：m=(left+right)/3，两者不同。受对半搜索的影响：m=(left+ri
6、ght)/2和 m=left+(right-left+1)/2是一样的94246213567130123455677012-10345670112233445566708证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为logn，至多为logn1。在不成功搜索的情况下，关键字之间的比较次数至少为logn1，至多为logn2。所以，算法的最好、最坏情况的时间复杂度为logn。假定查找表中任何一个元素的概率是相等的，为不成功搜索的平均时间复杂度为1，那么，nE logn，n1I nE 2nnE成功搜索的平均时间复杂度为Asn1 logn。nnn其中，I是二叉判定树的内路径长度，E是外路
7、径长度，并且E I 2n。Aun11.步数初始时1234排序结果步数初始时12345排序结果05433222152223332833333333344444445555555388885562555588701111111111111211111131111114111111512.（1）证明：当n 0或n 1或n 2时，程序显然正确。当 n=right-left+12 时，程序执行下面的语句：int k=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);首次递
8、归 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）最坏情况发生在序列按递减次序排列。2n 0 1 0，21，n 31。3logn1 3设n 2，
9、则i。log3 12i 4 4 2 n3n133n11 9n31939ii1i22i 3 n333313i1 3 22i3i1322logn13n12log31222 3nlog3log31log3log31 n冒泡排序最坏时间复杂度为 n2，队排序最坏时间复杂度为nlogn，快速排序最坏时间复杂度为 nlogn。所以，该算法不如冒泡排序，堆排序，快速排序。13.template select(T&x,int k)if(mn)swap(m,n);if(m+nk|k=0)coutOut Of Bounds;return false;int*p=new tempk;int mid,left=0,r
10、ight=n-1,cnt=0,j=0,r=0;for(int i=0;i0)domid=(left+right)/2;if(amidbi)right=mid;else cnt=mid;break;while(leftright-1)if(aleftcnt)if(cnt0)for(j=0;jcnt;j+)tempj=ar;r+;left=cnt;k-=cnt;elsetempj=bi;left=0;k-;elsefor(j=0;jk;j+)tempj=ar;r+;left=cnt;k-=cnt;return tempk-1;第六章第六章1.由题可得：p0p1p2p3p4p5p610 5 15 7
11、 6 18 3,，w0w1w2w3w4w5w62 3 5 7 1 4 123所以，最优解为x0,x1,x2,x3,x4,x5,x6,1,1,0,1,1,1，最大收益为10521156183 55。338.(n-1)%(K-1)=(11-1)%(3-1)=0,故无需补充虚游程。9 9普里姆算法。因为图 G 是一个无向连通图。所以 n-1=m=n(n-1)/2;O(n)=m=O(n2);克鲁斯卡尔对边数较少的带权图有较高的效率，而此图边数较多，接近完全图，m n1.99 n2，故选用普里姆算法。1010.T 仍是新图的最小代价生成树。证明：假设 T 不是新图的最小代价生成树，T是新图的最小代价生成
12、树，那么 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)=minc(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)=min6+2,3+5=8Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7Bcost(3,5)=minc
13、(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)=min3+5,8+2=8Bcost(4,6)=minc(3,6)+Bcost(3,3),c(4,6)+Bcost(3,4),c(5,6)+Bcost(3,5)=min1+8,6+7,6+8=9Bcost(4,7)=minc(3,7)+Bcost(3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)=min4+8,2+7,6+8=9Bcost(5,8)=minc(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)=min7+9,3+9=12（0，2，4，7，8）2.向后递推的计算过程
14、如上题所示向前递推过程如下：cost(5,8)=0cost(4,6)=7,cost(4,7)=3cost(3,3)=min1+cost(4,6),4+cost(4,7)=7,cost(3,4)=min6+cost(4,6),2+cost(4,7)=5cost(3,5)=min6+cost(4,6),2+cost(4,7)=5cost(2,1)=min3+cost(3,3),3+cost(3,5)=8cost(2,2)=min6+cost(3,3),8+cost(3,5),5+cost(3,4)=10cost(1,0)=min5+cost(2,1),2+cost(2,2)=12所以，d(4,6)
15、=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.char A8=0,x,z,y,z,z,y,x B8=0,z,x,y,y,z,x,z00000000000000001111111111222112222211223331122334112333412233440000000000000002133313122213122112221222131122212122112222122212(a)cij（
16、b）sij所以，最长公共字串为(x,y,z,z)。11.void LCS:CLCS(int i,int j)if(i=0|j=0)return;if(xi=yj)CLCS(i-1,j-1);Cout=cij-1)CLCS(i-1,j);else CLCS(i,j-1);12.LCS:LCS(int nx,int ny,char*a,char*b)m=nx;n=ny;x=a;y=b;c=new int*2;for(int i=0;i2;i+)ci=new int n+1;int LCS:LCSLength()c10=0;/0 列置 0for(int i=0;i=n;i+)c0i=0;/0 行置
17、0for(i=1;i=m;i+)for(int j=1;j=c1j-1)c1j=c0j;/上格左格，则取上格else c1j=c1j-1;/否则取左格for(j=0;j=n;j+)c0j=c1j;return c1n;/或 return c0n也行15.S1(0,0),S10(10,2),1S0(0,0),(10,2),S1(15,5),(25,7),S1(0,0),(10,2),(15,5),(25,7),S12(6,8),(16,10),(21,13),(31,15),S2(0,0),(6,8),(16,10),(21,13),(31,15)S13(9,1),(15,9),(25,11),
18、(30,14),(40,16),S3(0,0),(6,8),(15,9),(16,10),(21,13),(30,14),(31,15)第八章第八章1 1状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。显示约束：用于规定每个xi 取值的约束条件称为显示约束隐式约束：用于判定一个候选解是否为可行解的条件问题状态：在状态空间树中的每个节点称为一个问题状态解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开
19、始结点就成为一个活结点。未检测的结点称为活结点扩展结点：算法从 x 出发，访问 x 的摸个后继结点y，则 x 被称为扩展结点约束函数：一个约束函数是关于部分向量的函数Bk(x0,x1.xk),它被定义为：如果可以判定 Y 的子树上不含任何答案状态，则Bk(x0,x1.xk)为 false,否则为 true.剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态节点数，他们统称为剪枝函数2 2int count=0;int N=1;bool place(int k,int,I,int*x)For(int j=0,jk,j+)If(xj=i)|(abs
20、(xj-j)=abs(j-k)Return false;Return true;Void nqueens(int k,int n,int*x)For(int i=0;in;i+)if(place(k,i,x)Xk=i;If(k=n-1)For(i=0;in;i+)coutxi;coutendl;count+;Else if(countN)nqueens(k+1,n,x)Void nqueens(int n,int*x)Nqueens(0,n,x);6.状态空间树如下：x0=15,1,82x1=05,2,75x2=115,3,650,0,87x0=00,1,82x1=17,2,75x1=00,2
21、,75x2=00,3,65x3=017,4,53x2=05,3,65x2=117,3,65x3=0 x3=115,4,5317,4,53x3=00,4,53x4=015,5,38x4=017,5,38x4=017,5,38x4=115,5,38x5=015,6,20 x5=1x5=1x5=015,6,20BCx6=1x6=1A可行解：（1，0，0，1，0，1），（0，1，1，0，0，1），（1，0，1，0，0，0，1），（0，0，0，0，1，0，1）7.可行解为：（1）（1，0，0，1，0，1），（0，1，1，0，0，1），（1，0，1，0，0，0，1），（0，0，0，0，1，0，1）（2）（
22、1，0，1），（0，1，0，0，1，1），（1，0，0，0，1，0，1），（0，1，0，1，0，0，1）（3）（1，0，1），（0，1，0，0，1，1），（0，0，1，1，0，1），（0，0，1，1，0，1）第三组的计算时间最少，其次是第二组，最慢的是第一组。D第九章第九章9.1templatevoid JS:GenerateAns(int*x,int&k)Node*ans1=ans;k=0;while(ans1-j0)k+;ans1=ans1-parent;ans1=ans;for(int i=k-1;i=0;i-)xi=ans1-j;ans1=ans1-parent;9.20 1 2 3 4p=3,8,6,4,5total=26U=7d=1,2,3,4,4最优解值=19t=1,1,2,2,1最优解 X=1,2,4(p,d,t)=(8,2,1),(6,3,2),(5,4,1)1 12 23 34 45 57 78 89 9111112121414171718182222