斐波那契数列，1，1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89， 144,.
如果设F(n)为该数列的第n 项( n ∈N* )，那么数列有如下形式，F(n)=F(n-1)+F(n 2)。

编写程序求出用户指定项数位置的数字。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class test1 {

    public static long Fibonacci1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return Fibonacci1(n - 1) + Fibonacci1(n - 2);
    }

    public static long Fibonacci2(int n, long[] dp) {
        if (dp[n] != 0)
            return dp[n];
        if (n == 1 || n == 2) {
            return dp[n] = 1;
        }
        return dp[n] = Fibonacci2(n - 1, dp) + Fibonacci2(n - 2, dp);
    }

    public static long Fibonacci3(int n) {
        long y1 = 1, y2 = 1, y3 = 1;
        for (int i = 3; i <= n; ++i) {
            y3 = y1 + y2;
            y1 = y2;
            y2 = y3;
        }
        return y3;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n = cin.nextInt();
        long[] dp = new long[n + 1];
        cin.close();
        System.out.println("循环版本斐波那契:" + Fibonacci3(n)); // 循环版本斐波那契，最好
        System.out.println("递归带动态规划的斐波那契:" + Fibonacci2(n, dp)); // 递归带动态规划的斐波那契，次之
        System.out.println("递归基础版本斐波那契:" + Fibonacci1(n)); // 递归基础版本斐波那契，最差，到45以上需要很久才出得来结果
    }
}


========================================Talk is cheap, show me the code=======================================