题目描述

斐波那契数列：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0），n<=39。

思路一

利用函数的递归来做。将第0个到第n个裴波那契数列元素都求出来，存在数组中。

代码

class Solution {

public:

    int Fibonacci(int n) {

        int Fibonacci_array[n];

        Fibonacci_array[0] = 0;

        Fibonacci_array[1] = 1;

        for(int i = 2; i <= n; i++){

            Fibonacci_array[i] = Fibonacci_array[i-1] + Fibonacci_array[i-2];

        }

        return Fibonacci_array[n];

    }

}

思路二

用三个变量，第一个变量和第二个变量分别存放0、1两个值，第三个变量用来存放前两项的相加值。

class Solution {

public:

    int Fibonacci(int n) {

        int first = 0,

             second = 1,

             result = 1;

        if (n < 2) {

            return n;

        }

        for (int i = 2;i < n;i ++){

                first = second;

                second = result;

                result = first + second;

        }

        return result;

    }

}