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ライブラリには、BigInteger を出力する factorial の高度に最適化された実装があります。 それをチェックしてください。(よりバランスの取れた乗算を行い、単純なシフトを最適化します。)

于 2012-01-24T20:50:59.050 に答える
0

factorial の単純な実装は、実際の状況ではうまくいきません。

深刻な必要性がある場合、最善の方法は、整数だけでなく 10 進数に対しても正しいガンマ関数 (または関数) を作成することです。ln(gamma)を使用して計算を繰り返し続ける必要がないように、結果をメモしておくWeakHashMapと、ビジネスに役立ちます。

于 2012-01-24T23:16:07.953 に答える