Java Fibonacci数列实现

Fibonacci数列是一个经典的数学序列,其中每个数字是前两个数字的和，以下是几种在Java中实现Fibonacci数列的方法：

递归实现（简单但效率低）

public class Fibonacci {
    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;
        System.out.println("Fibonacci数列前" + n + "项:");
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

迭代实现（高效）

public class Fibonacci {
    public static void fibonacci(int n) {
        int a = 0, b = 1, c;
        System.out.println("Fibonacci数列前" + n + "项:");
        for (int i = 0; i < n; i++) {
            System.out.print(a + " ");
            c = a + b;
            a = b;
            b = c;
        }
    }
    public static void main(String[] args) {
        fibonacci(10);
    }
}

使用数组存储（适用于需要多次访问）

public class Fibonacci {
    public static int[] fibonacci(int n) {
        int[] fib = new int[n];
        fib[0] = 0;
        if (n > 1) {
            fib[1] = 1;
        }
        for (int i = 2; i < n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib;
    }
    public static void main(String[] args) {
        int n = 10;
        int[] fibSequence = fibonacci(n);
        System.out.println("Fibonacci数列前" + n + "项:");
        for (int num : fibSequence) {
            System.out.print(num + " ");
        }
    }
}

使用BigInteger处理大数

import java.math.BigInteger;
public class Fibonacci {
    public static void fibonacci(int n) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        BigInteger c;
        System.out.println("Fibonacci数列前" + n + "项:");
        for (int i = 0; i < n; i++) {
            System.out.print(a + " ");
            c = a.add(b);
            a = b;
            b = c;
        }
    }
    public static void main(String[] args) {
        fibonacci(100); // 可以计算非常大的Fibonacci数
    }
}

动态规划优化（记忆化递归）

public class Fibonacci {
    private static int[] memo;
    public static int fibonacci(int n) {
        memo = new int[n + 1];
        return fibHelper(n);
    }
    private static int fibHelper(int n) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = fibHelper(n - 1) + fibHelper(n - 2);
        return memo[n];
    }
    public static void main(String[] args) {
        int n = 50;
        System.out.println("第" + n + "个Fibonacci数是: " + fibonacci(n));
    }
}

性能比较

1. 递归方法：简单直观，但时间复杂度为O(2^n)，效率极低
2. 迭代方法：时间复杂度O(n)，空间复杂度O(1)，是最常用的方法
3. 数组存储：时间复杂度O(n)，空间复杂度O(n)，适合需要多次访问的情况
4. BigInteger：可以处理任意大的数，但计算速度会稍慢
5. 动态规划：时间复杂度O(n)，空间复杂度O(n)，比纯递归高效

对于大多数应用场景,迭代方法是最佳选择，因为它既高效又易于实现。