1、计算机算法分析习题课第四章：2 、3、5、6、10、11、23P99-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
2、)和f(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 BINS
3、RCH(A, low, high, x, j)integer midif lowhighthenmid(low+high)/2 if x=A(mid) thenjmid;endifif xA(mid) thenBINSRCH(A, mid+1, high, x, j);endifif xA(mid) thenBINSRCH(A, low, mid-1, x, j);endifelsej0;endifend BINSRCHP99-5作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析
4、此算法在各种情况下的计算复杂度。Procedure ThriSearch(A, x, n, j)integer low, high, p1, p2low1; highnwhile lowhighdop1(high+2low)/3 p2(2high+low)/3 case:x=A(p1): jp1; return:x=A(p2): jp2; return:xA(p2): low p2+1:else: lowp1+1; highp2-1end caserepeatj0end ThriSearch实例运行 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 361时间复杂度h
5、8708;成功:O(1),O(log3(n),O(log3(n)最好，平均，最坏失败:O(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
6、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的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是(nlogn)吗？最好情况：对有序文件进行排序分析归并的次数不会发生变化-log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小需要比较n-1次
7、048708;最好情况一个序列完全大于/小于另一个序列比较n/2次差异都是线性的，不改变复杂性的阶最好情况也是nlog(n), 平均复杂度nlog(n)。P99-11写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。见数据结构-第九章P238算法MPass（R，n，1engthX）MP1 初始化i1 MP2 合并相邻的两个长度为length的子文件WHILE i n 2*length + 1 DO（Merge（R，i，ilengthl，i2*length1X）.ii2
8、length ）MP3 处理余留的长度小于2*length的子文件IF i+length1 0，要用的处理时间ti0，限期diti.解：根据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.J(1)=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)；证明即使作业
9、有不同的处理时间定理5.3亦真。这里，假定作业i的效益pi0，要用的处理时间ti0，限期diti.(P106)定理5.3:设J是K个作业的集合, =i1i2ik是J中作业的一种排序,它使得di1di2dik.J是一个可行解,当且仅当J中的作业可以按照的次序又不违反任何一个期限的情况下来处理.证明：显然即使ti0（diti），如果J中的作业可以按照的次序而又不违反任何一个期限来处理，即对次序中的任一个作业k，应满足dk =kjjt1，则J就是一个可行解。下面证明如果J是可行解， =i1i2ik使得J中的作业可以按照di1di2din 序列排列而又不违反任何一个期限。 J是可行
10、解，则必存在=r1r2rn，使得对任意的rk，都有 dk=kjjt1，我们设是按照di1di2din排列的作业序列。假设，那么令a是使raia的最小下标，设rb=ia，显然ba，在中将ra与rb相交换，因为drbdra，显然ra和rb可以按期完成作业，我们还要证明ra和rb之间的作业也能按期完成。因为drbdra，而显然二者之间的所有作业rt，都有drbdrt，又由于是可行解，所以1btbkrrktdd=，所以作业ra和rb交换后，仍满足1ttkrktd=，即所有作业可依新产生的排列=s1s2sn的次序处理而不违反任何一个期限，连续使用这种方法，就可转换成且不违反任何一个期限，定理得证。 P1
11、23-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中的作业根据时间期限的非降次序排列，得到i1i2ikin，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任意作业ik，如果它
12、的时间期限是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=min n,maxd(i) =min7,4 =4P123-11证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足n m
13、od (k-1)=1.证明对于满足n mod (k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.证明：设某棵树内部节点的个数是i，外部结点的个数是n，边的条数是e，则有e=i+n-1ik=eik=i+n-1(k-1)i=n-1n mod (k-1)=1P123-12证明如果n mod (k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,
14、q2,qn）生成一棵最优的k元归并树。(P111)当（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 (s0)，都生成一棵最优树，则只需证明对于(q1,q2,qn)，其中n=(k-1)(s+1)+1，也能生成最优树即可。不失一般性，假定q1q2qn，且q1,q2
15、qk是算法所找到的k棵树的WEIGHT信息段的值。于是q1,q2,qk可生成子树T，设T是一棵对于（q1,q2,qn）的最优k元归并树。设P是距离根最远的一个内部结点。如果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)的最优归并树。
16、因此TREE生成一棵关于(q1,q2,qn)的最优归并树。计算机算法分析习题课第六章1 2 3 4 5 6 8 13 17动态规划1.多阶段过程2.满足最优性原理3.建立递推关系式P151-1递推关系式（6.8）对右图成立吗？为什么？递推关系式（6.8）为什么对于含有负长度环的图不能成立？解：成立，不包含负长度环可以使节点间的长度任意小。P151-2修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？回忆算法：P127 算法6.1P131 算法6.3P127 算法
17、6.1D(i,j)/D(j) :从节点j到汇点t的最优路径中下一个节点，即最优路径中j的后继节点。算法6.1在计算COST(j)的同时也计算了D(j)37行计算出D( j ) 之后，即可计算最短路径。911行P131 算法6.3对矩阵进行初始化，每个元素赋值为边的长度（如果没边则赋值成MAX）15行迭代计算最短路径长度612行仿照6.1，在每次计算最短路径的时候计算出D(j) 再通过D(j) 就可以表示出最短路径for k1 to n do /迭代计算for i1 to n
18、dofor j1 to n doif A(i,j)A(i,k)+A(k,j) thenA(i,j)A(i,k)+A(k,j)Path(i,j)Path(i,k)endifrepeatrepeatrepeatfor i1 to n do/输出最优路径for j1 to n doprint(“thepath of i to j is ”i )kpath(i, j)while k0 doprint(k)kpath(k, j)repeatrepeatrepeatend ShortestPath分析时间复杂度第一个循环：O(n2)第一个循环：O(n3)第一个循环：O(n2)h
19、8707;空间复杂度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(3)=1/20, Q(4)=1/20，用算法OBST对其计算W(i,j)，R(i, j)和C(i, j)（0i, j4）。P136 算法6.5P（i）P(1)=1/20, P(2)=1/5,
20、P(3)=1/10, P(4)=1/20Q（i）Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20,Q(4)=1/20P（i）P(1)=1, P(2)=4, P(3)=2, P(4)=1Q（i）Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=1P151-4证明算法OBST的计算时间是O(n2)。在已知根R(i, j)，0i j4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。 将C中元素的加法看做基本运算，
21、则算法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), kTreeNodeRoot, LR, RRkR(m,n)if k0 then data(Root)k,BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR)left(Root)LR, right(Root)RRelse data(Root)m, left(
22、Root)null, right(Root)null, endifend BuildTree时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。P151-5由于我们通常只知道成功检索和不成功检索概率的近似值，因此，若能在较短的时间内找出几乎是最优的二分检索树，也是一件很有意义的工作。所谓几乎是最优的二分检索树，就是对于给定的P和Q，该树的成本（由（6.9）式计算）几乎最小。已经证明，由以下方法获得这种
23、检索树的算法可以有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,1)=1，T(2,4)=3，T(3,4)=4总体
24、成本是4+2*（2+1）+2*（4+2+4）+3*（1+1+1）=39Procedure CreateTree(m, n, root, w)integer r, k, root(n, n), w(n, n)real ww, minif m=n then root(m, n)0else if m=n-1 then root(m,n)nelsefor km+1 to n doww|w(m, k-1)-w(k, n)|if ww min then minww, rkendifrepeatroot(m, n)rCall CreateTree(m, r-1)Call CreateTree(r, n)en
25、difEnd 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, 0in。还要求对n的任意取值都适用。取(P1,P2,Pi,)=(W1,W2,Wi,)=(20,21,2i-1,)P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，
26、即可知是最坏的情况。可用归纳法证明此结论。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)(W2的库存为dj-x)。于是此仓
27、库问题的最优总花费是gn(r1).P128-13求gi(x)的递推关系式写一个算法求解这个递推关系式并要能得到xij的决策值得最优序列，1i2,1jn.1112110min,()()()() miniiiiiiiiixxdiigxcxcdxgxdxd1121()()() iiiiiiigxcxcdxxd=+P152-17最优性原理并不总是对可以将其解看成是一系列决策结果的所有问题成立。找两个最优性原理不成立的例子，并说明对这两个问题最优性原理为什么不成立。多段图问题：路径和改为路径乘积并允许出现负数计算机算法分析习题课第八章：1、3、8、9P215-1修
28、改算法8.1和8.2，使它们只求出问题的一个解而不是问题的全部解算法8.1procedure BACKTRACK(n)integerk,n; localX(1: n)k 1whilek0 doif还剩有没检验过的X(k)使得X(k) T ( X(1), ,X(k-1) and Bk ( X(1), ,X(k) =truethen if ( X(1), ,X(k) ) 是一条抵达一答案节点的路径then print ( X(1), ,X(k)returnendifk k 1elsek k 1endifrepeatend BACKTRACK算法8.2procedure RBACKTRACK(k)g
29、lobal n, X(1:n)for满足下式的每个X(k)X(k) T ( X(1), ,X(k-1) and Bk( X(1), ,X(k)=truedoif( X(1), ,X(k)是一条抵达一答案结点的路径then print( X(1), ,X(k)returnendifcall RBACKTRACK(k+1)repeatend RBACKTRACKP215-3重新定义过程PLACE(k)，使它的返回值或者是第k个皇后可以放置于其上的合法列号，或者是一个非法值，这样可以提高一些NQUEENS的效率，按以上策略重写这两个过程。算法8.4procedure PLACE(k)global X(1:K) ; integer i, kj -1while X(k)n doi 1while i0 doX(k) X(k)+1if PLACE(k) -1 /找到一个位置then if knthen print（X）else k k1；X(k) 0endifelse k k1endifrepeatend NQUEENSP215-8设W=(5,7,10,12,15,18,20) 和M=35，使用过程SUMOFSUB找出W中使得和数等于M的全部子集并画出所生成的部分状态空间树。
免费区 
