算法设计与分析课后习题解答

算法设计与分析基础课后练习答案习题1.14.设计一个计算错误!未找到引用源。的算法，n是任意正整数。除了赋值和比较运算，该算法只能用到基本的四则运算操作。算法求错误!未找到引用源。//输入：一个正整数n错误!未找到引用源。2//输出：。step1:a=1；step2:若a*an转step3，否则输出a；step3:a=a+1转step2；5.a．用欧几里德算法求gcd（31415，14142）。b.用欧几里德算法求gcd（31415，14142）,比检查min｛m，n｝和gcd（m，n）间连续整数的算法快多少倍？请估算一下。a.gcd(31415,14142)=gcd(14142,3131)=gcd(3131,1618)=gcd(1618,1513)=gcd(1513,105)=gcd(1513,105)=gcd(105,43)=gcd(43,19)=gcd(19,5)=gcd(5,4)=gcd(4,1)=gcd(1,0)=1.b.有a可知计算gcd（31415，14142）欧几里德算法做了11次除法。连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142和2·14142之间，所以欧几里德算法比此算法快1·14142/11≈1300与2·14142/11≈2600倍之间。6.证明等式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)7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0=mn的一对数字,Euclid算法在第一次叠代时交换m和n,即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.8.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//输出:实根或者无解信息Ifa≠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]//输出:thesmallestdistancedbetweentwoofitselements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a.该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间forSandCount[]4.(古老的七桥问题)第2章习题2.17.对下列断言进行证明:(如果是错误的,请举例)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))，T2(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时上述不等式成立。证毕。习题2.22.请用错误!未找到引用源。的非正式定义来判断下列断言是真还是假。a.n(n+1)/2∈O(n3)b.n(n+1)/2∈O(n2)c.n(n+1)/2∈Θ(n3)d.n(n+1)/2∈Ω(n)答：c假，其它真。5.按照下列函数的增长次数对它们进行排列（按照从低到高的顺序）(n−2)!,5lg(n+100)10,22n,0.001n4+3n3+1,ln2n,错误!未找到引用源。，3n.答：习题2.31.计算下列求和表达式的值。答：3.考虑下面的算法。a．该算法求的是什么？b．它的基本操作是什么？c．该基本操作执行了多少次？d．该算法的效率类型是什么？e．对该算法进行改进，或者设计一个更好的算法，然后指出它们的效率类型。如果做不到这一点，请试着证明这是不可能做到的。9.证明下面的公式：可以使用数学归纳法，也可以像10岁的高斯一样，用洞察力来解决该问题。这个小学生长大以后成为有史以来最伟大的数学家之一。数学归纳法：高斯的方法：习题2.41.解下列递推关系（做a,b）a.解：b.解：0)1(5)1()(xnxnx4)1()1(3)(xnxnx当n1时当n1时2.对于计算n!的递归算法F(n)，建立其递归调用次数的递推关系并求解。解：3.考虑下列递归算法，该算法用来计算前n个立方的和：S(n)=13+23+…+n3。算法S(n)//输入：正整数n//输出：前n个立方的和ifn=1return1elsereturnS(n-1)+n*n*na.建立该算法的基本操作次数的递推关系并求解b.如果将这个算法和直截了当的非递归算法比，你做何评价？解：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.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])foralln1n=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≤temp2returntemp1Elsereturntemp2a.建立该算法所做的的操作次数的递推关系并求解b.算法Min1和Min2哪个更快?有其他更好的算法吗?解:a.习题2.53.java的基本数据类型int和long的最大值分别是错误!未找到引用源。当n最小为多少的时候，第n个斐波那契数能够使下面的类型溢出。a.int类型b.long类型4.爬梯子假设每一步可