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

《算法设计与分析基础习题参考答案.docx》由会员分享，可在线阅读，更多相关《算法设计与分析基础习题参考答案.docx（28页珍藏版）》请在优知文库上搜索。

1、习题1.15.证明等式gcd(m.n=gcd(n.mn(1.n)对每一对正整数m.n都成立.Hint:根据除法的定义不难证明：如果d整除U和V.那么d一定能整除uv;加果d整除U.那么d也能修整除U的任何整数倍ku.对于任意一对正整数m,n,辑设d能整除m和nJE么d一定能整除n和r=mmodn=m-qn:显然，假设d能整除n和r,也一定能整除n=r+qn和n.数对(m.n)和(n.r)具有相同的公约数的有限非空集，其中也包括了最大公约数.故gcd(111.n)=gctcmpreturnx1.,x2e1.seifD=Oreturn-M2*a)e1.serc(umnorea1.Isme1.se/

2、a=f1.ifb0return-cbe1.se/a=b=Oifc=0return,fcnrea1.numbers*e1.sereturn,wnorea1.roots”5 .描述将十进制整数表达为.进制整数的标准算法必用文字描述b.用伪代码描述解答:今将十进制整数转换为：进制整数的修法输入：一个正整数n输出，正整数n相应的二进制数第一步：用n除以2.余数赋给Ki(i三whi1.ei!=()doprintBini;i9.考虑下面这个算法.它求的是数组中大小相差最小的两个元素的差(算法略)对这个究法做尽可能多的改良.算法MinDistance(O.n-1)“输入:数组A(0.n-1.)输出:thes

3、ma1.1.estdistancedbetweentwoofitse1.ementsdminfori0ton2doforJ4i+1.ton-Idotemp44ijiftempdmindmin-tempreturndmin习题1.3考虑这样一个排序算法,该算法对于待持序的数组中的姆一个元素,计算比它小的元素个数,然后利用这个信息.将各个元素放到有序数祖的相应位置上去.foriOton1doCounti*OfortOton-2doforji1ton-1doifiAjCcnntjCountj+1e1.seCountiCounti+1forOton1doSCunfiAia.应用该算法对列表”60,35

4、31.98.14.47”排序b.该和法稳定吗？C,该算法在位吗？解：a.该算法对列表”60.35.81.98.14.4T排序的过程如下所示:Initia1.1.yCountAfterpassi=OCountAfterpassi1CountAfterPaSSi=2CountAfterPaSSi=3CountAfterpassi=4CountFina1.stateCountArray0.5ArrayS0.5OOOOOO3O11OO122O143O15O1O23145O2I6()3581I981447I14I35476()I819Kb该算法不杨定.比方对列表“2.2*”排序C该辞法不在位.额外空间f

5、brSa1.Count1.1.4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现以下对数组的操作.使得操作时间不依敕数组的长发.a删除数组的第i个元素(1.=i=n)b.州除有序数祖的第i个元素(依然有序)hints:a. Rep1.acetheithe1.ementwiththe1.aste1.ementanddecreasethearraysizeof1b. Rep1.acetheithC1.CmCntwihaspecia1.symbo1.thatCanno1.beava1.ueofthearraysc1.emcn(c.g.,0foranarrayofpositivenumbe

6、rs)tomark(heithpositionisenpde1.e习题2.1欧几里得竟法的时间复杂度欧几里得笄法,又称混转相除法.用于求两个自然数的最大公约数.算法的思想很简单,基于卜面的数论等式gc1.(a,b)=gcd(b,amodb)其中gcd(a,b)表示a和b的班大公约数,mod是模运獴,即求a除以b的余数.算法如下：输入：两个整数&b输出:a和b的最大公约数functiongcd(a,b:intcgcr):intcgcr;ifb=0returna;e1.sereturngc=1.(假设a=2).显然.假设算法需要n次模运算.那么行Un=SCd(a.b).un+1.=O.我们比拟数列

7、un)和班波那奥数列Fn,R)-=un,F1.=1.=uk+1.+uk+2,由数学归嗨去容易得到uk=Fnk.于是得到a=uO=Fn,b=uO=Fn1.,也就是说如果欧几里得以法需要做n次模运算,班么b必定不小于Fn-1.换句话说,假设bn/Sqrt(5).即b(1.618)nsqrt(5),所以模运算的次数为O(Igb)以b为底数=O(Ig(2)b)一以2为底数，输入规模也可以看作是b的bh位数.习题2.27.对以下新古进行证明:(如果是错误的,请举例a.如果Nn)Wo(g(n),那么g(n)O(t(n)b.0.(g(n)=(g(n)解：a.这个断古是正确的.它指出如果t(n)的增长率小于或

8、等于g(n)的增长率,那么g(n)的培氏率大于或等于(三)的增长率由t(n)cg(nfora1.1.nn.wherec0(一)/()g()那么：CIbraHnNnOb.这个断言是正确的.只需证明(ag()u(g(MRg5)U=n0.c0f(n)ctg(n)ftwa1.1.n=Mc1.=c00即：f(n)(g(n)又设f(n)6(g(n).那么有：/()cg()fora1.1.n=nO.cOf()-ag(n)=c1.ag(n)afora1.1.n=11.c1.=c00UP：f(n)-)(tg(n)8.证明本节定理对于以下符号也成立：&Q符号b.。符号证明:aweneed(oproof(hatif

9、ti(n)0(g1.(n)andc2(n)Q(g2(n),then(1(n)=n1.,wherec1.0由c2(n)Q(g2(n),T2(n)c2g2(n)fora1.1.n=n2fcwherec20那么取c=minc1.c2).当n=maxn1.n2)Bf:t1.(nc1.g1.(n+c2g2(ncg1.(n)+cg2(n)c(g1.(n+g2(n)NCmaX1.g1.(n),g2(n)所以以命遨成立，bU(n)+2nW电(max(g】(),g2()证明：由大的定义知.必须确定常数c1.、c2和n.使得对于所有n=n.有：C1.maX他1(”).g2(”)”()+t2(n)max(g1.(),g2()由存在非负整数a1.*和id使：a1.4g1.(n)-(1)由I2(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)V=a21*g1.(n)+b2*g2(n)令c1.=nin(a1.,b1.),c2=max(a2,b2).那么C1.*(g1.+g2)=t1.(n)+t2(n)=c2(g1.+g2)-(3)不失一般性假设11ux(g1.(n).g2(n)=g1.(n).显然.gI(n