1

n 個の要素のセットから m 個の要素の組み合わせとマルチセットを計算する問題を実装する必要があります。それらの式は次のとおりです。

ここに画像の説明を入力

ここに画像の説明を入力

問題は、階乗ではオーバーフローしやすいことです。基本的に、この問題の解決策は何ですか?

これは TopCoder の問題のサブ問題であるため、次の制約があります。

1) プログラムは C++ で作成する必要があります。

2) 外部ライブラリを読み込めません。

4

3 に答える 3

5

n!簡単にオーバーフローする可能性があるため、直接計算する必要はありません。以来

C(n,m) = C(n-1, m-1) + C(n-1,m)
C(n,0) = C(n,n) =1

サイズ(n+1,m+1)を指定してテーブルを作成し、動的計画法を使用してボトムアップ方式でテーブルを作成できます。

アルゴリズムの疑似コードは次のようになります。

for i ← 0 to n do  // fill out the table row wise
      for j = 0 to min(i, m) do
          if j==0 or j==i then C[i, j] ← 1 
          else C[i, j] ← C[i-1, j-1] + C[i-1, j] 
return C[n, m]

long double であると宣言c(n,m)し、n がそれほど大きくない場合、この方法は機能するはずです。それ以外の場合は、独自の BigInteger クラスを定義してオーバーフローを回避し、+通常は文字または文字列の配列として表される BigInteger に対して演算子がどのように機能するかを定義する必要があります。

于 2013-03-27T19:46:14.217 に答える
0

スタック オーバーフローを引き起こす可能性のある階乗の計算に再帰的なアプローチを使用する代わりに、反復的なアプローチを使用してください。これにより、数値が大きくてもオーバーフローを防ぐことができます。

于 2013-03-27T19:49:50.460 に答える
0

階乗は非常に大きな数です (64 ビット ワードには収まりません)。そのため、 bignum (任意精度演算) を使用してそれらを完全に計算する必要があります。その目的でGMPlibを使用することを検討してください(または言語と実装のコード、たとえば Common Lisp with SBCL、ネイティブにそれらを提供します)

あなたの質問に非常によく似た質問へのこれとその回答も参照してください。

于 2013-03-27T19:25:49.697 に答える