16

我正在尝试编写一个 Java 程序来计算大量的阶乘。似乎BigInteger无法容纳这么大的数量。

下面是我写的（直截了当的）代码。

 public static BigInteger getFactorial(BigInteger num) {
      if (num.intValue() == 0) return BigInteger.valueOf(1);

      if (num.intValue() == 1) return BigInteger.valueOf(1);

      return num.multiply(getFactorial(num.subtract(BigInteger.valueOf(1))));
  }

上述程序处理的最大数量为 5022，之后程序抛出一个StackOverflowError. 还有其他方法可以处理吗？

4

5 回答 5

34

这里的问题看起来像是由于过多的递归而导致的堆栈溢出（5000 次递归调用看起来大约是正确数量的调用来炸毁 Java调用堆栈），而不是. 迭代地重写阶乘函数应该可以解决这个问题。例如：BigInteger

public static BigInteger factorial(BigInteger n) {
    BigInteger result = BigInteger.ONE;

    while (!n.equals(BigInteger.ZERO)) {
        result = result.multiply(n);
        n = n.subtract(BigInteger.ONE);
    }

    return result;
}

希望这可以帮助！

于 2012-01-24T18:59:59.047 回答
3

问题不在于 BigInteger，而是您使用递归方法调用 ( getFactorial())。

于 2012-01-24T19:00:26.270 回答
2

试试这个，一个迭代算法：

public static BigInteger getFactorial(int num) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= num; i++)
        fact = fact.multiply(BigInteger.valueOf(i));
    return fact;
}
于 2012-01-24T19:14:22.940 回答
0

Google的Guava库对输出 BigIntegers 的阶乘进行了高度优化。 检查出来。（它做了更平衡的乘法并优化了简单的转变。）

于 2012-01-24T20:50:59.050 回答
0

简单的阶乘实现在实际情况下是行不通的。

如果您有严重的需求，最好的办法是编写一个gamma函数（或ln(gamma)函数），它不仅适用于整数，而且适用于十进制数。记住结果，这样您就不必继续使用 a 重复计算，WeakHashMap并且您正在开展业务。

于 2012-01-24T23:16:07.953 回答