算法 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
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 习题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 M(n)???1??i?i?0j?1i?0ninn(n?1)??(n2) 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
