斐波那契數列f（93）具有負值，怎麼樣？

我想打印出斐波那契數列'N'數字。所有的作品都按照期望值運行直到f（92），但當我試圖獲得f（93）的值時，數值變爲負值：「-6246583658587674878」。這怎麼可能？以下邏輯中的錯誤是什麼？斐波那契數列f（93）具有負值，怎麼樣？

public long fibo(int x){ 
    long[] arr = new long[x+1]; 
    arr[0]=0; 
    arr[1]=1; 
    for (int i=2; i<=x; i++){ 
     arr[i]=arr[i-2]+arr[i-1]; 
    } 
    return arr[x]; 
} 

f(91) = 4660046610375530309 
f(92) = 7540113804746346429  
f(93) = -6246583658587674878

這是因爲數據類型？還有什麼數據類型可用於打印斐波納契數列的N個數字？ N可以是範圍[0..10,000,000]內的任何整數。

來源

2014-02-10 R. Rahul

似乎是整數溢出。我敢打賭，BigInteger會更好用。 – Makoto

由於長時間使用64位編碼範圍在[-2^63,2^63 -1]之間。 – mweisz

你遇到了一個integer overflow：

4660046610375530309 <-- term 91 
+7540113804746346429 <-- term 92 
==================== 
12200160415121876738 <-- term 93: the sum of the previous two terms 
9223372036854775808 <-- maximum value a long can store

爲了避免這種情況，使用BigInteger，它可以處理的數字的任意數量。
這裏是你實現轉換爲使用BigDecimal：

public String fibo(int x){ 
    BigInteger[] arr = new BigInteger[x+1]; 
    arr[0]=BigInteger.ZERO; 
    arr[1]=BigInteger.ONE; 
    for (int i=2; i<=x; i++){ 
     arr[i]=arr[i-2].add(arr[i-1]); 
    } 
    return arr[x].toString();u 
}

注意，返回類型必須爲String（或BigInteger的），因爲93 x甚至適度值產生的結果是太大，任何Java原語代表。

來源

2014-02-10 00:31:23 Bohemian

感謝您添加解決方案 –

我剛剛遇到此解決方案，並注意到如果x == 0，則arr [1] = BigInteger.ONE將拋出IndexOutOfBoundsException。應該可能檢查一下，並相應地初始化數組：BigInteger [] arr; if（x == 0）{arr = new BigInteger [x + 2]; } else {arr = new BigInteger [x + 1]; } – nihilon

@nih如果x <1，拋出IllegalArgumentException會更好。如果x是-5，該怎麼辦？該方法接受從1（對於第一個斐波納契數）到n（對於第n）的自然數。這顯示了工作方法的本質。這並不意味着成爲商業上可用的防彈解決方案。 – Bohemian

發生這種情況是因爲long類型溢出。換句話說：計算的數字太大而不能表示爲long，並且因爲用於整數類型的two's complement表示形式，所以在發生溢出後，該值變爲負值。有發生了什麼更好的主意，看看這段代碼：

System.out.println(Long.MAX_VALUE); 
=> 9223372036854775807 // maximum long value 
System.out.println(Long.MAX_VALUE + 1); 
=> -9223372036854775808 // oops, the value overflowed!

的fibo(93)值是12200160415121876738，這顯然比適合在一個long值的最大值。

這是整數在計算機程序中的工作方式，畢竟他們是有限的，不能是無限的。一種可能的解決方案是使用BigInteger來實現該方法（而不是long），它是用於表示Java中的任意精度整數的類。

來源

2014-02-10 00:28:34

斐波那契數列f（93）具有負值，怎麼樣？

回答

相關問題