《算法设计与分析课后习题解答》由会员分享，可在线阅读，更多相关《算法设计与分析课后习题解答（38页珍藏版）》请在金锄头文库上搜索。
1、 算法设计与分析基础课后练习答案习题1.1 4.设计一个计算的算法，n是任意正整数。除了赋值和比较运算，该算法只能用到基本的四则运算操作。算法求 /输入：一个正整数n2 /输出：。step1:a=1； step2:若a*an 转step 3，否则输出a； step3:a=a+1转step 2；5. a用欧几里德算法求gcd（31415，14142）。 b. 用欧几里德算法求gcd（31415，14142）,比检查minm，n和gcd（m，n）间连续整数的算法快多少倍？请估算一下。a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618)
2、=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每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于114142 和 214142之间，所以欧几里德算法比此算法快114142/11 1300 与 214142/11 2600 倍之间。6.证明等式gcd(m,
3、n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明: l 如果d整除u和v, 那么d一定能整除uv; l 如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任
4、何形如0=m0 temp2*a x1(-b+sqrt(D)/temp x2(-b-sqrt(D)/temp return x1,x2 else if D=0 return b/(2*a) else return “no real roots”else /a=0 if b0 return c/b else /a=b=0 if c=0 return “no real numbers” else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n输出：正整数n相应
5、的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2.)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码 算法 DectoBin(n)/将十进制整数n转换为二进制整数的算法/输入：正整数n/输出：该正整数相应的二进制数，该数存放于数组Bin1.n中i=1while n!=0 do Bini=n%2;n=(int)n/2;i+;while i!=0 doprint Bini;i-;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进.算法 MinDistance(A0.n-1)/输入:数
6、组A0.n-1/输出:the smallest distance d between two of its elements习题1.3 1. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count4.(古老的七桥问题)第2章习题2.1 7
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)cg(n) for all nn0, where c0 则： for all nn0b. 这个断言是正确的。只需证明。设f(n)(g(n),则有： for all n=n0, c0 for all n=n0, c1=c0即：f(n)(g(n)又设f(n)(g(n),则有： for all n=n0,c0 for all n
8、=n0,c1=c/0即：f(n)(g(n)8证明本节定理对于下列符号也成立：a.符号b.符号证明：a。we need to proof that if t1(n)(g1(n) and t2(n)(g2(n), then t1(n)+ t2(n)(maxg1(n), g2(n)。由 t1(n)(g1(n)， t1(n)c1g1(n) for all n=n1, where c10由 t2(n)(g2(n)， T2(n)c2g2(n) for all n=n2, where c20那么，取c=minc1,c2,当n=maxn1,n2时： t1(n)+ t2(n)c1g1(n)+ c2g2(n) c
9、 g1(n)+c g2(n)cg1(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=
10、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+g20，g1(n)+g2(n)g1(n),即g1+g2max(g1,g2)。则（3）式转换为：C1*max(g1,g2) = t1(n)+t2(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)答
11、：c假，其它真。5.按照下列函数的增长次数对它们进行排列（按照从低到高的顺序） (n2)!, 5lg(n+100)10, 22n, 0.001n4+3n3+1, ln2 n, ， 3n.答：习题2.31. 计算下列求和表达式的值。答：3. 考虑下面的算法。a 该算法求的是什么？b 它的基本操作是什么？c 该基本操作执行了多少次？d 该算法的效率类型是什么？e 对该算法进行改进，或者设计一个更好的算法，然后指出它们的效率类型。如果做不到这一点，请试着证明这是不可能做到的。9.证明下面的公式：可以使用数学归纳法，也可以像10岁的高斯一样，用洞察力来解决该问题。这个小学生长大以后成为有史以来最伟大的
12、数学家之一。数学归纳法：高斯的方法：习题2.41. 解下列递推关系 （做a,b）当n1时a. 解：当n1时b.解：2. 对于计算n!的递归算法F(n)，建立其递归调用次数的递推关系并求解。解：3. 考虑下列递归算法，该算法用来计算前n个立方的和：S(n)=13+23+n3。算法S(n) /输入：正整数n /输出：前n个立方的和if n=1 return 1else return S(n-1)+n*n*na. 建立该算法的基本操作次数的递推关系并求解b. 如果将这个算法和直截了当的非递归算法比，你做何评价？解：7. a. 请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值。 b. 建立该算法所做的加法运算次数的递推关系并求解 c. 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。 d. 对于该问题的求解来说，这是一个好的算法吗？解:a.算法power(n)/基于公式2n=2n
