斐波那契数列，Java版本实现

斐波那契数列是一个著名的数列，其中每个数字（从第三个开始）是前两个数字的和。数列的前几个数字是 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … 等。下面是一个用Java实现的斐波那契数列的详细版本，包括递归方法、迭代方法以及一个优化的迭代方法，该方法使用动态规划来避免重复计算。

递归方法

递归方法虽然简单直观，但在处理大数字时效率很低，因为它会重复计算许多相同的子问题。

public class FibonacciRecursive {

    // 递归方法
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 10; // 示例数字
        long startTime = System.currentTimeMillis();
        int result = fibonacci(n);
        long endTime = System.currentTimeMillis();

        System.out.println("斐波那契数列第 " + n + " 项是: " + result);
        System.out.println("递归方法执行时间: " + (endTime - startTime) + " 毫秒");
    }
}

迭代方法

迭代方法通过从第一个和第二个数开始，并使用循环来计算后续的数字，从而避免了重复计算。

public class FibonacciIterative {

    // 迭代方法
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0;
        int b = 1;
        int c;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }

    public static void main(String[] args) {
        int n = 100; // 示例数字（使用更大的数字以显示效率差异）
        long startTime = System.currentTimeMillis();
        int result = fibonacci(n);
        long endTime = System.currentTimeMillis();

        System.out.println("斐波那契数列第 " + n + " 项是: " + result);
        System.out.println("迭代方法执行时间: " + (endTime - startTime) + " 毫秒");
    }
}

优化迭代方法（使用动态规划）

在上面的迭代方法中，我们实际上已经使用了动态规划的思想，因为我们在每次迭代中重用了之前的计算结果。但为了更明确地展示动态规划的概念，我们可以使用一个数组来存储已经计算过的斐波那契数。

public class FibonacciDynamicProgramming {

    // 动态规划方法
    public static int fibonacci(int n) {
        if (n <= 1) {
            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];
    }

    public static void main(String[] args) {
        int n = 1000; // 示例数字（使用更大的数字以显示效率）
        long startTime = System.currentTimeMillis();
        int result = fibonacci(n);
        long endTime = System.currentTimeMillis();

        System.out.println("斐波那契数列第 " + n + " 项是: " + result);
        System.out.println("动态规划方法执行时间: " + (endTime - startTime) + " 毫秒");

        // 扩展：分析斐波那契数列的特性或与其他算法进行比较
        // ...
    }
}

扩展与深入分析

以上三种方法在处理斐波那契数列时各有优缺点。递归方法简单但效率低下，因为它重复计算了很多子问题。迭代方法通过避免重复计算提高了效率，但仍然只计算了单个斐波那契数。动态规划方法进一步提高了效率，因为它不仅计算了所需的斐波那契数，还存储了计算过程中的所有斐波那契数，这些数可以在后续计算中重复使用。