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

第一章1-3 .最大公约数为1。 快1414倍。主要考虑循环次数，程序1-2的while循环体进行了10次，程序1-3的while循环体进行了14141次(14142-2循环)想想别的话，没有这么多的话可能会加倍。第二章2-8.(1)格线文件的执行次数为。 的双曲馀弦值。 评分句的执行次数应理解为整个格。(2)格线文件的执行次数为。 的双曲馀弦值。(3)格线文件的执行次数为。 的双曲馀弦值。(4)n为奇数时格线文件的执行次数为n为偶数时格线文件的执行次数为。 的双曲馀弦值。2-10.(1)当时，其选择如下： 是的，所以。(2)当时，所以可以选择。 是的，所以。(3)由(1)、(2)可知，2-11. (1)因为当时。 选项。 是的，也就是说。 注意： f(n )和g(n )的关系。(2)因为当时。 选项。 是的，也就是说。(3)因为。 当时，所以选择，是的。第二章2-17 .证明：于是。当时。 所以。第五章5-4 .解决方案类型与c1(入左，入右)装模作样while (！ 小(左，右)左 m )左=m 1；else return S(P )以下称为以下称为5-7 .模板intsortablelist :3360 bsearch (const tx，int left，int right) const装模作样if (左=右)装模作样int m=(right left)/3；if (xlm) return BSearch(x、m 1、right )else return m；以下称为return -1；以下称为第五章9.9证明：该算法在检索成功时，关键词之间的比较次数至少应该是最多的。 如果检索失败，关键字之间的比较次数至少最多。 因此，算法的最优、最差情况的时间复杂度如下。假设检索表元素的概率相等搜索失败的平均时间复杂度成功搜索的平均时间复杂度如下：其中，是二叉判定树的内路径长度，是外路径长度，并且。11.步数012345初期11111111 )111 )8211111 )8311111 )84111118排序结果111118步数01234567初期5583432814233 )585 )82323 )4585 )8332 )34585 )842334585 )8523345588排序结果2334558812.(1)证明：或者，程序显然是正确的。如果n=right-left 12，程序执行以下语句int k=(right-left 1)/3；stoogesort (左，右- k )stoogesort (左k，右)stoogesort (左，右- k )初次递归StoogeSort(left，right-k )时序的前2/3的子序列有序。对递归运行StoogeSort(left k，right )的时间序列的最后2/3个子序列进行排序，通过这两次递归排序，使得原始序列的最后1/3的位置在整个序列中是最大的数量，即，序列的最后1/3的位置的数量大于最前2/3的数量对再次运行StoogeSort(left，right-k )的序列的前2/3进行排序。经过三次递归，最终排序了序列。因此，该排序算法是正确的。(2)最坏的情况下顺序按降序排列。、是的，先生。泡沫排名的最差时间复杂度是，团队排名的最差时间复杂度是，高速排名的最差时间复杂度是。 因此，该算法不如泡排序、堆排序和快速排序。13 .模板select (Tx，int k )装模作样if(mn) swap(m，n )if(m n0 )装模作样do装模作样mid=(左右)/2；if(amidbi) right=mid；else cnt=mid； break； 以下称为 while (左CNT )装模作样if(cnt0)装模作样for(j=0； j=cij-1) CLCS (i-1，j )else CLCS (i，j-1 )以下称为12.intlcs:3360lcsnelength ()装模作样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=n； j )if (x I =y j ) c I j =c I-1 j-1 1；else if (c I-1 j =c I j-1 ) c I j =c I-1 j ；else cij=cij-1；return cmn；以下称为15 .、，8-1。状态空间：描述了问题的各种可能情况，一种情况是正确的状态空间的一种状态。显示约束条件：按xi取值的约束条件称为显示约束条件隐式约束：确定候选解是否为可能解的条件问题状态：状态空间树中的每个节点称为问题状态解状态：在从根到树中的状态的路径表示成为解候补的元组的情况下，该状态成为解状态答案状态：从根到树内状态的路径表示可执行解的元组时，其状态为解除状态。活节点：回溯法从开始节点以深度优先搜索解空间全体，该开始节点成为活节点。 未检测到的节点称为活动节点扩展节点：算法从x访问x的下一个节点y，x称为扩展节点。约束函数：一个约束函数是对于部分向量的函数Bk(x0，x1. xk )，如果能确定y子树不包括任何答案，则Bk(x0，x1. xk )定义为假，否则定义为真。剪枝