剑指offer-斐波那契数列

剑指offer-斐波那契数列

class Solution {
  public:
    int Fibonacci(int n) {
        if ( n == 0) return 0;
        if ( n == 1) return 1;
        int first = 0, second = 1, third = 1;
        for (int i = 2; i <= n; ++i) {//当然也可以只设置两个数，那么i就要从1开始遍历
            third = first + second;//最后输出的数
            first =  second;//更新第一个数
            second = third;//更新第二个数
        }
        return third;
    }

class Solution {
  public:
    int Fibonacci(int n) {
        if (n == 1 || n == 2) {
            return  1;
        } else {
            return  Fibonacci(n - 1) + Fibonacci(n - 2);//公式
        }
    }
};//费时

f(1)=f(2)=1,f(n)=f(n-1)+f(n-2);