算法设计技巧与分析答案

1、算法设计技巧与分析参考答案第1章算 法分析基本概念 1.1 (a)6 (b)5 (c)6 (d)6 1.4算法执 行了 7+6+5+4+3+2+仁28次比较 45 33 24 45 12 12 24 12 1233 24 45 45 12 24 1212 12 24 45 45 33 24 1212 12 12 45 45 3324 2412 2412 12 45 33 45 2412 12 12 24 24 33 45 4512 1212 24 24 33 45 4512 12 12 24 24 33 45 451.5 算法MODSELECTIONSOR执行的元素赋值的最少次数是0,元素已按

2、非降序排列的时候达到最小值。(b)算法MODSELECTIONSORT执行的元素赋值的最多3n(n 1)次数是,元素已按非升序排列的时候达到最小值。21.74 3 12 5 6 7 2 91 次 3 41 次 3 4 12 2 次 3 4 5 123 4 5 6 12 2 次 7 123 4 5 6 2 次 2 3 4 5 6 7 12 6 次 7 923 4 5 6 12 2次由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。1.11 比较 9 次 2 4 5 7 8 11 12 13 1517 19 比较为6次 2 4 5 8 11 13 17 19 7 12 15 比较为

3、3次，2 5 17 19 4 8 11 13 7 12 15 2次，1 次 2 17 5 19 11 13 4 8 12 15 7 比较均为1次，共5次 2 17 19 5 13 11 4 8 15 12 7由上图可以 得出比较次数为 5+6+6+9=26次。1.13 FTF,TTT,FTF,TFF,FTF 1.1执!(行该算法，元素比较的最少次数是n-1。元素已按非降序排列时候达到最小值。(b)执行该算法，元素比较的最多次数是。元素已2按非升序排列时候达到最大值。 (C)执行该算法，元素赋值的最少次数是 0。元素已按非降序排列时候达到最小值。(d)执行该算法，元素赋值的最多 次数是。元素已2

4、按非升序排列时候达到 最大值。(e)用0符号和符号表示算法 BUBBLESORT的运行时 R 间:， 2(f)不可以用符号来表示算法的运行时间：是用来表示算法的精确阶的，而本算法运行时间由线性到平方 排列，因此不能用这一符号表示。 1.27 不能用关系来比较和增长的阶。22 100nn2n1 /22 不是的，即不能用关系来比较和增长 222 o(100n)1OOnn 的阶。 1.32(a)当n为2的幂时，第六步执行的最大次数是：时，kk In 2J 2nn(b)由(a)可以得到：当每一次循环j都为2的幂时，第六步执 行的次数最大，kk33则当(其中取整)时，22nnkm log(3 1) nl

5、ogfn l)ii li l(c)用符号32 37 45 5112 25 17 19 51 32 45 18 22 37 1512 17 19 25 32 5132 37 45 5112 25 17 19 51 32 45 18 22 37 1512 17 19 25 32 510000表示的算法的时间复杂性是 O(nlogn) kk已 证明n=2的情况，下面证明 n=2+1的情 况：因为有所以n=2+1时，第六步执行的 最大次数仍是n log n。(d)用符号表示的算法的时间复杂性是。当满足取整为奇数时，算法执行的次数是次，其他情况算法执行次数均大于。n(e)O更适合表示算法的时间复杂性。因

6、为本 算法时间复杂性从到，而是表示精确阶的。1.38对个数进行排序。n第5章归纳法 5.3 (本题不仅有以下一个答案)1.max(n)过程：max(i) if n=1 return a1 t=max(i-1) if ai-1t return ai-1 else return t end if 5.6 最多次数：0川1 qn)1)価1)川2 nn(n 1)C(n) j 2j 1最少次数:01 C(n) C(n 1 12 C(n)=n-1 5.7参考例5.1 5.14 (a)不稳定，例如：12 45 452412 45 45 2412 24 45 4512 24 45 45 可见SELECTION

7、SOR中相等元素的序在排序后改变。(b)(c)(d)(f)稳定 5.17 (a)利 用10 取，x 3P(3) P(3) P(3) P(3) P(3) P(3)543210PP(3) 3*P(3) 1 112 P3) 3*P(3) 2 338 P(3) 3* P(3) 5 10193243545.18(a)p即)p(2 ,2p) (2p,l)222y 4*2 y 2 4 y 1*2 y 1 第 6 章分治6.3 输入：A1,2,n输出：max,min 1for i=1 to mid 2. j=highi 3. if aiaj, then exchange ai,aj 4.end for 5.f

