斐波那契数列

斐波那契数列，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)。

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

代码语言：javascript复制

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以上需要很久才出得来结果
    }
}

dp return 递归 动态规划 基础

0 人点赞