Java程序打印斐波那契数列

---

斐波那契数列通过将前两个数相加来生成后续的数。斐波那契数列从两个数开始——F0 & F1。F0 & F1的初始值可以分别取0, 1或1, 1。

Fn = Fn-1 + Fn-2

问题陈述

编写一个Java程序来打印斐波那契数列。

输入

Run the program

输出

1 1 2 3 5 8 13 21 34 55

当n=10时，得到上述输出。

打印斐波那契数列的不同方法

以下是打印斐波那契数列的不同方法：

• 使用自底向上动态规划
• 使用递归方法
  

使用自底向上动态规划

以下是使用动态规划打印斐波那契数列的步骤：

• 初始化变量
• 检查边缘情况
• 迭代计算项
• 更新变量
• 打印结果。

示例

以下是使用自底向上动态规划打印斐波那契数列的Java程序：

public class FibonacciSeries {
  public static void main(String args[]) {
    int a, b, c, i, n;
    n = 10;
    a = b = 1;
    System.out.print(a + " " + b);
    for (i = 1; i <= n - 2; i++) {
      c = a + b;
      System.out.print(" ");
      System.out.print(c);
      a = b;
      b = c;
    }
  }
}

输出

1 1 2 3 5 8 13 21 34 55

代码解释

初始化两个变量，last和secondLast，分别存储第(i-1)项和第(i-2)项。从2循环到n，计算每一i-th项为last和secondLast的和。在每次迭代中，将secondLast更新为last，将last更新为当前第i项。这种方法有效地生成直到第n项的斐波那契数列。

时间复杂度 : O(n)
空间复杂度 : O(1)

使用递归方法

以下是使用递归方法打印斐波那契数列的步骤：

• 首先在主方法中，设置n = 10，因为我们想要打印斐波那契数列的前10个数。
  
• 我们使用for循环遍历从0到n - 1（或9）的数字。在每个循环中，我们调用Fibonacci方法来查找该位置的斐波那契数并打印它。
• 使用递归计算斐波那契数，在Fibonacci方法内部，如果位置(n)是0或1，我们直接返回n。这是因为斐波那契数列的前两个数都是1。
• 对于任何其他位置，我们通过将序列中的前两个数相加来查找该数。我们通过调用Fibonacci(n - 1)和Fibonacci(n - 2)并将它们的结果加在一起来做到这一点。
  

示例

以下是使用递归方法打印斐波那契数列的Java程序：

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

输出

0 1 1 2 3 5 8 13 21 34 

代码解释

上述代码通过对从0到9的每个位置调用Fibonacci来递归地计算斐波那契数列。该方法将来自前两个位置的结果加起来以获得每个新数，除了前两个位置，它们都是1。

时间复杂度 : O(2ⁿ)

空间复杂度 : O(1)