第一章1-3.最大公约数为1。快1414倍。主要考虑循环次数，程序1-2的while循环体做了10次，程序1-3的while循环体做了14141次(14142-2循环)若考虑其他语句，则没有这么多，可能就601倍。第二章2-8.(1)画线语句的执行次数为logn。匚：'(logn)。划线语句的执行次数应该理解为一格整体。(2)画线语句的执行次数为:::仁门⑴呼12)。匸心3)。i4j4k4(3)(4)画线语句的执行次数为,n。0(..n)。(n1)(n3)当n为奇数时画线语句的执行次数为22-10.(1)当n-1时，5n当n为偶数时画线语句的执行次数为2-8n，2_5n,所以，可选c=5,山=1。对于门一①,225n-8n2=O(n)。22f(n)=5n-8n2乞5n，所以,2222(2)当n-8时，5n-8n•2—5i-n2_4n,所以，可选c=4,n0=8。对于n_让,f(n)=5n2—8n+2^4n2，所以，5n2—8n+2=0(n2)。222(3)由(1)、(2)可知，取c,=4，c2=5，n0=8，当n启n0时，有qn兰5n—8n+c2n，所以5n2-8n2-0(n2)。2-11.(1)当n-3时，logn：：n：：log3n，所以f(n)=20nlogn：：21n,g(n)=nlog3n2n。可21选c=—,n0=3。对于n—n°,f(n)-cg(n)，即f(n)Y)(g(n))。注意：是f(n)和g(n)的关系。22222(2、当n-4时，logn：：n::logn，所以f(n)=n/logn：：n,g(n)二nlogn_n。可选c=1,n0=4。对于n—①,f(n)
P[m])left=m+1;elsereturnS(P)}}5-7.templateintSortableList::BSearch(constT&x,intleft,intright)const{if(left<=right){intm=(right+left)/3;if(xl[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}第五章9.证明：因为该算法在成功搜索的情况下，关键字之间的比较次数至少为|.logn，至多为||logn1。在不成功搜索的情况下，关键字之间的比较次数至少为||logn1，至多为||logn2。所以，算法的最好、最坏情况的时间复杂度为心logn。1假定查找表中任何一个元素的概率是相等的，为一，那么，n不成功搜索的平均时间复杂度为AunElogn,n+1I+nE-2n+nE,成功搜索的平均时间复杂度为Asn1logn。nnn其中，I是二叉判定树的内路径长度，E是外路径长度，并且E=1•2n。11.步数012345初始时111111[11]1[11]OO2[1]11[11]OO3111[11]OO4111[1]1OO排序结果11111OO步数01234567初始时5583432OO1[4233]5[85]OO2[323]45[85]OO3[32]345[85]OO4[2]3345[85]OO523345[5]8OO排序结果2334558OO12.(1)证明：当n=0或n=1或n=2时，程序显然正确。当n=right-left+1>2时，程序执行下面的语句：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)最坏情况发生在序列按递减次序排列。f2n'T(O)=T⑴=0,T(2)=1,T(n)=3T—+1I3丿Iog3-1冒泡排序最坏时间复杂度为On2，队排序最坏时间复杂度为Onlogn，快速排序最坏时间复杂度为门nlogn。所以，该算法不如冒泡排序，堆排序，快速排序。13.templateselect(T&x,intk){if(m>n)swap(m,n);if(m+n0){domid=(left+right)/2;if(a[mid]b[i])right=mid;else{cnt=mid;break;}}while(leftcnt){if(cnt>0){for(j=0;j
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
可得:PlP^PLP4_P5_P^Lf1051576183]lW0,Wi,w2,w3,w4,w5,Wj丿12，3,5，7，1，4，1J所以，最优解为$v12xmls—崎1,0,1,1,1，最大收益为105-156183=55丄。33第八早6-9.普里姆算法。因为图G是一个无向连通图。所以n-1<=m<=n(n-1)/2;0(n)<=m<=0(n2);克鲁斯卡尔对边数较少的带权图有较高的效率，而n1.99n2，此图边数较多，接近完全图，故选用普里姆算法。6-10.T仍是新图的最小代价生成树。证明：假设T不是新图的最小代价生成树，T'是新图的最小代价生成树，那么t(T')>>>>>,'z','y','z','z','y','x'}B[8]={‘0',''z'x',,'>>>>>>y','y','z','>>>)x','z'}(a)c[i][j](b)s[i][j]所以，最长公共字串为(x,y,z,z)。第七章11.voidLCS::CLCS(inti,intj){if(i==0||j==0)return;if(c[i][j]==c[i-1][j-1]+1)CLCS(i-1,j-1);Cout<=c[i][j-1])CLCS(i-1,j);elseCLCS(i,j-1);}12.intLCS::LCSLength(){for(inti=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(intj=1;j<=n;j++)if(x[i]==y[j])c[i][j]=c[i-1][j-1]+1;elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];returnc[m][n];}15.S’={(0,0)},S；二{(10,2)},s0={(0,0),(10,2)},S11={(15,5),(25,7)},S1={(0,0),(10,2),(15,5),(25,7)},{(6,8),(16,10),(21,13),(31,15)},S—{(0,0),(6,8),(16,10),(21,13),(31,15)}&={(9,1),(15,9),(25,11),(30,14),(40,16)},8-1．状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。显示约束：用于规定每个xi取值的约束条件称为显示约束隐式约束：用于判定一个候选解是否为可行解的条件问题状态：在状态空间树中的每个节点称为一个问题状态解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点扩展结点：算法从x出发，访问x的摸个后继结点y,则x被称为扩展结点约束
函
关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函
数：一个约束函数是关于部分向量的函数Bk(x0,x1xk),它被定义为：如果可以判定Y的子树上不含任何答案状态,则Bk(x0,x1xk)为false,否则为true.剪枝函数：约束函数和限界函数的目的相同,都是为了剪去不必要搜索的子树,减少问题求解所需实际生成的状态节点数,他们统称为剪枝函数8-2boolplace(intk,int,I,int*x){For(intj=0,j
本文档为【算法设计与分析C语言描述陈慧南版课后答案】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483