遞歸函數計算階乘失敗後20

我寫了下面的Java代碼遞歸地計算從1到30的數字階乘。出於某種原因，輸出與results here不匹配的數字大於20.我很驚訝地看到負數。遞歸函數計算階乘失敗後20

代碼

class Test { 

    public static Long factorial(Long number) { 
     if(number == 1){ 
      return 1L; 
     }else{ 
      return number*factorial(number-1); 
     } 
    } 

    public static void main(final String... arguments){ 
     for(Long number=1L;number<=30;number++){ 
      System.out.println("Factorial of " + number + " : " + factorial(number)); 
     } 
    } 
}

輸出

Factorial of 1 : 1 
Factorial of 2 : 2 
Factorial of 3 : 6 
Factorial of 4 : 24 
Factorial of 5 : 120 
Factorial of 6 : 720 
Factorial of 7 : 5040 
Factorial of 8 : 40320 
Factorial of 9 : 362880 
Factorial of 10 : 3628800 
Factorial of 11 : 39916800 
Factorial of 12 : 479001600 
Factorial of 13 : 6227020800 
Factorial of 14 : 87178291200 
Factorial of 15 : 1307674368000 
Factorial of 16 : 20922789888000 
Factorial of 17 : 355687428096000 
Factorial of 18 : 6402373705728000 
Factorial of 19 : 121645100408832000 
Factorial of 20 : 2432902008176640000 
Factorial of 21 : -4249290049419214848 
Factorial of 22 : -1250660718674968576 
Factorial of 23 : 8128291617894825984 
Factorial of 24 : -7835185981329244160 
Factorial of 25 : 7034535277573963776 
Factorial of 26 : -1569523520172457984 
Factorial of 27 : -5483646897237262336 
Factorial of 28 : -5968160532966932480 
Factorial of 29 : -7055958792655077376 
Factorial of 30 : -8764578968847253504

可能有人請幫助我正確計算階乘高達30？

來源

2017-07-19 Beginner

查找溢出...... – brso05

這是一個整數溢出問題。嘗試使用BigInteger。 – luizfzs

你有一個溢出的情況下繼續。 – Chris

這就是所謂的「溢出」。長整型存儲在64位;其最大值爲2^63 - 1，即9,223,372,036,854,775,807。請嘗試使用BigInteger。使用BigInteger有點棘手，因爲實例化和操作與正常的int/long不同。這是你返工的BigInteger的代碼：

public class BigIntFactorial { 

    public static BigInteger factorial(BigInteger number) { 
     if(number.equals(BigInteger.ONE)) { 
      return BigInteger.valueOf(1); 
     } else { 
      return number.multiply(factorial(number.subtract(BigInteger.ONE))); 
     } 
    } 

    public static void main(final String... arguments){ 
     for(Long number=1L;number<=30;number++){ 

      System.out.println("Factorial of " + number + " : " + factorial(BigInteger.valueOf(number))); 
     } 
    } 
}

輸出爲：

Factorial of 1 : 1 
Factorial of 2 : 2 
Factorial of 3 : 6 
Factorial of 4 : 24 
Factorial of 5 : 120 
Factorial of 6 : 720 
Factorial of 7 : 5040 
Factorial of 8 : 40320 
Factorial of 9 : 362880 
Factorial of 10 : 3628800 
Factorial of 11 : 39916800 
Factorial of 12 : 479001600 
Factorial of 13 : 6227020800 
Factorial of 14 : 87178291200 
Factorial of 15 : 1307674368000 
Factorial of 16 : 20922789888000 
Factorial of 17 : 355687428096000 
Factorial of 18 : 6402373705728000 
Factorial of 19 : 121645100408832000 
Factorial of 20 : 2432902008176640000 
Factorial of 21 : 51090942171709440000 
Factorial of 22 : 1124000727777607680000 
Factorial of 23 : 25852016738884976640000 
Factorial of 24 : 620448401733239439360000 
Factorial of 25 : 15511210043330985984000000 
Factorial of 26 : 403291461126605635584000000 
Factorial of 27 : 10888869450418352160768000000 
Factorial of 28 : 304888344611713860501504000000 
Factorial of 29 : 8841761993739701954543616000000 
Factorial of 30 : 265252859812191058636308480000000

來源

2017-07-19 15:39:54

它不起作用，因爲您超過了可以用long表示的最大數量。其最低值爲-9,223,372,036,854,775,808，最高值爲9,223,372,036,854,775,807（含）。負數會出現，因爲當您超過最大值時，java會翻轉到負數。找到表示數字的不同方式。

來源

2017-07-19 15:30:06 ja08prat

你似乎已經運行到該階乘得到大得離譜的真快的問題。大於可以用長整數表示的最大數字。而在java中，這意味着價值「翻身」並變爲負面。

一個解決方案是使用BigInteger。它具有不同數量的位，因此您可以在其中表示幾乎任何大小的數字，並且不會遇到溢出問題。請注意，當我說的差不多時，我的意思是biginteger在某些實現上僅限於Integer.MAX_VALUE位，並且您不應該遇到該限制。

另一種解決方案是用雙打來表示數字。他們有一個更高的限制比多頭，以損失一些精度爲代價。我沒有運行這些數字，但是你應該可以計算30！

當你真的想要達到極限時，你可以做的另一件很酷的事情就是使用fft來計算非常高精度數的乘法。點擊此處瞭解詳情：http://numbers.computation.free.fr/Constants/Algorithms/fft.html

編輯：跑數，雙精度優良

來源

2017-07-19 15:54:42

遞歸函數計算階乘失敗後20

回答

相關問題