java实现Fibonacci算法实例

接下来我将为您详细讲解Java实现Fibonacci算法实例的攻略。

什么是Fibonacci数列

Fibonacci数列是指：1、1、2、3、5、8、13、21、34……从第三个数开始，每一个数都等于它前面两个数之和。在数学上，Fibonacci数列以如下递推式定义：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)

实现Fibonacci算法

递归法实现Fibonacci算法

递归是最常用的实现Fibonacci数列的方法，它很好理解，但是在计算较大的Fibonacci数列时，会存在重复计算，导致时间复杂度较高。

public static int fibonacciByRecursion(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n should >= 0");
    }
    if (n < 2) {
        return n;
    }
    return fibonacciByRecursion(n - 1) + fibonacciByRecursion(n - 2);
}

优化的递归法实现Fibonacci算法

通过记忆化搜索和DP动态规划，可以避免递归过程中的重复计算，提高效率。

记忆化搜索

public static int fibonacciByMemoization(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n should >= 0");
    }

    int[] memory = new int[n + 1];
    Arrays.fill(memory, -1);

    return fibonacciByMemoization(n, memory);
}

private static int fibonacciByMemoization(int n, int[] memory) {
    if (memory[n] != -1) {
        return memory[n];
    }

    if (n < 2) {
        return n;
    }

    memory[n] = fibonacciByMemoization(n - 1, memory) + fibonacciByMemoization(n - 2, memory);
    return memory[n];
}

DP动态规划

public static int fibonacciByDP(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n should >= 0");
    }

    if (n < 2) {
        return n;
    }

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

示例说明

示例1

假设现在要求第10个Fibonacci数。

int result = fibonacciByRecursion(10);
System.out.println("Fibonacci(10) = " + result);
result = fibonacciByMemoization(10);
System.out.println("Fibonacci(10) = " + result);
result = fibonacciByDP(10);
System.out.println("Fibonacci(10) = " + result);

输出结果：

Fibonacci(10) = 55
Fibonacci(10) = 55
Fibonacci(10) = 55

示例2

当 n = -1 时，会抛出异常。

fibonacciByRecursion(-1);
// IllegalArgumentException: n should >= 0

fibonacciByMemoization(-1);
// IllegalArgumentException: n should >= 0

fibonacciByDP(-1);
// IllegalArgumentException: n should >= 0

总结

本文通过例子介绍了Java实现Fibonacci算法的方法，并给出了具体的实现示例。其中递归法是最常用的实现Fibonacci数列的方法，虽然容易理解，但是在计算较大的Fibonacci数列时会存在重复计算，导致效率较低。记忆化搜索和DP动态规划可以在一定程度上避免递归过程中的重复计算，提高效率。