《《计算机算法基础》课后答案.pdf》由会员分享，可在线阅读，更多相关《《计算机算法基础》课后答案.pdf（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机算法分析 习题课第四章：2、3、5、6、10、11、23 P99-2 在下列情况下求解 4.1节的递归关系式 T(n)=()2(/2)()gnnTnfn?足够小否则当 g(n)=O(1)和f(n)=O(n)；g(n)=O(1)和f(n)=O(1)。P99-2递推表达式设n=2k则:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2 T(2k-2)+f(2k-1)+f(2k)=22T(2k-2)+21f(2k-1)+f(2k)=2kT(1)+2k-1f(2)+2k-2f(22)+20f(2k)=2kg(n)+2k-1f(2)+2k-2f(22)+20f(2k)g(n)=O(1)和f
2、(n)=O(n)当g(n)=O(1)和f(n)=O(n)时不妨设 g(n)=a，f(n)=bn，则：T(n)=T(2k)=2ka+2k-1*2b+2k-2*22b+20*2kb=2ka+kb2k=an+bnlog2n=O(nlog2n)g(n)=O(1)和f(n)=O(1)当g(n)=O(1)和f(n)=O(1)时，不妨设 g(n)=c，f(n)=d，则：T(n)=T(2k)=c2k+2k-1d+2k-2d+20d=c2k+d(2k-1)=(c+d)n-d=O(n)P99-3 根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。Procedure BINSRCH(A,low,hig
3、h,x,j)integer mid if low highthen mid?(low+high)/2?if x=A(mid)then jmid;endif if xA(mid)then BINSRCH(A,mid+1,high,x,j);endif if xA(mid)then BINSRCH(A,low,mid-1,x,j);endif else j0;endif end BINSRCH P99-5 作一个“三分”检索算法，它首先检查 n/3处的元素是否等于某个 x的值，然后检查 2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的 1/3。分析此算法在各种情况下的计算复杂度。Proc
4、edure ThriSearch(A,x,n,j)integer low,high,p1,p2 low 1;high n while low highdo p1?(high+2low)/3?p2?(2high+low)/3?case:x=A(p1):j p1;return:x=A(p2):j p2;return:xA(p2):low p2+1:else:low p1+1;highp2-1 end case repeat j0 endThriSearch 实例运行 1,2,3,4,5,6,7,8,9 361 时间复杂度成功:O(1),O(log3(n),O(log3(n)最好，平均，最坏失败:O
5、(log3(n),O(log3(n),O(log3(n)最好，平均，最坏P99-6 对于含有 n个内部结点的二元树，证明E=I+2n 其中，E，I分别为外部和内部路径长度。证明：数学归纳法当n=1时，易知 E=2，I=0，所以 E=I+2n 成立；假设nk(k0)时，E=I+2n 成立；此时新树内部结点为 k个，则满足：Ek=Ik+2k（1）考察原树的外部路径长度和内部路径长度：Ek+1=Ek-h+2(h+1)（2）Ik+1=Ik+h（3）综合（1）（2）（3）式：Ek+1=Ik+2k+h+2=Ik+1-h+2k+h+2=Ik+1+2(k+1)故命题成立。P99-10 过程MERGESORT
6、的最坏情况时间是 O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是(nlogn)吗？最好情况：对有序文件进行排序分析归并的次数不会发生变化-log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小需要比较 n-1次最好情况一个序列完全大于/小于另一个序列比较n/2次差异都是线性的，不改变复杂性的阶最好情况也是 nlog(n),平均复杂度 nlog(n)。P99-11 写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。见数据结构-第九章P238 算法MPass（R，n，1engthX）MP1 初始化 i1 MP2 合并相邻的两个长度为 len
7、gth的子文件 WHILE i n 2*length+1 DO（Merge（R，i，ilength l，i2*length 1X）.ii2*length）MP3 处理余留的长度小于 2*length的子文件 IF i+length 1 0，要用的处理时间 ti0，限期di ti.解：根据 pi 的非增排序得到（p7,p3,p4,p6,p2,p1,p5）=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)，按照算法 3.5生成的解为：1.J(1)=7(2),2.J(1)=7(2),J(2)=3(4)；3.J(1)=7(2),J(2)=4(3),J(3)=3(4)；4
8、.J(1)=6(1),J(2)=7(2),J(3)=4(3),J(4)=3(4)；证明即使作业有不同的处理时间定理5.3亦真。这里，假定作业 i的效益 pi0，要用的处理时间 ti0，限期di ti.(P106)定理5.3:设J是K个作业的集合,=i1i2 ik 是J中作业的一种排序,它使得 di1di2dik.J是一个可行解,当且仅当 J中的作业可以按照的次序又不违反任何一个期限的情况下来处理.证明：显然即使ti0（di ti），如果 J 中的作业可以按照 的次序而又不违反任何一个期限来处理，即对次序中的任一个作业k，应满足 dk=kjjt1，则 J 就是一个可行解。下面证明如果J 是可行解
9、，=i1i2 ik 使得 J 中的作业可以按照di1 di2 din 序列排列而又不违反任何一个期限。J 是可行解，则必存在=r1r2 rn，使得对任意的 rk，都有 dk=kjjt1，我们设是按照 di1di2din排列的作业序列。假设 ，那么令 a 是使 raia 的最小下标，设rb=ia，显然 ba，在中将 ra 与 rb 相交换，因为 drbdra，显然 ra 和 rb 可以按期完成作业，我们还要证明 ra 和 rb 之间的作业也能按期完成。因为 drbdra，而显然二者之间的所有作业rt，都有 drbdrt，又由于 是可行解，所以 1btbkrrktdd=，所以作业 ra 和 rb
10、交换后，仍满足 1ttkrktd=，即所有作业可依新产生的排列=s1s2 sn的次序处理而不违反任何一个期限，连续使用这种方法，就可转换成 且不违反任何一个期限，定理得证。P123-9 对于 5.3节的作业排序问题证明：当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解；如果J中的作业 I还没分配处理时间，则将它分配在时间片a-1，a处理，其中 a是使得 1rdi的最大整数 r，且时间片 a-1，a是空的。仿照例 5.4的格式，在习题 5.8的所提供的数据集上执行算法5.5。易证如果 J中的作业能按上述规则处理，显然J是可行解；如果J是可行解，根据定理 5.3可知，J中的作业根据时间
11、期限的非降次序排列，得到 i1i2 ik in，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任意作业ik，如果它的时间期限是 dk，且时间片 dk-1,dk 是空的，则分配之；若时间片 dk-1，dk 非空，则向前找最大的非空 r-1,r 时间片，1rdk因为J是可行解，所以一定可以找到如此时间片。故命题得证。n=7(p1,p7)=(3,5,20,18,1,6,30)(d1,d7)=(1,3,4,3,2,1,2)(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)b=minn,maxd(i)=min7,4 =
12、4 P123-11 证明如果一棵树的所有内部节点的度都为k，则外部节点数 n满足n mod(k-1)=1.证明对于满足 n mod(k-1)=1 的正整数 n，存在一棵具有 n个外部节点的 k元树T(在一棵 k元树中，每个节点的度至多为k)。进而证明 T中所有内部节点的度为 k.证明：设某棵树内部节点的个数是i，外部结点的个数是 n，边的条数是 e，则有e=i+n-1 ik=e?ik=i+n-1?(k-1)i=n-1?n mod(k-1)=1 P123-12 证明如果 n mod(k-1)=1，则在定理 5.4后面所描述的贪心规则对于所有的（q1,q2,qn）生成一棵最优的 k元归并树。(P1
13、11)当（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。通过数学归纳法证明：对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于（q1,q2,qm），其中 m=(k-1)s+1(s 0)，都生成一棵最优树，则只需证明对于(q1,q2,qn)，其中 n=(k-1)(s+1)+1，也能生成最优树即可。不失一般性，假定 q1q2qn，且q1,q2,qk 是算法所找到的k棵树的WEIGHT 信息段的值。于是q1,q2,qk可生成子树 T，设T是一棵对于（q1,q2,qn）的最优 k元归并树。设 P是距离
14、根最远的一个内部结点。如果 P的k个儿子不是 q1,q2,qk，则可以用q1,q2,qk和P现在的儿子进行交换，这样不增加 T 的带权外部路径长度。因此T也是一棵最优归并树中的子树。于是在T 中如果用其权为q1+q2+qk 的一个外部结点来代换 T，则所生成的树 T是关于(T,qk+1,qn)的一棵最优归并树。由归纳假设，在使用其权为q1+q2+qk 的那个外部结点代换了 T以后，过程 TREE转化成去求取一棵关于(T,qk+1,qn)的最优归并树。因此 TREE生成一棵关于(q1,q2,qn)的最优归并树。计算机算法分析 习题课第六章 1 2 3 4 5 6 8 13 17 动态规划1.多阶
15、段过程2.满足最优性原理3.建立递推关系式P151-1 递推关系式（6.8）对右图成立吗？为什么？递推关系式（6.8）为什么对于含有负长度环的图不能成立？?解：?成立，不包含负长度环?可以使节点间的长度任意小。P151-2 修改过程 ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？回忆算法：P127 算法6.1 P131 算法6.3 P127 算法6.1 D(i,j)/D(j):从节点j到汇点t的最优路径中下一个节点，即最优路径中j的后继节点。算法6.1在计算COST(j)的同时也计算了 D(j)37行计算出 D(j)之后，即可计算最短路径。91
16、1行P131 算法6.3 对矩阵进行初始化，每个元素赋值为边的长度（如果没边则赋值成 MAX）15行迭代计算最短路径长度612行仿照6.1，在每次计算最短路径的时候计算出D(j)再通过 D(j)就可以表示出最短路径for k1 to n do/迭代计算for i1 to n do for j1 to n do if A(i,j)A(i,k)+A(k,j)then A(i,j)A(i,k)+A(k,j)Path(i,j)Path(i,k)endif repeat repeat repeat for i1 to n do/输出最优路径for j1 to n do print(“thepath of
17、 i to j is”i)kpath(i,j)while k0 do print(k)kpath(k,j)repeat repeat repeat endShortestPath 分析时间复杂度第一个循环：O(n2)第一个循环：O(n3)第一个循环：O(n2)空间复杂度Cost(n,n)A(n,n)Path(n,n)O(n2)P151-3 对于标识符集（a1,a2,a3,a4）=（end,goto,print,stop），已知成功检索概率为 P(1)=1/20,P(2)=1/5,P(3)=1/10,P(4)=1/20，不成功检索概率为Q(0)=1/5,Q(1)=1/10,Q(2)=1/5,Q(
18、3)=1/20,Q(4)=1/20，用算法OBST对其计算 W(i,j)，R(i,j)和C(i,j)（0i,j4）。P136 算法6.5 P（i）P(1)=1/20,P(2)=1/5,P(3)=1/10,P(4)=1/20 Q（i）Q(0)=1/5,Q(1)=1/10,Q(2)=1/5,Q(3)=1/20,Q(4)=1/20 P（i）P(1)=1,P(2)=4,P(3)=2,P(4)=1 Q（i）Q(0)=4,Q(1)=2,Q(2)=4,Q(3)=1,Q(4)=1 P151-4 证明算法 OBST 的计算时间是 O(n2)。在已知根 R(i,j)，0i j4的情况下写一个构造最优二分检索树T的
19、算法。证明这样的树能在O(n)时间内构造出来。将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：20(1,)(,1)1)nnmmiRijRij-=+-+=20(1,)(,1)1)nnmmiRiimRiim-=+-+-+=2(1,)(0,1)1)nmRnmnRmnm=-+-+-+O(n2)Procedure BuildTree(m,n,R,Root)integer R(n,n),k TreeNodeRoot,LR,RR kR(m,n)if k 0 then data(Root)k,BuileTree(m,k-1,R,LR),BuileTree(k,n,R,RR)left(Root)LR
20、,right(Root)RR else data(Root)m,left(Root)null,right(Root)null,endif endBuildTree 时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为 O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。P151-5 由于我们通常只知道成功检索和不成功检索概率的近似值，因此，若能在较短的时间内找出几乎是最优的二分检索树，也是一件很有意义的工作。所谓 几乎是最优的二分检索树，就是对于给定的 P和Q，该树的成本（由（6.9）式计算
21、）几乎最小。已经证明，由以下方法获得这种检索树的算法可以有O(nlogn)的时间复杂度，选取这样的k为根，它使|W(0,k-1)-W(k,n)|尽可能地小。重复以上步骤去找这根的左、右子树。对于题 6.3的数据，用上述方法找出一棵这样的二分检索树。它的成本是什么？用SPAKS 写一个实现上述方法的算法，你的算法的计算时间为O(nlogn)吗？解：矩阵 W如下所示，相应的 k从1到4得式如下：|W(0,0)-W(1,4)|=11,|W(0,1)-W(2,4)|=2,|W(0,2)-W(3,4)|=12,|W(0,3)-W(4,4)|=17 所以该树的根是 T(0,4)=2，依次计算得到 T(0,
22、1)=1，T(2,4)=3，T(3,4)=4 总体成本是 4+2*（2+1）+2*（4+2+4）+3*（1+1+1）=39 Procedure CreateTree(m,n,root,w)integer r,k,root(n,n),w(n,n)real ww,min if m=n then root(m,n)0 else if m=n-1 then root(m,n)n else for k m+1 to n do ww|w(m,k-1)-w(k,n)|if ww min then minww,r kendif repeat root(m,n)r Call CreateTree(m,r-1)C
23、all CreateTree(r,n)endif End BuildTree 时间复杂性最好和平均的情况应该是O(nlogn)，但最坏的情况是O(n2)P151-6 设(w1,w2,w3,w4)=(10,15,6,9),(p1,p2,p3,p4)=(2,5,8,1)。生成每个 fi阶跃点的序偶集合 Si，0i4。P151-8 给出一个使得 DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i,0 in。还要求对 n的任意取值都适用。取(P1,P2,Pi,)=(W1,W2,Wi,)=(20,21,2i-1,)P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明
24、不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。P152-13 假定两个仓库 W1和W2都存有同一种货物，其库存量分别为r1和r2。想要将其全部发往 n个目的地 D1,D2,Dn.设发往 Dj的货物为 dj，因此r1+r2=dj.如果由仓库 Wi发送量为 xij 的货物到目的地 Dj的花费为Cij，那么仓库问题就是求各个仓库应给每个目的地发多少货才使总的花费最小。即要求出这些非负整数xij，1i2,1jn，它使得x1j+x2j=dj,1jn，并且使ijcij(xij)取最小值。假设当 W1有x的库存且按最优方式全部发往目的地D1,D2,Di时所需的花费为gi(x)(
25、W2的库存为 dj-x)。于是此仓库问题的最优总花费是gn(r1).P128-13 求gi(x)的递推关系式写一个算法求解这个递推关系式并要能得到xij的决策值得最优序列，1i2,1jn.1112110min,()()()()miniiiiiiiiixxdiigxcxcdxgxdxd-1121()()()iiiiiiigxcxcdxxd=+-P152-17 最优性原理并不总是对可以将其解看成是一系列决策结果的所有问题成立。找两个最优性原理不成立的例子，并说明对这两个问题最优性原理为什么不成立。多段图问题：路径和改为路径乘积并允许出现负数计算机算法分析 习题课第八章：1、3、8、9 P215-1
26、 修改算法 8.1和8.2，使它们只求出问题的一个解而不是问题的全部解算法8.1 procedure BACKTRACK(n)integerk,n;localX(1:n)k 1 whilek0 do if还剩有没检验过的 X(k)使得X(k)T(X(1),X(k-1)and Bk(X(1),X(k)=true then if(X(1),X(k)是一条抵达一答案节点的路径then print(X(1),X(k)return endif k k 1 else kk 1 endif repeat end BACKTRACK 算法8.2 procedure RBACKTRACK(k)globaln,X
27、(1:n)for满足下式的每个 X(k)X(k)T(X(1),X(k-1)and Bk(X(1),X(k)=true do if(X(1),X(k)是一条抵达一答案结点的路径then print(X(1),X(k)return endif callRBACKTRACK(k+1)repeat end RBACKTRACK P215-3 重新定义过程 PLACE(k)，使它的返回值或者是第k个皇后可以放置于其上的合法列号，或者是一个非法值，这样可以提高一些NQUEENS 的效率，按以上策略重写这两个过程。算法8.4 procedure PLACE(k)global X(1:K);integer i,k j-1 while X(k)n do i 1 while i0 do X(k)X(k)+1 if PLACE(k)-1/找到一个位置then if kn then print（X）else k k1；X(k)0 endif else k k1 endif repeat end NQUEENS P215-8 设W=(5,7,10,12,15,18,20)和M=35，使用过程 SUMOFSUB 找出W中使得和数等于 M的全部子集并画出所生成的部分状态空间树。