`

迭代法

 
阅读更多
fibonacci数列这个例子够出名吧?(以下代码未经测试)
首先来看一下递归函数:
int fibonacci(int n){
    if(0 == n || 1 == n)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}
这是自顶向下求的,要求f[n],就递归地去求f[n-1]和f[n-2],一直递归到边界条件(n为0或1,那时后再不断的往上回溯,得出答案。

但是来观察一下,假设计算f[4]:
                f[4]
               /   \
              /     \
             /       \
           f[3]      f[2]
          / \         / \         
         /   \       /   \
        /     \     /     \
      f[2]   f[1]  f[1]   f[0]

对于这个例子来说,递归不好,因为很多节点被重复计算了好多次,像f[2]就被计算了2次,f[1],f[0]就更多了。

如果改成迭代呢,效果会怎么样?
因为f[n] = f[n - 1] + f[n - 2];
在这题里迭代其实是一个自底向上的运算过程,避免了重复运算。
开始就使f[0] = f[1] = 1;
那么f[2] = f[1] + f[0];
    f[3] = f[2] + f[1];
    f[4] = f[3] + f[2];
    ....
    f[n] = f[n - 1] + f[n - 2];
由前开始往后算,那么我们就很容易写出以下代码:
f[0] = f[1] = 1;
for(int i = 2; i <= n; i++)
    f[i] = f[i - 1] + f[i - 2];
这就是一个完整的由前往后迭代的过程。
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics