Java 程式設計師應該了解哪些關於斐波那契數的知識

通常在面試過程中，尤其是在外企，人們可能會被問到演算法，而在壓力很大的情況下，瘋狂地記住一些東西並不總是那麼容易。因此，你需要做好準備。首先，至少刷新一下你對基本演算法的記憶。今天我們將分析斐波那契數列這樣的現像以及與之相關的問題的最常見變體。 斐波那契數是一個以數字 0 和 1 開頭的自然數序列，後續的每個數字都等於前兩個數字總和： F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0，n ∈ Z

值得注意的是，有時會省略 0，並且級數以 1 1 2 3 開始...通常，在問題的條件下，會立即指定級數以哪一個前兩個數字開始（0.1 或 1.1），因此，我們將進一步考慮這兩種情況的解決方案。

在Java中取得前n個斐波那契數

假設我們有一個任務來取得前 n 個斐波那契數。

• 案例0.1：

  某個數字 n 來到我們身邊：

  int[] arr = new int[n];
  arr[0] = 0;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  我們建立一個大小為 n 的陣列。前兩個元素將等於 0 和 1，其餘元素是透過執行此循環並使用數組中的先前數字獲得的。

  我們顯示：

  for (int i = 0; i < arr.length; ++i) {
    System.out.println(arr[i]);
  }

  設定int n = 10；

  我們得到：

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• 對於情況 1.1，解決方案實際上沒有什麼不同：

  int[] arr = new int[n];
  arr[0] = 1;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  我們需要更改的只是數組 arr[0] 的第一個元素：從 0 到 1。相應地，前 10 個元素將是：

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

通過流的前 n 個斐波那契數

但我們想展示我們的水平。那麼讓我們看看使用Stream 的解決方案會是什麼樣子。

• 對於 0.1：

  Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));

  Stream類別的靜態 iterate 方法傳回一個無限有序流，該流是透過將該函數應用於初始數組 arr 而建立的。在我們的例子中，該功能是根據前一個陣列設定組成每個新數組的規則。結果，我們將得到一個數組流：

  {0,1}
  {1,1}
  {1, 2}
  {2, 3}
  {3, 5}
  {5, 8}
  {8, 13}
  {13, 21}
  {21, 34}
  {34, 55}
  …..

  但它們的數量是無限的，因此使用 .limit(n) 我們將元素的數量減少到前 n （在我們的例子中減少到 10）。

  但是，我們不需要數組流，因此使用 .map(y -> y[0]) 我們選擇每個數組的第一個元素並獲取包含我們需要的數字的流，並使用 forEach 將其列印到控制台。

  看起來更酷，不是嗎？

  第一個元素為 1,1，此程式碼也幾乎相同：

  Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(y -> y[0])
       .forEach(x -> System.out.println(x));

  同樣，差異在於初始元素：我們設定了 {1, 1}，而不是 {0, 1}

  實際上，結果將與前面的範例相同。

斐波那契數列之和

如果我們被要求獲得直到第 n 個元素（含第 n 個元素）的斐波那契數列總和，該怎麼辦？這不應該給我們帶來任何困難。讓我們採用流的解決方案，並將 forEach 替換為其他幾個方法：

• 對於 0.1：

  int n = 10;
  int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(t -> t[0])
       .mapToInt(Integer::intValue)
       .sum();
  System.out.println(result);

  使用 .mapToInt(Integer::intValue) 我們將流轉換為數位 IntStream 並使用其 .sum() 方法來取得所有元素的總和。

• 對於初始元素為 1,1 的情況，我們設定 {1, 1}，而不是 {0, 1}。

取得斐波那契數列中的第 n 個數字

有時，系統會要求您列印的不是一系列數字，而是列印斐波那契數列中的第 n 個數字。通常，這只會使任務變得更容易，因為您可以輕鬆適應先前的解決方案。那麼，透過遞歸來解決問題怎麼樣呢？

1. 對於 0.1：

   public int getFibonacciValue(int n) {
     if (n <= 1) {
        return 0;
     } else if (n == 2) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   要使用 0,1 運行演算法，需要指定當我們嘗試取得第一個元素時，我們取得 0，第二個元素取得 - 1。事實上，與先前的解決方案一樣，我們需要設定前兩個元素元素。

2. 1.1 的實作會略有不同：

   public int getFibonacciValue(int n) {
     if (n == 0) {
        return 0;
     } else if (n == 1) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   在這種情況下，我們只需將第一個元素設為 1，因為第二個元素將相同，且該方法的回應將相同。

   同時，我們將方法的反應設為0，因為如果我們不設定它，那麼當2作為參數時，會遞歸呼叫相同的方法，但參數為0。接下來，將啟動相同的方法，但為負數，依此類推，直到負無窮大。結果，我們將收到一個 StackOverflowError。

但是，不建議使用遞歸方法，因為與先前的方法（在線性 O(n) 時間內運行）不同，遞歸方法可能需要更長的時間才能完成。為什麼？ 遞歸方法可能需要很長時間，因為在計算過程中，相同參數會多次呼叫函數。例如，在計算 getFibonacciValue(7) 時，該函數將遞歸呼叫 getFibonacciValue(5) 和 getFibonacciValue(6)，這兩個遞歸呼叫都會呼叫 getFibonacciValue(4)），這將導致多次呼叫相同的操作。在面試時，你可以展示這個方法作為解決方案，但同時談論它的缺點並提供另一種方法作為回報。另外值得注意的是，Java 中的int 類型允許儲存從-2147483648 到2147483647 的範圍，因此您只能計算前46 個斐波那契數：如果我們嘗試取得下一個47 個數，則會出現溢出，而我們會得到一個負數。如果我們使用 long 資料型別而不是 int，我們將能夠正確計算前 91 個斐波那契數。要計算後續的斐波那契數，您需要使用 BigInteger 類，該類實現了真正 BIG 數的儲存和算術運算的邏輯。