计算机问题求解一论题3-1 动态规划 2016年08月31日
计算机问题求解 – 论题3-1 - 动态规划 2016 年08 月31 日
Fibonacci:F=F+Fn2 问题1: 如果要你计算第n个 Fibonacci数,你用递归还是 用循环,还是随便?为什么?
递归可能代价高昂 计算第n个Fibonacci数 其实可以在线性时间内 - (以加法次数计量)完成。 6 18 23 3 3 16 24 25 21 10 但如果采用递归,递归 调用的次数是2Fn+1~1
递归可能代价高昂 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 4 3 3 3 6 5 4 13 16 10 11 9 8 12 3 4 5 6 7 14 15 21 2 1 19 18 17 25 23 24 22 20 计算第 n个Fibonacci数 其实可以在线性时间内 (以加法次数计量)完成。 但如果采用递归,递归 调用的次数是 2 Fn+1-1
问题2 相比较快速排序的分治法递 归,为什么上面的例子采用 递归代价高昂? QUICKSORT(A,p,r) 1 if p<r 2 g PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A,g+1,r)
问题3 我们有什么办法来应对这种 情沉? “用循环解决斐波拉契数列 的方案给我们什台启发?