《计算机算法基础》课后答案

1、计算机算法分析习题课第四章：2、3、5、6、10、11、23P99-2在下列情况下求解41节的递归关系式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(2T(2k-2)+f(2k-1)+f(2k)=22T(2k-2)+21f(2k-1)+f(2k)=2kT(l)+2k-lf(2)+2k-2f(22)+20f(2k)=2kg(n)+2k-lf(2)+2k-2f(22)+20f(2k)g(n)=O(1)和f(n)=O(n)

2、当g(n)=O(1)和f(n)=O(n)时不妨设g(n)=a，f(n)=bn,贝lj：T(n)=T(2k)=2ka+2k-l*2b+2k-2*22b+.+20*2kb=2ka+kb2k=an+bnlog2n=O(nlog2n)g(n)=O(1)和f(n)=O当g(n)=O(l)和f(n)=O(l)时，不妨设g(n)=c,f(n)=d,贝lj：T(n)=T(2k)=c2k+2k-ld+2k-2d+20d=c2k+d(2k-1)=(c+d)n-d=O(n)P99-3根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程ProcedureBINSRCH(A,low,high,x,j)inte

3、germidiflowshighthenmid4(low+high)/2ifx=A(mid)thenjmid;endififxA(mid)thenBINSRCH(A,mid+1,high,x,j);endififxA(mid)thenBINSRCH(A,low,mid-1,x,j);endifelsej-0;endifendBINSRCH作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x,或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。ProcedureThriSearch(A,x,n,j)integerlow,hi

4、gh,p1,p2lowT;highnwhilelowhighdop1(high+2low)/3Jp2(2high+low)/3Jcase:x=A(p1):jp1;return:x=A(p2):jp2;return:xA(p2):lowp2+1:else:lowp1+1;highp2-1endcaserepeatj0endThriSearch实例运行627981,2,3,4,5,6,7,8,93611234567891234567891234567891234567891234567891234567893698n足够小否则f(Il)=01H(n/3)+f(n)1g(n)=0(1)Miuaw*m

5、ilH(n)=H(n/3)+2H(3)=3H(2)=2H(l)=lH(n)=时间复杂度成功:口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成立;假设nWk（k0）时，E=l+2n成立;L*11F严Fr则当n=k+1时，不妨认定某个内结点x,而且它另叶结点（根据二元扩展树的定义，一定存在这样的结点X,且设该结点的层数为h）,将结点x及其左右子

6、结点（外结点）从原树中摘除（x替换为外结点）.此时新树内部结点为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的最坏情况时间是O（nlogn）,它的最好情况时间是什么？能说归并分类的时间是（nlogn）吗？最好情况：对有序文件进行排序分析归并的次数不会发生变化-log(n)次归并中比较的次数会发生变化(两个长n/2序列归并)最坏情况两个序列交错大小需要比较n

7、-1次最好情况一个序列完全大于/小于另一个序列口比较n/2次差异都是线性的，不改变复杂性的阶最好情况也是nlog(n),平均复杂度nlog(n)。P99-11写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。见数据结构一第九章P238算法MPass(R，n，length.X)MP1初始化MP2合并相邻的两个长度为length的子文件WHILLEiWn-2*length+1DO(Merge(R，i，i+length-l，i+2*length-1.X)iT+2*length).MP3处理余留的长度小于2*length的子文件IFi+length-1nTHENMerge(R,i,i+leng

8、th-1,n.X)ELSEFORj=iTOnDOXj-RjlP99-23通过手算证明(4.9)和(4.10)式确实能得到C11,C12,C21和C22的正确值。C11=P+S-T+V=(A11+A22)(B11+B22)+A22(B21-B11)-(A11+A12)B22+(A12-A22)(B21+B22)=A11B11+A22B11+A11B22+A22B22+A22B21-A22B11-A11B22-A12B22+A12B21+A12B22-A22B21-A22B22=A11B11+A12B21P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B1

9、1U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)C12=R+T=A11B12-A11B22+A11B22+A12B22=A11B12+A12B22C21=Q+S=A21B11+A22B11+A22B21-A22B11=A21B11+A22B21C22=P+R-Q+U=(A11+

10、A22)(B11+B22)+A11(B12+B22)-(A21+A22)B11+(A21-A11)(B11+B12)A11B11+A22B11+A11B22+A22B22+A11B12-A11B22-A21B11-A22B11+A21B11+A21B12-A11B11-A11B12=A22B22+A21B12P=(A11+A22)(B11+B22)T=(A11+A12)B22Q=(A21+A22)B11U=(A21-A11)(B11+B12)R=A11(B12-B22)V=(A12-A22)(B21+B22)S=A22(B21-B11)计算机算法分析习题课第五章：2、3、6、8、9、10、11

11、、12P121-2求以下情况背包问题的最优解，n=7,m=15,(p1，,p7)=(10,5,15,7,6,183)和(w1,w7)=(2,3,5,7,1,4,1)。将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/FG(I)是多少？当物品按wi的非降次序输入时，重复的讨论。按照pi/mi的非增序可得(p5/w5,p1/w1,p6/w6,p3/w3,p7/w7,p2/w2,p4/w4)=(6,5,9/2,3,3,5/3,1)所以最优解为：(1,23,1,0,1,1,1)，并且FO(I)=16

12、6/3按照pi的非增次序输入时，得到(p6,p3,p1,p4,p5,p2,p7)=(18,15,10,7,6,5,3)，对应的(w6,w3,w1,w4,w5,w2,w7)=(4,5,2,7,1,3,1),则FG(I)的解为(1,0,1,4/7,0,1,0)，并且FG(I)=47，所以FO(I)/FG(I)=166/141.按照wi的非降次序输入时，得(w5,w7,w1,w2,w6，w3,w4)=(1,1,2,3,4,5,7)，相应的(p5,p7,p1,p2,p6,p3,p4)=(6,3,10,5,18,15,7),则FW(I)的解为(1,1,4/5,0,1,1,1)，并且FW(I)=54，所以

