《剑指offer》c++版本 10. 斐波那契数列

如题：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

这道题基本上学过算法的人都直到，斐波那契数列即，即1，1，2，3，5.......

用数学公式描述即 f(n) = f(n-1) + f(n-2)，很多教科书上都提供了递归算法，虽然，能够满足，但是效率是在太低了，存在大量重复计算，比如，计算f(5)的时候，需要计算f(4)和f(3)，计算f(6)的时候，需要计算f(4)和f(5)，显然，f(4)和f(5)重复计算了，随着n的增大，重复计算量越来越多。

为了减少重复计算量，此题最好的方式是使用循环法，不仅仅是此题，平常运用递归求解问题的时候，也要注意是否存在重复计算，如果存在的话，则需使用循环法求解。再循环体中保存前一步得到的值即可。思想上有点类似dp动态规划。

此题变种有很多，例如，青蛙跳台阶，仔细分析，本质上也是求斐波那契数列问题。

本题的c++解法如下：

//f(n) = f(n-1) + f(n-2);
class Solution {
public:
    int Fibonacci(int n) {
        int i = 3, v1 = 1, v2 = 1, val;
        
        //特殊情况处理
        if (n < 1)
            return 0;
        if (n < 3)
            return 1;
        
         //循环求解，保存上一步得到的值
         while (i <= n)
         {
             val = v1 + v2;
             v1 = v2;
             v2 = val;
             i++;
         }
         return val;
    }
};

=============================================================================================

Linux应用程序、内核、驱动、后台开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。