斐波那契、整數溢位、記憶 e um exagero

我們來做個練習吧。
下面我留下一個程式碼，回傳斐波那契數列 n 位置上的數字：

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

我們嘗試在終端機中顯示斐波那契數列中小於 2147483647 的所有數字怎麼樣？

    public static int fib(int n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int position = 1;
        int currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

存在的問題

運行程式碼時，您會注意到兩個主要問題：

• 我們的循環永遠不會結束，而且奇怪的是，負數開始出現在控制台中。
  

• 隨著時間的推移，程式碼變得越來越慢。

問題1：負數

暫時忽略所有這些斐波那契數，看看這段程式碼。

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

你認為這樣做的結果會是多少？ 20億20億=40億對嗎？所以在我們的程式碼中結果將是 40 億...對吧？

錯誤！

出路其實是這樣的：

造成這個結果的原因是溢出。 int 型別的最大限制為 2147483647（或 2^31 - 1）。當超過此限制時，該值將「傳回」為 int 類型的最低可能值，即 -2147483648。

為什麼我們的循環沒有停止？

當我們達到大於或等於 2147483647 的數字時，我們的循環應該停止，但是當斐波那契值超過 int 限制時，開始產生負數。由於我們從未達到大於 2147483647 的數字，因此循環從未停止。

問題1的解決方案

為了簡單起見，我只需將 fi​​b 函數的返回類型從 int 更改為 long，後者俱有更大的限制。我們的程式碼將如下所示：

    public static long fib(long n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

現在，使用 long 類型，我們可以正確列印斐波那契數列，直到小於 2147483647 的最大數。

解決問題2：緩慢

你注意到什麼了嗎？每次循環迭代時，fib 函數都會重新計算序列中所有先前的數字。換句話說，我們正在重複不必要的計算。

如何避免不必要的重新計算？我向您介紹：記憶化。記憶技術是一種保存已計算結果的方法，以免再次進行計算過程。

讓我們實作一個 HashMap 來儲存已經找到的值，其中鍵是位置，值是數字本身。

    static HashMap<Long, Long> memo = new HashMap<>();

    public static long fib(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            return n;
        }
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

美麗！現在我們的程式碼運行得更快了，我們解決了問題。

誇張之處

實際上，這裡不需要記憶。我只是想把這個概念帶到教學中。我們可以簡單地計算每個斐波那契數，直到完成我們的條件，如下所示：

    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 < 2147483647) {
            System.out.println(prev2);
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
    }

我已經玩夠了，對吧？對不起！但至少你學到了一些新東西。

---

文章封面作者：Gerd Altmann，來自 Pixabay

以上是斐波那契、整數溢位、記憶 e um exagero的詳細內容。更多資訊請關注PHP中文網其他相關文章！