7

バックグラウンド：

n次のようなボールが与えられた場合:

'a' balls are of colour GREEN
'b' balls are of colour BLUE
'c' balls are of colour RED
...

（もちろんa + b + c + ... = n）

これらのボールを配置できる順列の数は、次の式で与えられます。

perm = n! / (a! b! c! ..)

perm質問 1:整数オーバーフローをできるだけ長く回避するために「エレガントに」計算するにはどうすればよいですか?また、計算が完了したら、 の正しい値を持っているかperm、最終結果がオーバーフローすることがわかっていることを確認してください。 ?

基本的に、GNU GMP などの使用は避けたいと考えています。

オプションで、質問 2: これは本当に悪い考えですか?

4

5 に答える 5

6

これらは多項係数として知られており、 で表しm(a,b,...)ます。

そして、この ID を利用することで、オーバーフローを回避して効率的に計算できます (証明するのはかなり簡単なはずです)。

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ...
m(0,0,0,...) = 1 // base case
m(anything negative) = 0 // base case 2

次に、再帰を使用して係数を計算するのは簡単なことです。指数関数的な実行時間を回避するには、(再計算を避けるために) 結果をキャッシュするか、動的計画法を使用する必要があることに注意してください。

オーバーフローをチェックするには、合計がオーバーフローしないことを確認してください。

はい、この単純なタスクを実行するために任意精度ライブラリを使用するのは非常に悪い考えです。

于 2011-12-21T15:11:33.237 に答える
5

CPU時間の塊がある場合は、すべての階乗からリストを作成し、リスト内のすべての数値の素因数分解を見つけてから、数値が完全になるまで、上部のすべての数値を下部の数値でキャンセルできます。減少。

于 2011-12-21T14:58:30.973 に答える
3

オーバーフローに対して最も安全な方法は、Dave が提案した方法です。総和で素数をp割る指数を求めますn!

m = n;
e = 0;
do{
    m /= p;
    e += m;
}while(m > 0);

pなどの因数分解での指数を引きますa!。すべての素数 に対して<= nこれを行うと、多項係数の因数分解が得られます。その計算は、最終結果がオーバーフローする場合にのみオーバーフローします。しかし、多項式の係数はかなり急速に大きくなるため、かなり小さい のオーバーフローが既に発生していますn。実質的な計算には、bignum ライブラリが必要になります (正確な結果が必要ない場合は、doubles を使用してもう少し長くすることができます)。

bignum ライブラリを使用しても、中間結果が大きくなりすぎないようにする価値があるため、階乗を計算して膨大な数を割るのではなく、部分を順番に計算する方がよいでしょう。

n!/(a! * b! * c! * ...) = n! / (a! * (n-a)!) * (n-a)! / (b! * (n-a-b)!) * ...

これらの要因のそれぞれを計算するために、説明のために 2 番目の要因を考えてみましょう。

(n-a)! / (b! * (n-a-b)!) = \prod_{i = 1}^b (n-a+1-i)/i

で計算されます

prod = 1
for i = 1 to b
    prod = prod * (n-a+1-i)
    prod = prod / i

最後にパーツを掛けます。これには、n除算とn + number_of_parts - 1乗算が必要であり、中間結果を適度に小さく保ちます。

于 2011-12-21T15:32:09.663 に答える
1

このリンクによると、途中で整数オーバーフローを制御しながら、複数の二項係数の積として多項係数を計算できます。

これにより、元の問題が 2 項係数のオーバーフロー制御計算に軽減されます。

于 2011-12-21T21:15:22.900 に答える
-2

表記法: n! = prod(1,n)where prod 何をするかはお察しのとおりです。

とても簡単ですが、最初に、任意の 2 つの正の整数に対して(i, n > 0)、その式が正の整数であることを知っておく必要があります。

prod(i,i+n-1)/prod(1,n)

したがって、アイデアは、の計算をn!小さなチャンクにスライスし、できるだけ早く分割することです。

とa、よりとbなど。

perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!)

これらの各要素は整数であるため、オーバーフローしない場合perm、その要素のいずれもオーバーフローしません。

ただし、そのような係数の計算では、分子または分母のオーバーフローになる可能性がありますが、分子で乗算を行ってから交互に除算を行うことは避けられます。

prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b

そのようにして、すべての除算が整数になります。

于 2015-08-24T20:04:02.300 に答える