13、FO(I)/FW(I)=83/81.P122-33.(0/1背包问题)如果将53节讨论的背包问题修改成极大化约束条件口皿=0或11WiWn口这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装的进就将其装入背包。证明这种策略不一定能得到最优解。1ng1niiwxM0，要用的处理时间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生成的解为：J(1)

14、=7(2),J(1)=7(2),J(2)=3(4)；J(1)=7(2),J(2)=4(3),J(3)=3(4)；J(1)=6(1),J(2)=7(2),J(3)=4(3),J(4)=3(4)；证明即使作业有不同的处理时间定理53亦真。这里，假定作业i的效益pi0，要用的处理时间ti0，限期di$ti(P106)定理53:设J是K个作业的集合，o=i1i2ik是J中作业的一种排序,它使得di1Wdi2WWdikJ是一个可行解，当且仅当J中的作业可以按照a的次序又不违反任何一个期限的情况下来处理.证明：显然即使ti0(di上ti),如果J中的作业可以按照。的次序而又不违反任何一个期限来处理，即对a

15、次序中的任一个作业k,应满足dk込=灿1,则J就是一个可行解。下面证明如果J是可行解，a二ili2ik使得J中的作业可以按照dilWdi2WWdin序列排列而又不违反任何一个期限。J是可行解，则必存在a=r1r2rn，使得对任意的rk，都有dk工二kjjtl，我们设a是按照di1Sdi2SSdin排列的作业序列。假设a工a，那么令a是使ra工ia的最小下标，设rb=ia，显然ba，在a中将ra与rb相交换，因为drbdra，显然ra和rb可以按期完成作业我们还要证明ra和rb之间的作业也能按期完成。因为drbdra，而显然二者之间的所有作业rt，都有drbdrt，又由于a是可行解,所以1btb

16、krrktdd=，所以作业ra和rb交换后，仍满足1ttkrktd=1a假设当mA(i,k)+A(k,j)thenA(i,j)A(i,k)+A(k,j)Path(i,j)Path(i,k)endifrepeatrepeatrepeatfori1tondo输出最优路径forj1tondoprint(“thepathofitojis”i)kpath(i,j)whilek#0doprint(k)kpath(k,j)repeatrepeatrepeatendShortestPath分析时间复杂度第一个循环：0(n2)第一个循环：0(n3)第一个循环：O(n2)空间复杂度Cost(n,n)A(n,n)P

17、ath(n,n)O(n2)P151-3对于标识符集(a1,a2,a3,a4)=(end,goto,print,stop),已知成功检索概率为P=1/20,P(2)=1/5,P(3)=1/10,P(4)=1/20，不成功检索概率为Q(0)=1/5,Q(1)=1/10,Q=1/5,Q(3)=1/20,Q(4)=1/20，用算法OBST对其计算W(ij),R(i,j)和C(i,j)(0Wi,jW4)。P136算法6.5P(i)P(1)=1/20,P(2)=1/5,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/2

18、0P(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)=1u*LF4-RR1”PTRc44+2+17+4+4=15152+1=1818+1+1=2001222卄722323922+4+4=1G10+2+1=13131+1=150222010202744+1+27+I+i=903307121i-Hl0403100P151-4口证明算法OBST的计算时间是0(n2)。在已知根R(i,j),0WijW4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。将C中元素的加法看做基本运算，则算法

19、OBST的时间复杂性为:20(l,)(,l)l)nnmmiRjRj=+EE=20(l,)(,l)l)nnmmiRiimRiim=+-+-+EE=2(1,)(0,1)1)nmRnmnRmnm=+EO(n2)ProcedureBuildTree(m,n,R,Root)integerR(n,n),kTreeNodeRoot,LR,RRkR(m,n)ifk#0thendata(Root)k,BuileTree(m,k-1,R,LR),BuileTree(k,n,R,RR)left(Root)LR,right(Root)RRelsedata(Root)m,left(Root)null,right(Roo

20、t)null,endifendBuildTree时间复杂性分析：T(n)=c+T(k)+T(n-k-1),此递推式保证算法的时间复杂性为0(n),也可从递归的角度出发，递归的次数正是结点的个数,而每次递归时间复杂性为常数，所以算法的时间复杂度也为0(n)。P151-5口由于我们通常只知道成功检索和不成功检索概率的近似值，因此，若能在较短的时间内找出几乎是最优的二分检索树,也是一件很有意义的工作。所谓几乎是最优的二分检索树，就是对于给定的P和Q，该树的成本(由(6.9)式计算)几乎最小。已经证明，由以下方法获得这种检索树的算法可以有O(nlogn)的时间复杂度，选取这样的k为根，它使|W(0,k

21、-1)-W(k,n)|尽可能地小。重复以上步骤去找这根的左、右子树。对于题63的数据，用上述方法找出一棵这样的二分检索树。它的成本是什么？用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总体成本是4+2*(2+1)+2*(4+2+4)+3*(1+1+1)=39ProcedureCreateTree(m,n,root,w)integerr,k,root(n,n),w(n,n)realww,min_gifm=nthenroot(m,n)0elseifm=n-1thenroot(m,n)nelseforkm+1tondoww|w(m,k-1)-w(k,n)|ifww1121()0()iiiiiiigxcxcdxxd=+0dof还剩有没检验过的X(k)使得X(k)WT(X(l),.,X(k-l)andBk(X(l),.,X(k)=truet