我們來做個練習吧。
下面我留下一個程式碼，回傳斐波那契數列 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);
}
}
運行程式碼時，您會注意到兩個主要問題：
我們的循環永遠不會結束，而且奇怪的是，負數開始出現在控制台中。
隨著時間的推移，程式碼變得越來越慢。
暫時忽略所有這些斐波那契數，看看這段程式碼。
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 的數字，因此循環從未停止。
為了簡單起見，我只需將 fib 函數的返回類型從 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 的最大數。
你注意到什麼了嗎？每次循環迭代時，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中文網其他相關文章！
