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

习题1.15.证明等式gcd(m.n>=gcd(n.mn(1.n)对每一对正整数m.n都成立.Hint:根据除法的定义不难证明：如果d整除U和V.那么d一定能整除u±v;加果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)=gc<1.(n.r)6.时于第一个数小于第二个数的一对数字,欧几里得打法利会如何处理?该尊:法在处埋这种输入的过程中,上述情况最多会发生几次？Him：对于任何形如(K=mvn的一对数字.Euc1.id算法在第一次登代时交换m和n.即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.Za.对于所有IWm.n这10的输入.Euc1.id算法最少要做几次除法?(1次)b.对于所有IWmmWIO的输入,Euc1.k1.亢法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)PggPWgWPwcucPwgcPwgcw、cPwcCPgcgPgP-农夫W狼G山羊C一白菜2.(过桥问题)7,1.22/,2.5,105.1(1/,1.2.5.10(。)，.;，13)(15)7,12-17)/,1.2.5.105f1.()/,1.5,101125.10-分别代表4个人.J手电筒4 .对于任意实系数a.b.c.某个算法能求方程ax2÷bx+c=0的实根,写出上述算法的伪代码(可以假设Sqrt(x)是求平方根的函数)算法QUadra1.iC(a.b.c)“求方程ax2+bx+c=()的实根的算法“4ft入:实系数ahc"输出;实根或者无解信息IfaOD-b*h-4*acIfDX)temp*-2*ax1.-(-b+sqrt(D)tempx2(-b-sqrt(D)>'tcmpreturnx1.,x2e1.seifD=Oreturn-M2*a)e1.serc(um"norea1.Isme1.se/a=f1.ifb0return-cbe1.se/a=b=Oifc=0return,fcnrea1.numbers*e1.sereturn,wnorea1.roots”5 .描述将十进制整数表达为.进制整数的标准算法必用文字描述b.用伪代码描述解答:今将十进制整数转换为：进制整数的修法输入：一个正整数n输出，正整数n相应的二进制数第一步：用n除以2.余数赋给Ki(i三<M2.),商赋给n第二步；如果n=0,那么到第三步，否那么重或第一步第三步：将Ki按照i从高到低的Itfi席输出b.伪代码眸法DecoBin(n)“将I进制整数n转换为二进制整数的算法陷入:正整数nMfi出:该正整数相应的二进制数,该数存放于数组BinU.n中i=1.whi1.en!=4)do(Bini=n%2;n=(int)n2;i+：>whi1.ei!=()doprintBini;i9.考虑下面这个算法.它求的是数组中大小相差最小的两个元素的差(算法略)对这个究法做尽可能多的改良.算法MinDistance(O.n-1)“输入:数组A(0.n-1.)"输出:thesma1.1.estdistancedbetweentwoofitse1.ementsdmin<fori<0ton2doforJ4i+1.ton-Idotemp44ijiftemp<dmindmin-tempreturndmin习题1.3考虑这样一个排序算法,该算法对于待持序的数组中的姆一个元素,计算比它小的元素个数,然后利用这个信息.将各个元素放到有序数祖的相应位置上去.foriOton1doCounti*Ofort<Oton-2doforj<i÷1ton-1doifi<AjCcnntjCountj+1e1.seCountiCounti+1for£Oton1doSCunfi<Aia.应用该算法对列表”60,3531.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该辞法不在位.额外空间fbrSa1.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.ueofthearray'sc1.emcn(c.g.,0foranarrayofpositivenumbers)tomark(heithpositionisenp<y.(*1.az>de1.e<ion">习题2.1欧几里得竟法的时间复杂度欧几里得笄法,又称混转相除法.用于求两个自然数的最大公约数.算法的思想很简单,基于卜面的数论等式gc<1.(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<i(b.amodb):endfunction欧几里得究法是最古老而般典的宛法，埋解和掌提这一尊法并不难，但要分析它的时间及杂度却并不容易,我们先不考虑模运算本身的时间经杂度(算术运算的时间发杂度在Knu1.h的TAOCP中有详细的讨论).我们只考虑这样的问题：欧几里得算法花球坏情况卜所需的模运蚌次数和添入的a利b的大小有怎样的关系？我们不妨设Qb>=1.(假设a<b我们只需多整一次模运算.假设b=0或a=b模运豫的次数分别为。和1).构造数歹Jun:UO=a.u1.=b.uk=uk-2moduk-1.(k>=2).显然.假设算法需要n次模运算.那么行Un=SCd(a.b).un+1.=O.我们比拟数列un)和班波那奥数列Fn,R)-<=un,F1.=1.<=un-1,又因为由Ukmoduk+1.=uk+2,11IfJuk>=uk+1.+uk+2,由数学归嗨去容易得到uk>=Fnk.于是得到a=uO>=Fn,b=uO>=Fn1.,也就是说如果欧几里得以法需要做n次模运算,班么b必定不小于Fn-1.换句话说,假设b<Fn-1.那么算法所需模运算的次数必定小于n.根据菲波那契数列的性质，有Fn-ii.618>n/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)的增长率小于或等于g(n)的增长率,那么g(n)的培氏率大于或等于(三)的增长率由t(n)cg(n>fora1.1.nn.wherec>0(一)/(«)g(")那么：CIbraHnNnOb.这个断言是正确的.只需证明(ag()u(g(MRg5)U<9(砥5)。设f(nC6(g(n)JE么有：f(n)cag(n)fora1.n>=n0.c>0f(n)ctg(n)ftwa1.1.n>=Mc1.=c0>0即：f(n)(g(n)又设f(n)6(g(n).那么有：/()cg()fora1.1.n>=nO.c>Of()-ag(n)=c1.ag(n)afora1.1.n>=11.c1.=c0>0UP：f(n)¢-)(tg(n)8.证明本节定理对于以下符号也成立：&Q符号b.。符号证明:a«weneed(oproof(hatifti(n)0(g1.(n)andc2(n)Q(g2(n),then(1(n)÷<2(n)(max(g1.(n)g2(n)«由t1.(n)WQ(g1.g)ti(n)c1.g1.(n)fora1.1.n>=n1.,wherec1.>0由c2(n)Q(g2(n),T2(n)c2g2(n)fora1.1.n>=n2fcwherec2>0那么取c>=minc1.c2).当n>=maxn1.n2)Bf:t1.(n>÷<2(n>>c1.g1.(n>+c2g2(n>>cg1.(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)<=t1.(n><=a2*'g1.(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