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項，即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 

程式碼解釋

以上程式碼透過遞迴呼叫Fibonacci來計算斐波那契數列，從0到9計算每個位置。該方法將前兩個位置的結果加起來以獲得每個新數字，除了前兩個位置，它們都是1。

時間複雜度 : O(2ⁿ)

空間複雜度 : O(1)