a.
?x(n)?x(n?1)?5?当n>1时
?x(1)?0解：
b. ?x(n)?3x(n?1) ?当n>1时
?x(1)?4解：
2. 对于计算n!的递归算法F(n)，建立其递归调用次数的递推关系并求解。 解：
3. 考虑下列递归算法，该算法用来计算前n个立方的和：S(n)=13+23+…+n3。算法S(n)
//输入：正整数n
//输出：前n个立方的和 if n=1 return 1
6
else return S(n-1)+n*n*n
a. 建立该算法的基本操作次数的递推关系并求解
b. 如果将这个算法和直截了当的非递归算法比，你做何评价？ 解： a.
7. a. 请基于公式2n=2n-1+2n-1，设计一个递归算法。当n是任意非负整数的时候，该算法能够计算2n的值。
b. 建立该算法所做的加法运算次数的递推关系并求解
c. 为该算法构造一棵递归调用树，然后计算它所做的递归调用次数。 d. 对于该问题的求解来说，这是一个好的算法吗？ 解:
a.算法power(n)
//基于公式2n=2n-1+2n-1,计算2n //输入:非负整数n //输出: 2n的值 If n=0 return 1
Else return power(n-1)+ power(n-1)
7
c. nC(n)??2i?0i?2n?1?1 8.考虑下面的算法 算法 Min1(A[0..n-1]) //输入:包含n个实数的数组A[0..n-1] If n=1 return A[0] Else temp←Min1(A[0..n-2]) If temp≤A[n-1] return temp Else return A[n-1] a.该算法计算的是什么? b.建立该算法所做的基本操作次数的递推关系并求解 解: a.计算的给定数组的最小值 ?C(n?1)?1b.C(n)?? ?0for all n>1 n=1 9.考虑用于解决第8题问题的另一个算法,该算法递归地将数组分成两半.我们将它称为Min2(A[0..n-1]) 算法 Min(A[r..l]) If l=r return A[l] Else temp1←Min2(A[l..(l+r)/2]) Temp2←Min2(A[l..(l+r)/2]+1..r) If temp1≤temp2 return temp1 Else return temp2 a.建立该算法所做的的操作次数的递推关系并求解 b.算法Min1和Min2哪个更快?有其他更好的算法吗? 解: a. 8
习题2.6
1. 考虑下面的排序算法,其中插入了一个计数器来对关键比较次数进行计数.
算法SortAnalysis(A[0..n-1])
//input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0
for i←1 to n-1 do v←A[i] j←i-1
while j>0 and A[j]>v do count←count+1 A[j+1]←A[j] j←j+1 A[j+1]←v return count
比较计数器是否插在了正确的位置?如果不对,请改正. 解:应改为:
算法SortAnalysis(A[0..n-1])
//input:包含n个可排序元素的一个数组A[0..n-1] //output:所做的关键比较的总次数 count←0
for i←1 to n-1 do v←A[i] j←i-1
while j>0 and A[j]>v do count←count+1 A[j+1]←A[j] j←j+1
if j>=0 count=count+1 A[j+1]←v return count
9
习题3.1 4. a.设计一个蛮力算法,对于给定的x0,计算下面多项式的值: P(x)=anxn+an-1xn-1+…+a1x+a0 并确定该算法的最差效率类型. b.如果你设计的算法属于Θ(n2),请你为该算法设计一个线性的算法. C.对于该问题来说,能不能设计一个比线性效率还要好的算法呢? 解: a. Algorithms BruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p在给定点x的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p在给定点x的值 p=0.0 for i=n to 0 do power=1 for j=1 to i do power=power*x p=p+P[i]*power return p 算法效率分析: 基本操作:两个数相乘,且M(n)仅依赖于多项式的阶n ninM(n)??i?0?1?j?1?i?0i?n(n?1)2??(n) 2b. tha above algorithms is very inefficient, because we recompute powers of x again and again as if there were no relationship among them.In fact ,we can move from the lowest term to the highest and compute xi by using xi-1. Algorithms BetterBruteForcePolynomialEvaluation(P[0..n],x) //由高幂到低幂用蛮力法计算多项式p在给定点x的值 //输入:P[0..n]是多项式按低幂到高幂的常系数,以及定值x //输出: 多项式p在给定点x的值 P=P[0] power=1 for i←1 to n do power←power*x p←p+P[i]*power return p 基本操作乘法运算总次数M(n): nM(n)??2?2n??(n) i?1c.不行.因为计算任意一个多项式在任意点x的值,都必须处理它的n+1 个系数.例如: (x=1,p(x)=an+an-1+..+a1+a0,至少要做n次加法运算) 5.应用选择排序对序列example按照字母顺序排序. 10