[编程题]斐波那契数列

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

斐波那契数列，是n = 0，值为0；n=1，值为1；n = 2，值为1；n = 3，值为2；当n >= 2时，值为前两个值的和。f(n) = f(n-1)+f(n-2);

实现方案如下,利用循环来实现；利用递归实现时，层数太深效率不高

class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0)
        {
            return 0;
        }
        else if(n == 1 || n ==2)
        {
            return 1;
        }
        else
        {
            int prepre = 0;
            int pre = 1;
            int result = 0;
            for(int i = 2; i <=n; ++i)
            {
                result = prepre+pre;
                prepre = pre;
                pre = result;
            }
            return result;
            //return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
};