解：
3. 考虑下列递归算法，该算法用来计算前n个立方的和：S(n)=13+23+…+n3。 算法S(n)
//输入：正整数n
//输出：前n个立方的和 if n=1 return 1
else return S(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的值 If n=0 return 1
Else return power(n-1)+ power(n-1)
c.
C(n)??2i?2n?1?1
i?0n8.考虑下面的算法
算法 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)??
0?for 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. 习题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
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