用Java设计并实现四种求解斐波那契数列的算法

斐波那契数列是一个经典的数列，其中每个数字都是前两个数字之和。以下是四种在Java中实现斐波那契数列的不同算法：

1. **递归法**：

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

递归虽然简洁，但对于大数值会非常慢，因为它会有大量的重复计算。

2. **循环迭代法**（也叫动态规划）：

public int fibonacciIterative(int n) {
    if (n <= 0) return 0;
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int temp = a;
        a = b;
        b = temp + b;
    }
    return a;
}

这种方法避免了递归带来的效率损失，时间复杂度是O(n)。

3. **矩阵快速幂法**（适合较大的n值）：
首先需要将斐波那契转换成矩阵乘法形式，然后利用矩阵快速幂的思想加速计算。这个过程涉及到矩阵乘法和取模运算，但可以显著提高效率。

public int fibonacciMatrix(int n) {
    // ... 矩阵乘法和快速幂的代码 ...
}

4. **预计算存储法**：
只计算并存储前几个斐波那契数，后续需要时直接查找，适用于需要多次查询的情况。

public class FibonacciCache {
    private static final int[] cache = new int[100];
    public static int fibonacci(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (cache[n] != 0) return cache[n];
        // 计算并存储结果
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        cache[n] = result;
        return result;
    }
}