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

斐波那契数列是一个经典的数学序列，其中每个数字是前两个数字的和。下面是使用Java分别设计和实现四种常见求解斐波那契数列的方法：

1. **迭代法**（简单循环）

public class FibonacciIterative {
    public int fibonacci(int n) {
        if (n <= 0) return 0;
        if (n == 1 || n == 2) return 1;
        int a = 0, b = 1;
        for (int i = 3; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

2. **递归法**

public class FibonacciRecursive {
    public int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

3. **矩阵快速幂法**（更高效，适用于大数值计算）

public class FibonacciMatrixPower {
    public int fibonacci(int n) {
        int[][] base = {{1, 1}, {1, 0}};
        if (n <= 1) return n;
        power(base, n - 1);
        return base[0][0];
    }

    private void power(int[][] matrix, int pow) {
        int[][] result = new int[2][2];
        result[0][0] = result[1][1] = 1;
        while (pow > 0) {
            if ((pow & 1) != 0) {
                multiply(result, matrix);
            }
            multiply(matrix, matrix);
            pow >>= 1;
        }
    }

    private void multiply(int[][] a, int[][] b) {
        int c00 = a[0][0] * b[0][0] + a[0][1] * b[1][0];
        int c01 = a[0][0] * b[0][1] + a[0][1] * b[1][1];
        int c10 = a[1][0] * b[0][0] + a[1][1] * b[1][0];
        int c11 = a[1][0] * b[0][1] + a[1][1] * b[1][1];

        a[0][0] = c00;
        a[0][1] = c01;
        a[1][0] = c10;
        a[1][1] = c11;
    }
}

4. **备忘录法**（避免重复计算，提高效率）

import java.util.HashMap;

public class FibonacciMemoization {
    private HashMap<Integer, Integer> memo = new HashMap<>();

    public int fibonacci(int n) {
        if (n <= 0) return 0;
        if (n == 1 || n == 2) return 1;
        if (memo.containsKey(n)) return memo.get(n);
        int fib = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, fib);
        return fib;
    }
}