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)