算法设计课程习题答案.doc

算法设计课程习题答案第一章1-1什么是算法？它与计算过程和程序有什么区别？算法是指求解一个问题所需要的具体步骤和方法。它是指令的有限序列。算法有一系列明确定义的基本指令序列所描述的，求解特定问题的过程，它能够对合法的输入，在有限时间内产生所要求的输出，取消有穷性限制则是计算过程；而程序是算法的描述。1-11使用归纳法证明汉诺塔函数的正确性。用数学归纳法证明汉诺塔函数对任何n（即n可以是任何正整数）有解。（1）当盘子数n=1时，只需直接将此盘从A柱搬到C柱即可。（2）现假设n=k时有解，即可以将k个盘子（在不违反规则的情况下）从一个源柱，通过一个中间柱移到目的柱上。（3）现在证明n=k+1时也有解。开始时A柱上的k+1个盘子可以看成由k个盘和最底下的一个最大盘组成。根据归纳假设这k个盘可以（在不违反规则的情况下）通过C柱移到B柱上（在这k个盘的移动过程中，最大盘可以看成不存在）。完成这一大步后，只要将A柱上的最大盘直接搬到C柱上。再根据归纳假设B柱上的这k个盘可以（在不违反规则的情况下）通过A柱移到C柱上。至此证明结束。第二章2-8确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。（1）程序步为画线语句的执行次数为。划线语句的执行次数应该理解为一个整体。（2）画线语句的执行次数为 。（3）画线语句的执行次数为 。（4）当n为奇数时画线语句的执行次数为 ，当n为偶数时画线语句的执行次数为 。 2-11设有和如下所示，分析为、还是。(1) 当时，所以，。可选 ，。对于，即。注意：是f(n)和g(n)的关系。(2) 当 时，所以，。可选 ，。对于 ，即 。（3）因为 ，。当 时，。所以，可选 ，对于，即 。（4）因为，。当时，所以，可选，,对于，即。（5）因为,。当n0时，,所以取, ,对于，即。第四章4-10识别图4-15的图的关节点，画出它们的双连通分图。01732456图G101632457图G2图G1的关节点3、7、1，图G2关节点没有关节点。它们的双连通图如下。01732456图G101632457图G20-1-32-3-43-77-6-5第五章5-11对两组数据（1,1,1,1,1）和（5,5,8,3,4,3,2）执行程序5-12的快速排序，按照 表5-1的格式分别列表表示执行过程。步数012345初始时11111111111211111311111411111排序结果11111步数01234567初始时55834321423358523234585332345854233458552334558排序结果2334558第六章11.由题可得：，所以，最优解为，最大收益为。3.设有带时限的作业排序n=7，(p0，p1,p6)=(3,5,20,18,1,6,30)；（d0,d1,d6）=(1,3,4,3,2,1,2)以此实例为输入的最优解和最大收益。按收益大小递减排序：p6,p2,p3,p5,p1,p0,p4=(30,20,18,6,5,3,1)最优解： (0，0，1，1，0，1，1) 由作业2,3,5,6产生最大收益：748.第七章7-1. Bcost(1,0)=0; Bcost(2,1)=c(1,1)+Bcost(1.0)=5 Bcost(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(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=127-9. char A8=0,x,z,y,z,z,y,x B8=0,z,x,y,y,z,x,z (a) cij （b）sij所以，最长公共字串为 (x,y,z,z)。7-15 , , , , , , ,8-1状态空间：描述问题的各种可能的情况，一种情况对呀状态空间的一个状态。显示约束：用于规定每个xi取值的约束条件称为显示约束隐式约束：用于判定一个候选解是否为可行解的条件问题状态：在状态空间树中的每个节点称为一个问题状态解状态：如果从根到树中某个状态的路径代表一个作为候选解的元组，则该状态为解状态答案状态：如果从根到树中某个状态的路径代表一个作为可行解的元组，则该状态为解状态。活结点：回溯法从开始结点出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个活结点。未检测的结点称为活结点扩展结点：算法从x出发，访问x的摸个后继结点y，则x被称为扩展结点约束函数：一个约束函数是关于部分向量的函数Bk(x0,x1.xk),它被定义为：如果可以判定Y的子树上不含任何答案状态，则Bk(x0,x1.xk)为false,否则为true.剪枝函数：约束函数和限界函数的目的相同，都是为了剪去不必