algorithm - 大きな数の階乗

Question

数値の階乗を計算する問題を考えてみましょう。結果が 2^32 より大きい場合、オーバーフローエラーが発生します。大きな数の階乗を計算するプログラムをどのように設計できますか?

編集: C++ 言語を使用していると仮定します。

EDIT2：これは重複した質問です

score 2 · Accepted Answer

アルゴリズムがタグ付けされた質問として。アルゴリズムにオーバーフローエラーが発生することはないため、2^32 は問題になりません。アルゴリズムの実装には、オーバーフローエラーが発生する可能性があります。それで、あなたは何語を使っていますか？

ほとんどの言語には、使用できる BigNumber または BigInteger があります。

C++ BigInteger ライブラリは次のとおりです: https://mattmccutchen.net/bigint/

Google で検索することをお勧めします:c++ biginteger

score 1 · Accepted Answer

これを行うには、いくつかのアプローチのいずれかを実行する必要がありますが、基本的には次のようになります。

そうすれば、配列内の各 int/element には位置の大きさがあり、最後につなぎ合わせて整数にすることができます。

score 1 · Accepted Answer

近似値を使用できる場合は、スターリング近似を使用して倍精度で計算することを検討してください。

正確な値が必要な場合は、任意精度の演算と多くの計算時間が必要になります...

score 1 · Accepted Answer

組み合わせの数を計算するなど、一部の目的では、階乗を階乗で除算し、最終結果がより適切なサイズになるため、階乗の対数を計算するだけで十分です。結果の指数。

対数を追加するか、 http://en.wikipedia.org/wiki/Gamma_functionを使用して、階乗の対数を計算できます。これは数学ライブラリでよく利用できます (これを概算する良い方法があります)。

score 1 · Accepted Answer

このスクリプトをテストします。

import gmpy as gm 
print gm.fac(3000)

数が非常に多いため、結果のストックや印刷が困難です。

score 0 · Accepted Answer

まず、大きな数を格納して使用する方法を発明します。一般的な方法は、整数の配列を大きな数字の数字として解釈することです。次に、乗算などの基本演算をシステムに追加します。次に、乗算します。

または、すでに作成されたソリューションを使用します。Google for: C++ big integer ライブラリ

8 に答える 8