斐波那契数列

题目描述:

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

思路

第一种思路

首先我们要知道什么是斐波那契数列： 斐波那契数列的 an = an-1 +an-2;
我们首先想到的是递归，两行代码就能使用递归实现，但是如果n太大就会出现溢出，虽然能实现但是效果不理想

第二种思路

利用循环实现，依然是利用an = an-1 +an-2这个公式，依次推导，选出a0 = 0 ，a1=1,然后依次计算

第三种思路：

大佬们说动态规划。。。我不是很懂，明天了解了解什么是动态规划再回来看这个解法

代码实现

第一种思路

public class Main {
    public static void main(String[] args) {
        int n=40;
        System.out.println(Fibonacci(n));
    }
    public static int Fibonacci(int n) {
        if(n<=1) return n;
        else return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

第二种思路

public class Main {
    public static void main(String[] args) {
        int n=40;
        System.out.println(Fibonacci(n));
    }
    public static int Fibonacci(int n) {
        int f = 0,g =1;
        int temp ;
        if(n==1) return 1;
        if(n==0) return 0;
        while (n>1)
        {
            n--;
            temp = g;
            g = f + g;
            f = temp;
        }
        return g;
    }
}