《计算机算法基础》第三版_课后习题答案

上机实验书上121页5。25。3书上1516。16。36。6他说搞懂这几题和实验就没问题了4.2在下列情况下求解递归关系式T(n)=()2(/2)()gnTnfn否则足够小n当①n=2kg(n)=O(1)和f(n)=O(n)；②n=2kg(n)=O(1)和f(n)=O(1)。解: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(1)+2k-1f(2)+2k-2f(22)+…+20f(2k)=2kg(n)+2k-1f(2)+2k-2f(22)+…+20f(2k)①当g(n)=O(1)和f(n)=O(n)时，不妨设g(n)=a，f(n)=bn，a，b为正常数。则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)=c，f(n)=d，c，d为正常数。则T(n)=T(2k)=c2k+2k-1d+2k-2d+…+20d=c2k+d(2k-1)=(c+d)n-d=O(n)4.3根据教材中所给出的二分检索策略，写一个二分检索的递归过程。ProcedureBINSRCH(A,low,high,x,j)integermidiflow≤highthenmid←2/)(highlowifx=A(mid)thenj←mid;endififxA(mid)thenBINSRCH(A,mid+1,high,x,j);endififxA(mid)thenBINSRCH(A,low,mid-1,x,j);endifelsej←0;endifendBINSRCH4.5作一个“三分”检索算法。它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。ProcedureThriSearch(A,x,n,j)integerlow,high,p1,p2low←1;high←nwhilelow≤highdop1←3/)2(highlow;p2←3/)2(highlowcase:x=A(p1):j←p1;return:x=A(p2):j←p2;return:xA(p1):high←p1-1:xA(p2):low←p2+1:else:low←p1+1;high←p2-1endcaserepeatj←0endThriSearchT(n)=)()3/()(nfnTng否则足够小ng(n)=O(1)f(n)=O(1)成功:O(1),O(log3(n)),O(log3(n))最好，平均，最坏失败:O(log3(n)),O(log3(n)),O(log3(n))最好，平均，最坏4.6对于含有n个内部结点的二元树，证明E=I+2n，其中，E，I分别为外部和内部路径长度。证明：数学归纳法①当n=1时，易知E=2，I=0，所以E=I+2n成立；②假设n≤k(k0)时，E=I+2n成立；③则当n=k+1时，不妨假定找到某个内结点x为叶结点（根据二元扩展树的定义，一定存在这样的结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除，生成新二元扩展树。此时新二元扩展树内部结点为k个，则满足Ek=Ik+2k，考察原树的外部路径长度为Ek+1=Ek-（h-1）+2h，内部路径长度为Ik+1=Ik+（h-1），所以Ek+1=Ik+2k+h+1=Ik+1+2k+2=Ik+1+2(k+1)，综合①②③知命题成立。4.10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？最好情况：是对有序文件进行排序。分析：在此情况下归并的次数不会发生变化----log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小，需要比较n-1次最好情况一个序列完全大于/小于另一个序列，比较n/2次差异都是线性的，不改变复杂性的阶因此最好情况也是nlogn,平均复杂度nlogn。可以说归并分类的时间是Θ(nlogn)5.2①求以下情况背包问题的最优解，n=7，m=15，）（71,.....pp=(10,5,15,7,6,18,3)和）（71,.....ww=(2,3,5,7,1,4,1)。②将以上数据情况的背包问题记为I。设FG(I)是物品按ip的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/FG(I)是多少?③当物品按iw的非降次序输入时，重复②的讨论。解：①按照ip/iw的非增序可得(5p/5w，1p/1w，6p/6w，3p/3w，7p/7w，2p/2w，4p/4w)=(6,5,9/2,3,3,5/3,1)W的次序为(1,2,4,5,1,3,7),解为(1,1,1,1,1,2/3,0)所以最优解为：（1,2/3,1,0,1,1,1）FO(I)=166/3②按照Pi的非增次序输入时得到(6p,3p,1p,4p,5p,2p,7p)=(18,15,10,7,6,5,3)，对应的(6w,3w,1w,4w,5w,2w,7w)=(4,5,2,7,1,3,1)解为(1,1,1,4/7,0,0,0)所以FG(I)的解为（1,0,1,4/7,0,1,0）FG(I)=47，所以FO(I)/FG(I)=166/141.③按照iw的非降次序输入时得到(5w,7w,1w,2w,6w,3w,4w)=(1,1,2,3,4,5,7)相应的(5p,7p,1p,2p,6p,3p,4p)=(6,3,10,5,18,15,7)解为(1,1,1,1,1,4/5,0)则FW(I)的解为（1,1,4/5,0,1,1,1）FW(I)=54，所以FO(I)/FW(I)=83/81.5.3．（0/1背包问题）如果将5.3节讨论的背包问题修改成极大化nii1px约束条件Mnii1wxxi=0或11≤i≤n这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按ip/iw的非增次序考虑这些物品，只要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。证明：当按照ip/iw的非增次序考虑物品存放背包时，如果所装入的物品恰能装满背包时，易证为最优解，否则未必是最优解。可举例如下：设n=3，M=6，（1p,2p,3p）=(3,4,8)，（1w,2w,3w）=(1,2,5)，按照ip/iw的非增序得到（1p/1w,2p/2w,3p/3w）=(3,2,1.6)，则其解为（1,1,0），而事实上最优解是(1,0,1)，问题得证。5.11．①证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足nmod(k-1)=1.②证明对于满足nmod(k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.证明：①设某棵树内部节点的个数是m，外部结点的个数是n，边的条数是e，则有e=m+n-1和e=mkmk=m+n-1(k-1)m=n-1nmod(k-1)=1②利用数学归纳法。当n=1时，存在外部结点数目为1的k元树T，并且T中内部结点的度为k；假设当n≤m，且满足nmod(k-1)=1时，存在一棵具有n个外部结点的k元树T，且所有内部结点的度为k；我们将外部结点数为n(n为满足n≤m，且nmod(k-1)=1的最大值)的符合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点，易知新生成的树T’中外部结点的数目为n+(k-1)，显然n为满足nmod(k-1)=1，且比m大的最小整数，而树T’每个内结点的度为k，即存在符合性质的树。综合上述结果可知,命题成立。6.2．修改过程ALL_PATHS，使其输出每对结点（i,j）间的最短路径，这个新算法的时间和空间复杂度是多少？ProcedureShortestPath(COST,n,A,Max)integeri,j,krealCOST(n,n),A(n,n),Path(n,n),Maxfori←1tondoforj←1tondoA(i,j)←COST(i,j)ifi≠jandA(i,j)≠MaxthenPath(i,j)←jelsePath(i,j)←0endifrepeatrepeatfork←1tondofori←1tondoforj←1tondoifA(i,j)A(i,k)+A(k,j)thenA(i,j)←A(i,k)+A(k,j)Path(i,j)←Path(i,k)endifrepeatrepeatrepeatfori←1tondoforj←1tondoprint(“thepathofitojis”i)k←path(i,j)whilek≠0doprint(,k)k←path(k,j)repeatrepeatrepeatendShortestPath时间复杂度O(n3)，空间复杂度O(n2)6.4．①证明算法OBST的计算时间是O(n2)。②在已知根R(i,j)，0≤ij≤4的情况下写一个构造最优二分检索树T的算法。证明这样的树能在O(n)时间内构造出来。解：①将C中元素的加法看做基本运算，则算法OBST的时间复杂性为：20((1,)(,1)1)nnmmiRijRij20((1,)(,1)1)nnmmiRiimRiim2((1,)(0,1)1)nmRnmnRmnmO(n2)②ProcedureBuildTree(m,n,R,Root)integerR(n,n),kTreeNodeRoot,LR,RRk←R(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(Root)←null,endifendBuildTree时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法的时间复杂性为O(n)，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法的时间复杂度也为O(n)。6.8．给出一个使得DKNAP(算法6.7)出现最坏情况的例子，它使得|Si|=2i,0≤in。还要求对n的任意取值都适用。解：取(P1,P2,…,Pi,…)=(W1,W2,…,Wi,…)=(20,21,…,2i-1,…)P和W取值相同，使支配原则成立，也就是说不会因为支配原则而删除元素；只要说明不会出现相同元素被删除一个的情形，即可知是最坏的情况。可用归纳法证明此结论。