Java 中的斐波那契数列

2025年7月2日 | 阅读6分钟

在Java中实现斐波那契数列是一个经典的编程练习，它为理解递归、动态规划和数学概念提供了一个极好的入门。在本节中，我们将探讨在Java中实现斐波那契数列的不同方法，讨论它们的优缺点，并深入研究其底层的数学原理。

斐波那契数列

斐波那契数列是一个数字序列，其中每个数字是前两个数字之和。

换句话说，在斐波那契数列中，下一个数字是前两个数字的和。它通常以0和1开始。该序列如下：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55，依此类推。

在深入研究Java代码之前，让我们简要讨论一下斐波那契数列的数学特性。

序列中的每个数字（前两个之后）是前两个数字的和。形式上，如果我们用 F(n) 表示第 n 个斐波那契数，那么

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1

有以下四种方法可以找到斐波那契数列

不使用递归
使用递归
使用动态规划
使用队列

不使用递归

斐波那契数列可以通过迭代方法确定。与迭代方法一样，递归方法也是从底层开始，然后向上构建。

让我们看看Java中不使用递归的斐波那契数列程序。

示例

public class Main {  
public static void main(String args[])  
{    
 int n1=0,n2=1,n3,i,count=10;    
 System.out.print(n1+" "+n2);  //printing 0 and 1    
 for(i=2;i<count;++i)   //loop starts from 2 because 0 and 1 are already printed    
 {    
  n3=n1+n2;    
  System.out.print(" "+n3);    
  n1=n2;    
  n2=n3;    
 }    
}
}  

编译并运行

输出

0 1 1 2 3 5 8 13 21 34

使用递归

在Java中生成斐波那契数的最直接方法之一是使用递归。递归方法直接遵循斐波那契数列的数学定义。

让我们看看Java中使用递归的斐波那契数列程序。

示例

public class Main {  
 static int n1=0,n2=1,n3=0;    
 static void printFibonacci(int count) {    
    if(count>0){    
         n3 = n1 + n2;    
         n1 = n2;    
         n2 = n3;    
         System.out.print(" "+n3);   
         printFibonacci(count-1);    
     }    
 }    
 public static void main(String args[]) {    
  int count=10;    
  System.out.print(n1+" "+n2);      //printing 0 and 1    
  printFibonacci(count-2);        //n-2 because 2 numbers are already printed   
 }  
}  

编译并运行

输出

0 1 1 2 3 5 8 13 21 34

这种方法有一个明显的缺点：它会反复重新计算斐波那契数。例如，在计算 fibonacci(5) 时，它会多次重新计算 fibonacci(3) 和 fibonacci(4)。这种冗余导致指数级的时间复杂度，使其对于较大的 n 值效率低下。

记忆化：克服递归的缺点

为了克服递归方法的低效率，我们可以采用记忆化。它涉及存储昂贵函数调用的结果，并在再次遇到相同的输入时返回缓存的结果。在斐波那契数列的上下文中，这意味着存储先前计算的斐波那契数以避免冗余计算。

以下是如何在Java中实现记忆化

示例

import java.util.HashMap;  
import java.util.Map;  
public class Main {  
    private static Map<Integer, Integer> memo = new HashMap<>();  
    public static int fibonacci(int n) {  
        if (n <= 1)  
            return n;  
        if (memo.containsKey(n))  
            return memo.get(n);  
        int result = fibonacci(n - 1) + fibonacci(n - 2);  
        memo.put(n, result);  
        return result;  
    }  
    public static void main(String[] args) {  
        int n = 10;  
        for (int i = 0; i < n; i++) {  
            System.out.print(fibonacci(i) + " ");  
        }  
    }  
}  

编译并运行

输出

0 1 1 2 3 5 8 13 21 34

通过将中间结果存储在 memo map 中，我们消除了冗余计算，从而极大地提高了斐波那契函数的性能。通过记忆化，时间复杂度降低到线性，使其更加高效。

使用动态规划

为了在Java中使用动态规划实现斐波那契数列，我们采用自底向上的方法，将子问题的结果存储在一个数组中，并重用它们以避免冗余计算。

示例

public class Main {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }
public static void main(String[] args) {
        int n = 10;
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

编译并运行

输出

0 1 1 2 3 5 8 13 21 34

说明

输出代表前十个斐波那契数。该程序初始化一个数组来存储计算值，避免了冗余计算。它从索引 2 开始迭代，将前两个数字相加。最后，main() 方法打印从 0 到 9 的斐波那契数，生成 0, 1, 1, 2, 3, 5, 8, 13, 21, 34。

使用队列

使用队列在Java中生成斐波那契数列是一种有趣的方法，它利用了先进先出（FIFO）原则。此实现使用队列来维护计算下一个斐波那契数的动态滑动窗口，使其对于此任务既直观又高效。

示例

import java.util.LinkedList;
import java.util.Queue;
public class FibonacciQueue {
    public static void fibonacci(int n) {
        if (n < 1) return;
 Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        queue.add(1);
System.out.print("0 1 "); // First two numbers
        for (int i = 2; i < n; i++) {
            int first = queue.poll();
            int second = queue.peek();
            int next = first + second;
            queue.add(next);
            System.out.print(next + " ");
        }
    }
public static void main(String[] args) {
        int n = 10;
        fibonacci(n);
    }
}

编译并运行

输出

0 1 1 2 3 5 8 13 21 34

结论

在本节中，我们探讨了在Java中生成斐波那契数的各种方法。我们讨论了递归方法、其低效率以及记忆化如何克服它们。此外，我们还探讨了迭代方法，它提供了一种高效的替代方案。

理解和实现斐波那契数列不仅有助于掌握基本的编程概念，还能深入了解数学序列的优雅和美妙。在您继续Java编程之旅时，请记住，斐波那契数列只是众多等待在代码中探索和实现的数学概念之一。