算法设计与分析基础习题参考答案

1习题1.15..证明等式gcd(m,n)=gcd(n,mmodn)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v,那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=mmodn=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0=mn的一对数字,Euclid算法在第一次叠代时交换m和n,即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入,Euclid算法最少要做几次除法?(1次)b.对于所有1≤m,n≤10的输入,Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人,f—手电筒4.对于任意实系数a,b,c,某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息2Ifa≠0D←b*b-4*a*cIfD0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturnx1,x2elseifD=0return–b/(2*a)elsereturn“norealroots”else//a=0ifb≠0return–c/belse//a=b=0ifc=0return“norealnumbers”elsereturn“norealroots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1whilen!=0do{Bin[i]=n%2;n=(int)n/2;i++;}whilei!=0do{printBin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]3//输出:thesmallestdistancedbetweentwoofitselements习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a.该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序4c.该算法不在位.额外空间forSandCount[]4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1=i=n)b.删除有序数组的第i个元素(依然有序)hints:a.Replacetheithelementwiththelastelementanddecreasethearraysizeof1b.Replacetheithelementwithaspecialsymbolthatcannotbeavalueofthearray’selement(e.g.,0foranarrayofpositivenumbers)tomarktheithpositionisempty.(“lazydeletion”)习题2.11欧几里得算法的时间复杂度欧几里得算法,又称辗转相除法,用于求两个自然数的最大公约数.算法的思想很简单,基于下面的数论等式gcd(a,b)=gcd(b,amodb)其中gcd(a,b)表示a和b的最大公约数,mod是模运算,即求a除以b的余数.算法如下:输入:两个整数a,b输出:a和b的最大公约数functiongcd(a,b:integer):integer;ifb=0returna;elsereturngcd(b,amodb);endfunction欧几里得算法是最古老而经典的算法,理解和掌握这一算法并不难,但要分析它的时间复杂度却并不容易.我们先不考虑模运算本身的时间复杂度(算术运算的时间复杂度在Knuth的TAOCP中有详细的讨论),我们只考虑这样的问题:欧几里得算法在最坏情况下所需的模运算次数和输入的5a和b的大小有怎样的关系?我们不妨设ab=1(若ab我们只需多做一次模运算,若b=0或a=b模运算的次数分别为0和1),构造数列{un}:u0=a,u1=b,uk=uk-2moduk-1(k=2),显然,若算法需要n次模运算,则有un=gcd(a,b),un+1=0.我们比较数列{un}和菲波那契数列{Fn},F0=1=un,F1=1=un-1,又因为由ukmoduk+1=uk+2,可得uk=uk+1+uk+2,由数学归纳法容易得到uk=Fn-k,于是得到a=u0=Fn,b=u0=Fn-1.也就是说如果欧几里得算法需要做n次模运算,则b必定不小于Fn-1.换句话说,若bFn-1,则算法所需模运算的次数必定小于n.根据菲波那契数列的性质,有Fn-1(1.618)n/sqrt(5),即b(1.618)n/sqrt(5),所以模运算的次数为O(lgb)---以b为底数=O(lg(2)b)---以2为底数，输入规模也可以看作是b的bit位数。习题2.27.对下列断言进行证明:(如果是错误的,请举例)a.如果t(n)∈O(g(n),则g(n)∈Ω(t(n))b.α0时,Θ(αg(n))=Θ(g(n))解:a.这个断言是正确的。它指出如果t(n)的增长率小于或等于g(n)的增长率，那么g(n)的增长率大于或等于t(n)的增长率由t(n)≤c·g(n)foralln≥n0,wherec0则：)()()1(ngntcforalln≥n0b.这个断言是正确的。只需证明))(())(()),(())((ngngngng。设f(n)∈Θ(αg(n)),则有：)()(ngcnfforalln=n0,c0)()(1ngcnfforalln=n0,c1=cα0即：f(n)∈Θ(g(n))又设f(n)∈Θ(g(n)),则有：)()(ncgnfforalln=n0,c0)()()(1ngcngcnfforalln=n0,c1=c/α0即：f(n)∈Θ(αg(n))8．证明本节定理对于下列符号也成立：a.Ω符号b.Θ符号证明：a。weneedtoproofthatift1(n)∈Ω(g1(n))andt2(n)∈Ω(g2(n)),thent1(n)+t2(n)∈Ω(max{g1(n),g2(n)})。由t1(n)∈Ω(g1(n))，t1(n)≥c1g1(n)foralln=n1,wherec10由t2(n)∈Ω(g2(n))，6T2(n)≥c2g2(n)foralln=n2,wherec20那么，取c=min{c1,c2},当n=max{n1,n2}时：t1(n)+t2(n)≥c1g1(n)+c2g2(n)≥cg1(n)+cg2(n)≥c[g1(n)+g2(n)]≥cmax{g1(n),g2(n)}所以以命题成立。b.t1(n)+t2(n)∈Θ()))(2),(1max(ngng证明：由大Ⓗ的定义知，必须确定常数c1、c2和n0，使得对于所有n=n0，有：))(2),(1max()(2)(1))(2),(1max((1ngngntntngngc由t1(n)∈Θ(g1(n))知，存在非负整数a1,a2和n1使：a1*g1(n)=t1(n)=a2*g1(n)-----(1)由t2(n)∈Θ(g2(n))知，存在非负整数b1,b2和n2使：b1*g2(n)=t2(n)=b2*g2(n)-----(2)(1)+(2):a1*g1(n)+b1*g2(n)=t1(n)+t2(n)=a2*g1(n)+b2*g2(n)令c1=min(a1,b1),c2=max(a2,b2)，则C1*(g1+g2)=t1(n)+t2(n)=c2(g1+g2)-----(3)不失一般性假设max(g1(n),g2(n))=g1(n).显然，g1(n)+g2(n)2g1(n)，即g1+g22max(g1,g2)又g2(n)0，g1(n)+g2(n)g1(n),即g1+g2max(g1,g2)。则（3）式转换为：C1*max(g1,g2)=t1(n)+t2(n)=c2*2max(g1,g2)所以当c1＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)时，当n=n0时上述不等式成立。证毕。10.切忌算法走的步数和人真实走的步数的区别，算法是不需要走回头路的。习题2.4解下列递推关系（做a,b）a.解：0)1(5)1()(xnxnx当n1时7b.解：对于计算n!的递归算法F(n)，建立其递归调用次数的递推关系并求解。解：考虑下列递归算法，该算法用来计算前n个立方的和：S(n)=13+23+…+n3。算法S(n)//输入：正整数n//输出：前n个立方的和ifn=1return1elsereturnS(n-1)+n*n*na.建立该算法的基本操作次数的递推关系并求解b.如果将这个算法和直截了当的非递归算法比，你做何评价？解：a.4)1()1(3)(xnxnx当n1时86.汉诺塔的非递归问题请见F:\work\继续教育\算法设计与分析基础7.a.请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值。b.建立该算法所做的加法运算次数的递推关系并求解c.为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。d.对于该问题的求解来说，这是一个好的算法吗？解:a.算法power(n)//基于公式2n=2n-1+2n-1,计算2n//输入:非负整数n//输出:2n的值Ifn=0return1Elsereturnpower(n-1)+power(n-1)c.9nininC01122)(8.考虑下面的算法算法Min1(A[0..n-1])//输入:包含n个实数的数组A[0..n-1]Ifn=1returnA[0]Elsetemp←Min1(A[0..n-2])Iftemp≤A[n-1]returntempElsereturnA[n-1]a.该算法计算的是什么?b.建立该算法所做的基本操作次数的递推关系并求解解:a.计算的给定数组的最小值b.01)1()(nCnC9.考虑用于解决第8题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为Min2(A[0..n-1])算法Min(A[r..l])Ifl=rreturnA[l]Elsetemp1←Min2(A[l..(l+r)/2])Temp2←Min2(A[l..(l+r)/2]+1..r)Iftemp1≤temp2r