一题一算法2018-02-09（斐波那契数列）

题目：斐波那契数列

题目描述：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

题目思考：

首先，我们需要知道的是斐波那契数列是什么？

image.png

既然我们知道了什么事斐波那契数列，那我们最先想到的方法就是通过数列的通项公式，通过递归的方式来计算n的对应值F(n).

题目思路一：

最简单最之际的方法，也是我们最先想到的，但是却是最不推荐的，通过递归的方式，这种方式占用时间和内存都不是最优的。

class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 0) return 0;
        if(n == 1|| n == 2) return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
};

题目思路二：

题目思考中的方式，通过中间变量的，迭代循环，不断叠加，最终计算出数据结果。

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        
        int temp1 = 0,temp2 = 1;
        int result = 0;
        for(int i = 2; i<= n; i++){
            result = temp1 + temp2;
            temp1 = temp2;
            temp2 = result;
        }
        return result;
    }
};

题目思路三：

在网上看的，动态规划的方式，我自习看了一下，其实和递归循环的方式有些类似，唯一的差别就是将中间存贮结果的变量省略，通过两个数据加减实现最终的这个算法。

方式一：
class Solution {
public:
    int Fibonacci(int n) {
        int f = 0, g = 1;
        while(n--){
            g =  g + f;
            f = g - f;
        }
        return f;
    }
};

方式二：
class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 0) return 0;
        int f = 0, g = 1;
        while(n-- > 1){
            g =  g + f;
            f = g - f;
        }
        return g;
    }
};

两种方式的差别在于返回的是g还是f：
第一种代码其实多循环了一次，最终的结果是n的下一阶，所以我们没有输出g，而是输出f。
第二种代码就是正合适的循环次数，最终结果就是n，所以我们就输出g，而不是输出f。