《算法设计与分析c语言描述课后答案计算机NET计算机C++资料.pdf》由会员分享，可在线阅读，更多相关《算法设计与分析c语言描述课后答案计算机NET计算机C++资料.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、15P 1-3.最大公约数为 1。快 1414 倍。主要考虑循环次数，程序 1-2 的 while 循环体做了 10 次，程序 1-3 的 while 循环体做了 14141 次（14142-2循环）若考虑其他语句，则没有这么多，可能就 601 倍。第二章 2-8.（1）画线语句的执行次数为。划线语句的执行次数应该理解为一格整体。（2）画线语句的执行次数为。（3）画线语句的执行次数为。（4）当 n 为奇数时画线语句的执行次数为，当 n 为偶数时画线语句的执行次数为。2-10.（1）当 时，所以，可选，。对于，所以，。（2）当 时，所以，可选，。对于，所以，。（3）由（1）、（2）可知，取，当时
2、，有，所以。2-11.(1)当时，所以，。可选，。对于，即。注意：是f(n)和g(n)的关系。（2）当 时，所以，。可选，。对于，即。（3）因为，。当 时，。所以，可选，对于，即。第二章 2-17.证明：设，则。当 时，。所以，。第五章 5-4.SolutionType DandC1(int left,int right)while(!Small(left,right)&leftright)int m=Divide(left,right);if(xPm)left=m+1;else return S(P)5-7.template int SortableList:BSearch(const T&
3、x,int left,int right)const if(left=right)int m=(right+left)/3;if(xlm)return BSearch(x,m+1,right);else return m;return-1;第五章 9 426351701234567-10 证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为，至多为。在不成功搜索的情况下，关键字之间的比较次数至少为，至多为。所以，算法的最好、最坏情况的时间复杂度为。假定查找表中任何一个元素的概率是相等的，为，那么，不成功搜索的平均时间复杂度为，成功搜索的平均时间复杂度为。可能就倍第二章画线语句的执行次
4、数为划线语句的执行次数应该理解为一格整体画线语句的执行次数为画线语句的执行次数为当为奇数时画线语句的执行次数为当为偶数时画线语句的执行次数为当时所以可选对于所以当时所以可选第二章证明设则当时所以第五章第五章证明因为该算法在成功搜索的情况下关键字之间的比较次数至少为至多为在不成功搜索的情况下关键字之间的比较次数至少为至多为所以算法的最好最坏情况的时间复杂度为假定查找表中任何的内路径长度是外路径长度并且步数初始时排序结果步数初始时排序结果证明当或或时程序显然正确当时程序执行下面的语句首次递归时序列的前的子序列有序当递归执行时使序列的后的子序列有序经过这两次递归排序使原序列的其中，是二叉判定树的内路
5、径长度，是外路径长度，并且。11.步数 0 1 2 3 4 5 初始时 1 1 1 1 1 1 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）证明：当或或时，程序显然正确。当 n=right-left+12时，程序执行下面的语句：int k
6、=(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,righ
7、t-k);使序列的前 2/3 有序。经过三次递归，最终使序列有序。所以，这一排序算法是正确的。（2）最坏情况发生在序列按递减次序排列。，。设，则。冒泡排序最坏时间复杂度为，队排序最坏时间复杂度为，快速排序最坏时间复杂度为。所以，该算法不如冒泡排序，堆排序，快速排序。可能就倍第二章画线语句的执行次数为划线语句的执行次数应该理解为一格整体画线语句的执行次数为画线语句的执行次数为当为奇数时画线语句的执行次数为当为偶数时画线语句的执行次数为当时所以可选对于所以当时所以可选第二章证明设则当时所以第五章第五章证明因为该算法在成功搜索的情况下关键字之间的比较次数至少为至多为在不成功搜索的情况下关键字之间的比
8、较次数至少为至多为所以算法的最好最坏情况的时间复杂度为假定查找表中任何的内路径长度是外路径长度并且步数初始时排序结果步数初始时排序结果证明当或或时程序显然正确当时程序执行下面的语句首次递归时序列的前的子序列有序当递归执行时使序列的后的子序列有序经过这两次递归排序使原序列的 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,right=n-1,cnt=0,j=0,r=0;for(int i=0;i0)do mi
9、d=(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;else tempj=bi;left=0;k-;else for(j=0;jk;j+)可能就倍第二章画线语句的执行次数为划线语句的执行次数应该理解为一格整体画线语句的执行次数为画线语句的执行次数为当为奇数时画线语句的执行次数为当为偶数时画线语句的执行次数为当时所以可选对于所以当时所以可选第二章证明设则当时所以第五章第五章证
10、明因为该算法在成功搜索的情况下关键字之间的比较次数至少为至多为在不成功搜索的情况下关键字之间的比较次数至少为至多为所以算法的最好最坏情况的时间复杂度为假定查找表中任何的内路径长度是外路径长度并且步数初始时排序结果步数初始时排序结果证明当或或时程序显然正确当时程序执行下面的语句首次递归时序列的前的子序列有序当递归执行时使序列的后的子序列有序经过这两次递归排序使原序列的 tempj=ar;r+;left=cnt;k-=cnt;return tempk-1;第六章 1.由题可得：，所以，最优解为，最大收益为。8.17240765625232815169182018783 第六章 6-9.普里姆算法。
11、因为图 G是一个无向连通图。所以 n-1=m=n(n-1)/2;O(n)=m=O(n2);克鲁斯卡尔对边数较少的带权图有较高的效率，而，此图边数较多，接近完全图，故选用普里姆算法。6-10.T 仍是新图的最小代价生成树。证明：假设 T 不是新图的最小代价生成树，T是新图的最小代价生成树，那么 cost(T)cost(T)。有 cost(T)-c(n-1)cost(t)-c(n-1)，即在原图中存在一颗生成树，其代价小于 T的代价，这与题设中T是原图的最小代价生成树矛盾。所以假设不成立。证毕。第七章 可能就倍第二章画线语句的执行次数为划线语句的执行次数应该理解为一格整体画线语句的执行次数为画线语
12、句的执行次数为当为奇数时画线语句的执行次数为当为偶数时画线语句的执行次数为当时所以可选对于所以当时所以可选第二章证明设则当时所以第五章第五章证明因为该算法在成功搜索的情况下关键字之间的比较次数至少为至多为在不成功搜索的情况下关键字之间的比较次数至少为至多为所以算法的最好最坏情况的时间复杂度为假定查找表中任何的内路径长度是外路径长度并且步数初始时排序结果步数初始时排序结果证明当或或时程序显然正确当时程序执行下面的语句首次递归时序列的前的子序列有序当递归执行时使序列的后的子序列有序经过这两次递归排序使原序列的1.Bcost(1,0)=0;Bcost(2,1)=c(1,1)+Bcost=5 Bcos
13、t(2,2)=c(1,2)+Bcost(1,0)=2 Bcost(3,3)=minc(2,3)+Bcost(2,2),c(1,3)+Bcost(2,1)=min6+2,3+5=8 Bcost(3,4)=c(2,4)+Bcost(2,2)=5+2=7 Bcost(3,5)=minc(1,5)+Bcost(2,1),c(2,5)+Bcost(2,2)=min3+5,8+2=8 Bcost(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=9 Bcost(4,7)=minc(3,7)+Bcost(
14、3,3),c(4,7)+Bcost(3,4),c(5,7)+Bcost(3,5)=min4+8,2+7,6+8=9 Bcost(5,8)=minc(6,8)+Bcost(4,6),c(7,8)+Bcost(4,7)=min7+9,3+9=12 2.向后递推的计算过程如上题所示 向前递推过程如下：cost(5,8)=0 cost(4,6)=7,cost(4,7)=3 cost(3,3)=min1+cost(4,6),4+cost(4,7)=7,cost(3,4)=min6+cost(4,6),2+cost(4,7)=5 cost(3,5)=min6+cost(4,6),2+cost(4,7)=5
15、 cost(2,1)=min3+cost(3,3),3+cost(3,5)=8 cost(2,2)=min6+cost(3,3),8+cost(3,5),5+cost(3,4)=10 cost(1,0)=min5+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.char A8=0,x,z,y,z,z,y,x B8=0,z,
16、x,y,y,z,x,z 4433221043332110433221103332211022222110222111101111110000000000 2122212022211220121222101312221022211220131222103133312000000000 (a)cij （b）sij 所以，最长公共字串为(x,y,z,z)。第七章 11.void LCS:CLCS(int i,int j)if(i=0|j=0)return;if(cij=ci-1j-1+1)CLCS(i-1,j-1);可能就倍第二章画线语句的执行次数为划线语句的执行次数应该理解为一格整体画线语句的执行
17、次数为画线语句的执行次数为当为奇数时画线语句的执行次数为当为偶数时画线语句的执行次数为当时所以可选对于所以当时所以可选第二章证明设则当时所以第五章第五章证明因为该算法在成功搜索的情况下关键字之间的比较次数至少为至多为在不成功搜索的情况下关键字之间的比较次数至少为至多为所以算法的最好最坏情况的时间复杂度为假定查找表中任何的内路径长度是外路径长度并且步数初始时排序结果步数初始时排序结果证明当或或时程序显然正确当时程序执行下面的语句首次递归时序列的前的子序列有序当递归执行时使序列的后的子序列有序经过这两次递归排序使原序列的 Cout=cij-1)CLCS(i-1,j);else CLCS(i,j-1
18、);12.int LCS:LCSLength()for(int i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i=0;for(i=1;i=m;i+)for(int j=1;j=cij-1)cij=ci-1j;else cij=cij-1;return cmn;15.)0,0(1S ,)2,10(01S,)2,10(),0,0(0S ,)7,25(),5,15(11S,)7,25(),5,15(),2,10(),0,0(1S ,)15,31(),13,21(),10,16(),8,6(21S,)15,31(),13,21(),10,16(),8,6(),0,0(2S)16,
19、40(),14,30(),11,25(),9,15(),1,9(31S,)15,31(),14,30(),13,21(),10,16(),9,15(),8,6(),0,0(3S 8-1 状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。显示约束：用于规定每个 xi 取值的约束条件称为显示约束 隐式约束：用于判定一个候选解是否为可行解的条件 问题状态：在状态空间树中的每个节点称为一个问题状态 解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态 答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。活结点：回溯法从开始结点出
20、发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点 扩展结点：算法从 x 出发，访问 x 的摸个后继结点 y，则 x 被称为扩展结点 约束函数：一个约束函数是关于部分向量的函数 Bk(x0,x1.xk),它被定义为：如果可以判定 Y的子树上不含任何答案状态，则 Bk(x0,x1.xk)为 false,否则为 true.剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态节点数，他们统称为剪枝函数 可能就倍第二章画线语句的执行次数为划线语句的执行次数应该理解为一格整体画线语句的执行次数为画线语句的执行次数为当为
21、奇数时画线语句的执行次数为当为偶数时画线语句的执行次数为当时所以可选对于所以当时所以可选第二章证明设则当时所以第五章第五章证明因为该算法在成功搜索的情况下关键字之间的比较次数至少为至多为在不成功搜索的情况下关键字之间的比较次数至少为至多为所以算法的最好最坏情况的时间复杂度为假定查找表中任何的内路径长度是外路径长度并且步数初始时排序结果步数初始时排序结果证明当或或时程序显然正确当时程序执行下面的语句首次递归时序列的前的子序列有序当递归执行时使序列的后的子序列有序经过这两次递归排序使原序列的 8-2 bool place(int k,int,I,int*x)For(int j=0,jk,j+)If
22、(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-1 For(i=0;in;i+)coutxiendl;Return;Else nqueens(k+1,n,x)Void nqueens(int n,int*x)Nqueens(0,n,x);可能就倍第二章画线语句的执行次数为划线语句的执行次数应该理解为一格整体画线语句的执行次数为画线语句的执行次数为当为奇数时画线语句的执行次数为当为偶数时画线语句的执行次数为当时所以可选对于所以当时所以可选第二章证明设则当时所以第五章第五章证明因为该算法在成功搜索的情况下关键字之间的比较次数至少为至多为在不成功搜索的情况下关键字之间的比较次数至少为至多为所以算法的最好最坏情况的时间复杂度为假定查找表中任何的内路径长度是外路径长度并且步数初始时排序结果步数初始时排序结果证明当或或时程序显然正确当时程序执行下面的语句首次递归时序列的前的子序列有序当递归执行时使序列的后的子序列有序经过这两次递归排序使原序列的