【Java面试题】斐波那契数列

【题目】：

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

【示例】：

从0开始的斐波那契数列(0+1+1+2+3+5+…)，

输入n=2

找出该数列的第2项

结果：1

【关键点】： 斐波那契数列（两数之和）、非递归

注意：n 的取值范围

【Java】：

public class Solution {
    public int Fibonacci(int n) {
        if(n==0)return 0;//0
        if(n==1)return 1;//0+1
        if(n>1){//0+1+1
            int a = 1;
            int b = 1;
            int c = a;
            while (n > 2)//0+1+1+2+...
            {
                c = a + b;//从第三个数开始，斐波那契数等于前两个数的和；
                a = b;//将前一个数给到a，开始下一次求值
                b = c;//将斐波那契数给b，开始下一次求值
                n--;//每求一次，n都要减一
            }
            return c;
        }
        return -1;
    }
}

迭代 (耗时长，但最简单)

    public int Fibonacci(int n) {
        if(n<=0)return 0;//0
        if(n==1)return 1;//0+1
        return Fibonacci(n-1)+Fibonacci(n-2);
    }