算法设计与分析第二版课后习题解答.docx
- 文档编号:14176395
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:36
- 大小:362KB
算法设计与分析第二版课后习题解答.docx
《算法设计与分析第二版课后习题解答.docx》由会员分享,可在线阅读,更多相关《算法设计与分析第二版课后习题解答.docx(36页珍藏版)》请在冰点文库上搜索。
算法设计与分析第二版课后习题解答
算法设计与分析基础课后练习答案
习题1.1
4.设计一个计算
的算法,n是任意正整数。
除了赋值和比较运算,该算法只能用到基本的四则运算操作。
算法求
//输入:
一个正整数n
2
//输出:
。
step1:
a=1;
step2:
若a*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<=m 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.2 1.(农夫过河) 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≠0 D←b*b-4*a*c IfD>0 temp←2*a x1←(-b+sqrt(D))/temp x2←(-b-sqrt(D))/temp returnx1,x2 elseifD=0return–b/(2*a) elsereturn“norealroots” else //a=0 ifb≠0return–c/b else //a=b=0 ifc=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=1 whilen! =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.3 1.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去. a.应用该算法对列表”60,35,81,98,14,47”排序 b.该算法稳定吗? c.该算法在位吗? 解: a.该算法对列表”60,35,81,98,14,47”排序的过程如下所示: b.该算法不稳定.比如对列表”2,2*”排序 c.该算法不在位.额外空间forSandCount[] 4.(古老的七桥问题) 第2章 习题2.1 7.对下列断言进行证明: (如果是错误的,请举例) 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,wherec>0 则: foralln≥n0 b.这个断言是正确的。 只需证明 。 设f(n)∈Θ(αg(n)),则有: foralln>=n0,c>0 foralln>=n0,c1=cα>0 即: f(n)∈Θ(g(n)) 又设f(n)∈Θ(g(n)),则有: foralln>=n0,c>0 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,wherec1>0 由t2(n)∈Ω(g2(n)), T2(n)≥c2g2(n) foralln>=n2,wherec2>0 那么,取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)∈Θ( 证明: 由大? 的定义知,必须确定常数c1、c2和n0,使得对于所有n>=n0,有: 由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+g2<2max(g1,g2) 又g2(n)>0,g1(n)+g2(n)>g1(n),即g1+g2>max(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.2 2.请用 的非正式定义来判断下列断言是真还是假。 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.3 1.计算下列求和表达式的值。 答: 3.考虑下面的算法。 a.该算法求的是什么? b.它的基本操作是什么? c.该基本操作执行了多少次? d.该算法的效率类型是什么? e.对该算法进行改进,或者设计一个更好的算法,然后指出它们的效率类型。 如果做不到这一点,请试着证明这是不可能做到的。 9.证明下面的公式: 可以使用数学归纳法,也可以像10岁的高斯一样,用洞察力来解决该问题。 这个小学生长大以后成为有史以来最伟大的数学家之一。 数学归纳法: 高斯的方法: 习题2.4 1.解下列递推关系(做a,b) 当n>1时 a. 解: 当n>1时 b. 解: 2.对于计算n! 的递归算法F(n),建立其递归调用次数的递推关系并求解。 解: 3.考虑下列递归算法,该算法用来计算前n个立方的和: S(n)=13+23+…+n3。 算法S(n) //输入: 正整数n //输出: 前n个立方的和 ifn=1return1 elsereturnS(n-1)+n*n*n a.建立该算法的基本操作次数的递推关系并求解 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=0return1 Elsereturnpower(n-1)+power(n-1) c. 8.考虑下面的算法 算法Min1(A[0..n-1]) //输入: 包含n个实数的数组A[0..n-1] Ifn=1returnA[0] Elsetemp←Min1(A[0..n-2]) Iftemp≤A[n-1]returntemp ElsereturnA[n-1] a.该算法计算的是什么? b.建立该算法所做的基本操作次数的递推关系并求解 解: a.计算的给定数组的最小值 foralln>1 n=1 b. 9.考虑用于解决第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≤temp2returntemp1 Elsereturntemp2 a.建立该算法所做的的操作次数的递推关系并求解 b.算法Min1和Min2哪个更快? 有其他更好的算法吗? 解: a. 习题2.5 3.java的基本数据类型int和long的最大值分别是 当n最小为多少的时候,第n个斐波那契数能够使下面的类型溢出。 a.int类型 b.long类型 4.爬梯子假设每一步可以爬一个或两格梯子,爬一部n格梯子一共可以用几种的不同方法? (例如,一部3格的梯子可以用三种不同的方法爬: 1-1-1,1-2和2-1)。 6.改进算法Fib,使它只需要? (1)的额外空间。 7.证明等式: 答: 数学归纳法证明 习题2.6 1.考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数. 算法SortAnalysis(A[0..n-1]) //input: 包含n个可排序元素的一个数组A[0..n-1] //output: 所做的关键比较的总次数 count←0 fori←1ton-1do v←A[i] j←i-1 whilej>0andA[j]>vdo count←count+1 A[j+1]←A[j] j←j+1 A[j+1]←v returncount 比较计数器是否插在了正确的位置? 如果不对,请改正. 解: 应改为: 算法SortAnalysis(A[0..n-1]) //input: 包含n个可排序元素的一个数组A[0..n-1] //output: 所做的关键比较的总次数 count←0 fori←1ton-1do v←A[i] j←i-1 whilej>0andA[j]>vdo count←count+1 A[j+1]←A[j] j←j+1 ifj>=0 count=count+1 A[j+1]←v returncount 习题3.1 4.a.设计一个蛮力算法,对于给定的x0,计算下面多项式的值: P(x)=anxn+an-1xn-1+…+a1x+a0 并确定该算法的最差效率类型. b.如果你设计的算法属于Θ(n2),请你为该算法设计一个线性的算法. C.对于该问题来说,能不能设计一个比线性效率还要好的算法呢? 解: a.AlgorithmsBruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p在给定点x的值 //输入: P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p在给定点x的值 p=0.0 fori=nto0do power=1 forj=1toido power=power*x p=p+P[i]*power returnp 算法效率分析: 基本操作: 两个数相乘,且M(n)仅依赖于多项式的阶n b.thaabovealgorithmsisveryinefficient,becausewerecompute powersofxagainandagainasiftherewerenorelationshipamongthem.Infact,wecanmovefromthelowesttermtothehighestandcomputexibyusingxi-1. AlgorithmsBetterBruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p在给定点x的值 //输入: P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p在给定点x的值 P=P[0] power=1 fori←1tondo power←power*x p←p+P[i]*power returnp 基本操作乘法运算总次数M(n): c.不行.因为计算任意一个多项式在任意点x的值,都必须处理它的n+1个系数.例如: (x=1,p(x)=an+an-1+..+a1+a0,至少要做n次加法运算) 5.应用选择排序对序列E,X,A,M,P,L,E按照字母顺序排序. 6.选择排序是稳定的吗? (不稳定) 7.用链表实现选择排序的话,能不能获得和数组版相同的Θ(n2)效率? Yes.Bothoperation—findingthesmallestelementandswappingit–canbedoneasefficientlywiththelinkedlistaswithanarray. 8.应用冒泡排序对序列E,X,A,M,P,L,E按照字母顺序排序. 9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可以停止了. b.结合所做的改进,为冒泡排序写一段伪代码. c.请证明改进的算法最差效率也是平方级的. Hints: a.第i趟冒泡可以表示为: 如果没有发生交换位置,那么: b.AlgorithmsBetterBubblesort(A[0..n-1]) //用改进的冒泡算法对数组A[0..n-1]排序 //输入: 数组A[0..n-1] //输出: 升序排列的数组A[0..n-1] count←n-1 //进行比较的相邻元素对的数目 flag←true //交换标志 whileflagdo flag←false fori=0tocount-1do
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 第二 课后 习题 解答