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

1、第一章 15P1-3. 最大公约数为 1。快 1414 倍。主要考虑循环次数，程序 1-2 的 while 循环体做了 10 次，程序 1-3 的 while 循环体做了 14141 次（14142-2 循环）若考虑其他语句，则没有这么多，可能就 601 倍。第二章 32P2-8.（1）画线语句的执行次数为 。 。划线语句的执行次数应该理解为一格整体。logn(l)（2）画线语句的执行次数为 。 。1126jniijk3()n（3）画线语句的执行次数为 。 。()（4）当 n 为奇数时画线语句的执行次数为 ，1(3)4n当 n 为偶数时画线语句的执行次数为 。 。 22()n2-10.（1）

2、当 时， ，所以，可选 ， 。对于 ，122585n5c01n0n，所以， 。22()58fn()n（2） 当 时， ，所以，可选 ， 。对于 ，2244c080，所以， 。22()4fn58()（3） 由（1） 、 （2）可知，取 ， ， ，当 时，有 ，所1c20n0n2215cncn以 。258()n2-11. (1) 当 时， ，所以 ， 。可33logln()2logf3()log2选 ， 。对于 ， ，即 。注意：是 f(n)和 g(n)的关系。12c00()fcgn()n（2） 当 时， ，所以 ， 。可选 4n2ll 22()/lf 2l， 。对于 ， ，即 。1c00n()f

3、c()g（3）因为 ， 。当 时，logl(og)()nf/lol2n4n， 。所以，可选 ， ，对于 ， ，log()nf()log2n1c04n0n()fcgn即 。第二章2-17. 证明：设 ，则 。2inlognlT2log2lognnT2logln22lTn2322loglog2nn3l4lT322lognn l4212kTknk1logiini4l121i in2l3lognlogln当 时， 。所以， 。22T2lTnn第五章5-4. SolutionType DandC1(int left,int right)while(!Small(left,right)else retur

4、n S(P)5-7. template int SortableList:BSearch(const Telse return m;return -1;第五章942 63 51 70 1 2 3 4 5 6 7- 1 0证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为 ，至多为 。在lognlog1n不成功搜索的情况下，关键字之间的比较次数至少为 ，至多为 。所以，算法的最log1n2好、最坏情况的时间复杂度为 。logn假定查找表中任何一个元素的概率是相等的，为 ，那么，不成功搜索的平均时间复杂度为 ，log1uEAnn成功搜索的平均时间复杂度为 。21logsI n其中， 是

5、二叉判定树的内路径长度， 是外路径长度，并且 。I 2EI11.步数 0 1 2 3 4 5初始时 1 1 1 1 11 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 1 4 1 1 1 1 1 排序结果 1 1 1 1 1 步数 0 1 2 3 4 5 6 7初始时 5 5 8 3 4 3 2 1 4 2 3 3 5 8 5 2 3 2 3 4 5 8 5 3 3 2 3 4 5 8 5 4 2 3 3 4 5 8 5 5 2 3 3 4 5 5 8 排序结果 2 3 3 4 5 5 8 12.（1）证明：当 或 或 时，程序显然正确。0n12n当 n=right-left

6、+12 时，程序执行下面的语句：int k=(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 的序列并不一定是有序的。再次执行

7、StoogeSort(left,right-k);使序列的前 2/3 有序。经过三次递归，最终使序列有序。所以，这一排序算法是正确的。（2）最坏情况发生在序列按递减次序排列。， ， 。0121231n设 ，则 。32inlogn413194931n 1223ii iinii312ilog312nlog31logn冒泡排序最坏时间复杂度为 ，队排序最坏时间复杂度为 ，快速排序最坏时间复杂度为2nlogn。所以，该算法不如冒泡排序，堆排序，快速排序。logn13. template select (Tif(m+n0)domid=(left+right)/2;if(amidbi) right=mid

8、;else cnt=mid; break;while(leftcnt)if(cnt0)for(j=0;j=cij-1) CLCS (i-1,j);else CLCS (i,j-1);12. int LCS:LCSLength()for ( int i =1; i=cij-1) cij=ci-1j;else cij=cij-1;return cmn;15. , ,)0(1S)210(S, ,)75(, ,)75(),(,1 )153(,2),106(821S,32,106802S )640(95,3)(4,0),()9(,),(38-1状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一

9、个状态。显示约束：用于规定每个 xi 取值的约束条件称为显示约束隐式约束：用于判定一个候选解是否为可行解的条件问题状态：在状态空间树中的每个节点称为一个问题状态解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点扩展结点：算法从 x 出发，访问 x 的摸个后继结点 y，则 x 被称为扩展结点约束函数：一个约束函数是关于部分向量的函数 Bk(x0,x1.xk),它被定义为：如果

10、可以判定 Y 的子树上不含任何答案状态，则 Bk(x0,x1.xk)为 false,否则为 true.剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态节点数，他们统称为剪枝函数8-2bool place(int k,int ,I,int*x)For(int j=0,jk,j+)If(xj=i)|(abs(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-1For(i=0;in;i+)coutxiendl;Return;Else nqueens(k+1,n,x) Void nqueens(int n,int *x)Nqueens(0,n,x);