8、or i=low to mid 6. if ai+1valow, then exchange alow,ai+1 7. end for 8.for i=mid+1 to high 9. if ai+1ahigh, then exchange ahigh,ai+1 10.end for 6.5 输入：一个整数 数组 A1,2,小输出：sum 1.if high-low=1 then 2. sum=alow+ahigh 3. else 4. mid=(low+high)/2 5 sum1=sum(low,mid) 6 sum2=sum(mid+1,high) 7. sum=sum1+sum2end

9、 ifreturn sum算法需要的工作空间为3 6.10.32 15 14 15 11 17 25 5111141515 17 25 32 513215141511 17 25 5114 15 15 32 11 17 25 5132 15 14 15 11 17 25 5115 32 14 15 11 17 25 5132 15 14 15 11 17 25 5132 15 14 15 1117 25 5112 25 17 19 51 32 45 18 22 37 1512 15 17 18 19 22 2515 18 22 37 4512 25 17 19 51 32 45 18 22 3

10、7 1512 17 25 19 3215 18 22 37 4512 25 17 19 51 32 45 18 22 37 1512 17 25 19 3251 18 22 4515 3712 2517 19 51 32 45 18 22 37 151225 17 1951 32 18 4522 37 151225 19 51 45 1812 25 19 5145186.3127 13 31 18 45 16 17 5327 13 31 18 45 16 17 5327 13 31 1845 16 17 5313 18 27 31 45 16 17 532713 18 3145 16 17 5

11、327 13 18 16 45 31 17 5327 13 18 161731 45 5317 13 18 1627 31 45 53彩色代表i,j所指的数字j总在i前6.3623 32 27 18 45 11 63 12 19 16 25 52 14 14 11 1218 19 1623 3245 27 25 52 63 14 18 11 12 19 16 12 11 14 18 19 16 12 11 11 1211 1118 19 16 16 18 19 16 16 19 19 32 45 27 25 52 6325 27 32 45 52 63 25 27 25 27 27 27 45

12、 52 63 45 52 63 5263 52 6363 63 11 12 14 16 18 19 23 25 27 32 45 52 636.42 Quicksort 不是稳定的。6.43 bcefg 均为适应的，a、h不是适应的。第7章动态规划7.1 ,算法BOTTOMUPSORT 75字符串A=” xzyzzy和”=” zxyyzxZ勺最长公共子序列长度为4,共有6个最长公共子序列，分别是：zyyxzyzzzyzxxyyxxyzzxyzx 7.9C1,5=C1,1+C2,5+r1*r2*r =307C1,5=C1,2+C3,5+r1*r3*r =252C1,5=C1,3+C4,5+r1*

13、r4*r6=372C1,5=C1,4+C5,5+r1*r5*r6=260 所以最优括号表达 TOC o 1-5 h z 式 为(M1M2)(M3M4)M5)7ij minD讥D1J D1000434021620067109 D 144021820DiJ minDiJ,DL2 D2J2111067109 D 244021820DiJ minDiJLDL3 D训 3222344021620129 12 9 122 4 2 4129 12 9 122 4 2 4Di,j minDijLDt4 D4j43 3 34340216207.210 1 2 3 4 5 6 7 8 9

14、 10 11 0 0 00 0 0 0 0 0 0 0 0 0 1 0 0 3 3 3 3 3 3 3 3 3 3 2 00 3 4 4 7 7 7 7 7 7 7 3 0 0 3 4 4 7 7 8 9 9 12 12 4 0 0 3 4 4 7 7 8 10 11 12 147.23 当物品体积为负值时，运行算法会发生溢出错误。第八章贪心算法 &121 s a 23 t由算法从s到t要选择先到a然后到t,其 结果为4，而从s到t距离为2，所以探索 不总是产生从s到t的距离8.1312 9 12 2 4 5 4 316 4 15 35 138 91255433416164415153535 13134129 20:8 16 129 122 49 122 455 28431 64 31 644 15153 5133 54 13134 138 12 169 122 454 3281 6415 3134 138.23 （共有4棵最小生成树，此处仅举一例） TOC o 1-5 h z 1 3 51 3