计算机算法设计与分析(第4版)-王晓东习题解答

1第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。若f=Ο(g)，则必然存在常数c10和n0，使得nn0，有fc1*g(n)。由于c10，故g(n)1/c1*f(n)，故g=Ω(f)。必要性。同理，若g=Ω(f)，则必然存在c20和n0，使得nn0，有g(n)c2*f(n).由于c20，故f(n)1/c2*f(n)，故f=Ο(g)。2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c10，c20和n0，使得nn0，有c1*g(n)f(n)c2*g(n)。由于c10，c20，f(n)c1*g(n)可得g(n)1/c1*f(n)，同时，f(n)c2*g(n)，有g(n)1/c2*f(n)，即1/c2*f(n)g(n)1/c1*f(n)，故g=Θ(f)。3）Ο(f+g)=Ο(max(f,g))，对于Ω和Θ同样成立。证明：设F(n)=Ο(f+g)，则存在c10，和n1，使得nn1，有F(n)c1(f(n)+g(n))=c1f(n)+c1g(n)c1*max{f,g}+c1*max{f,g}=2c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)=Ο(max(f,g))对于Ω和Θ同理证明可以成立。4）log(n!)=Θ(nlogn)2证明：由于log(n!)=nii1lognin1log=nlogn，所以可得log(n!)=Ο(nlogn)。由于对所有的偶数n有，log(n!)=nii1lognnii2/lognnin2/2/log(n/2)log(n/2)=(nlogn)/2-n/2。当n4，(nlogn)/2-n/2(nlogn)/4，故可得n4，log(n!)(nlogn)/4，即log(n!)=Ω(nlogn)。综合以上两点可得log(n!)=Θ(nlogn)2.设计一个算法，求给定n个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3）算法：Voidfindsecond(ElemTypeA[]){for(i=2;i=n;i++)if(A[1]A[i]){temp=A[1];A[1]=A[i];A[i]=temp;}for(i=3;i=n;i++)if(A[2]A[i])3{temp=A[1];A[1]=A[i];A[i]=temp;}returnA[2];}该算法使用的比较次数为：2n-33.设计一个算法，求给定n个元素的最大和最小元素。（要求算法的复杂度至多为1.5n）算法：voidMaxmin2(A;l,r;intx;inty);{if(l=r){x=A[l];y=A[r];return;}if(r-l=1){if(A[l]A[r]){x=A[l];y=A[r];}else{x=A[r];y=A[l];}return;}else{mid:=(l+r)div2;Maxmin2(A,l,mid,x1,y1);Maxmin2(A,mid+1,r,x2,y2);4x=min(x1,x2);y=max(y1,y2);}}该算法使用的比较次数为：1.5n-24.给定多项式p(x)=anxn+an-1xn-1+…+a1x+a0，假设使用以下方法求解：p=a0;xpower=1;for(i=1;i=n;i++){xpower=x*xpower;p=p+ai*xpower;}求（1）该算法最坏情况下使用的加法和乘法分别为多少次？（2）能不能对算法的性能进行提高？解：（1）该算法最坏情况下使用的加法n次，乘法2n次（2）改进的算法为：floatHorner(A,floatx){p=A[n+1];for(j=1;j=n;j++)p=x*p+A[n-j];returnp;}该算法中使用加法n次，乘法n次5第二章1．求解下列递推关系：1）当n≥1时，f(n)=3f(n-1)；f(0)=5解：f(n)=3f(n-1)=32f(n-2)=…=3nf(n-n)=3n*5=5*3n2)当n≥2时，f(n)=5f(n-1)-6f(n-2)；f(0)=1；f(1)=0解：该递推关系的特征方程为：x2-5x+6=0特征根为：r1=2；r2=3故f(n)=c1*2n+c2*3n有f(0)=c1*20+c2*30==c1+c2=1且f(1)=c1*21+c2*31==2c1+c32=0可得c1=3，c2=-2故f(n)=3*2n-2*3n3)当n≥1时，f(n)=f(n-1)+n2；f(0)=0解：f(n)=f(n-1)+n2=f(n-2)+(n-1)2+n2=….=f(0)+12+22+…+(n-1)2+n2=12+22+…+(n-1)2+n2=1/6n(n+1)(2n+1)4)当n≥1时，f(n)=2f(n-1)+n2；f(0)=1解：设f(n)=2nf’(n)，且f’(0)=f(0)=16则2nf’(n)=2*（2n-1f’(n-1)）+n2即f’(n)=f’(n-1)+nn22=f’(0)+niii122=1+niii122所以f(n)=2n*(1+niii122)=2n*(10-nn26)=10*2n-(n+6)5)当n≥1时，f(n)=nf(n-1)+1；f(0)=1解：f(n)=n!*(f’(0)+nii1!1)=n!*(1+nii1!1)2.求解下面的递推式：当n≥2时，f(n)=4f(n/2)+n；f(1)=1。假设n为2的幂，用直接展开法求解递推式。解：令kn2f(n)=4f(n/2)+n=nnnf)2)2(4(*42=nnnf2)2(422=nnnnf22)2(4233=….=nnnnfkkk22)2(41=nfkk)122()1(41=nnk)12(27=nn223.求解下面的递推式：当n≥2时，f(n)=9f(n/3)+n2；f(1)=1。假设n为3的幂，用直接展开法求解递推式。解：令kn3f(n)=2)3(9nnf=222))3()3(9(9nnnf=2222)3(9nnnf=22233)3(9nnnnf=….=2)3(9knnfkk=nnn322log4.法求解递推式的上界：当n≥4时，nnfnfnf)43()4()(；当n4时，f(n)=4。解：由于递推式为44)43()4(4)(nnnnfnfnf这里14341故作猜想nnfnf)2(2)(的解为：nnnnf4log)(故对原递推式做猜想nncnnf4log)(由于nnfnfnf)43()4()(8nnnncnnnc43443log43444log4nnnncnnnc43443log43444log4=nncnncn5)43log(log43)4log(log41ncnncn5)3log432(log若使f(n)满足上界为nncn4log则必有nncnncnncn4log5)3log432(log即0)3log432(ncn所以23.13log4321c故nnnnf4log23.1)(，即上界为nnn4log23.14.设计算法，求解问题：有一楼梯共M级，刚开始时你再第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？intfa(intm){intz;if(m==1)z=1;elseif(m==2)z=2;、elsez=fa(n-1)+fa(n-2);returnz;}95.设计算法，一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？这道题的思路与字符串的组合很像，用递归解决。一次射击有11种可能，命中1环至10环，或脱靶。函数功能：求解number次打中sum环的种数函数参数：number为打靶次数，sum为需要命中的环数，result用来保存中间结果，total记录种数voidShootProblem_Solution(intnumber,intsum,vectorint&result,int&total){Iif(sum0||number*10sum)//加number*10sum非常重要，它可以减少大量的递归，类似剪枝操作return;if(number==1)//最后一枪{if(sum=10)//如果剩余环数小于10，只要最后一枪打sum环就可以了{for(unsignedi=0;iresult.size();i++)coutresult[i]'';coutsumendl;total++;10return;}elsereturn;}for(unsignedi=0;i=10;i++)//命中0-10环{result.push_back(i);ShootProblem_Solution(number-1,sum-i,result,total);//针对剩余环数递归求解result.pop_back();}}voidShootProblem(intnumber,intsum){inttotal=0;vectorintresult;ShootProblem_Solution(number,sum,result,total);couttotalnums=totalendl;}intmain()11{ShootProblem(10,90);return0;}6.设计算法，求解猴子吃桃问题：有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，依此类推），第九天正好吃完，问猴子们摘来了多少桃子？思路：可假设有第十天，则第十天剩余的桃子数目为0，由此递推可得每一天剩余的桃子数目。第一天的桃子数目即为猴子摘桃子的总数。假设有第10天，则第10天吃0个桃子，倒推出前一天的个数x，x[9]=2(x[10]+1)。voidmain(){inti=0;intnum[11];num[10]=0;for(i=9;i=1;i--)num[i]=2*(num[i+1]+1);coutnum[1];}第三章121.设计一个分治算法，判定两棵给定的二叉树T1和T2是否相同。采用先序遍历算法来实现，其中访问结点的操作为“判断两个结点是否相同”，如果t1和t2所指的结点均为空或均不为空且数据域的值相等，则继续先序比较它们的左、右子树，否则返回0。具体算法如下：intEqualBtr(bitreptrt1,bitreptrt2){if(t1==NULL&&t2==NULL)return(1);if((t1==NULL&&t2!=NULL)||t1!=NULL&&t2==NULL)||(t1-data!=t2-data))return(0);hl=EqualBtr(t1-Lchild,t2-Lchild);hr=EqualBtr(t1-Rchild,t2-Rchild);if(hl==1&&hr==1)return1;elsereturn0;}2.设计一个分治算法，求给定二叉树的高度。设根结点为第一层的结点，所有k层结点的左、右孩子结点在k+1层。因此，可以通过先序遍历计算二叉树中每个结点的层次，其中最大值即为该二叉树的深度。具体算法如下：voidBtdepth(bitreptrt,intk,int&h)//指针t指向二叉树的根结点，k,h的初值均设为0{if(t!=NULL){k++;//表示结点的层次if(kh)h=k;Btdepth(t-Lchild,k,h);Btdepth(t-Rchild,k,h);}}3.设计一个分治算法，在一个具有n个数的数组中找出第二大元素，并给13出算法的复杂度