2

Nが非常に大きくなる可能性があるN個のギフトからk個のギフトを選択できる方法の数を見つける効率的な方法は何ですか（N〜10 ^ 18）。つまり、N（C）Kを計算するか、NがKを選択する必要があります。KはNのオーダーにすることもできます。

4

4 に答える 4

5

このような大きな数を計算するための高速な方法はないと思います。スターリングの公式を使用して近似できます

于 2011-01-23T16:56:30.510 に答える
3

の値はC(n, k)に近い可能性があり2^nます。（まあ、桁違いに小さいですが、それはここでは重要ではありません）。

重要なのは、数値を格納するには、ビットまたはバイト2^(10^18)が必要なことです。 そのようなコンピューターはないので、問題の定義を調整することをお勧めします。10^18~ 10^17

他の人は、結果を浮動小数点数として格納できる近似式をすでに指摘しているため、必要以上にメモリを消費することはありません。

于 2011-01-23T16:59:47.860 に答える
3

k ~ n / 3スターリングの公式は、またはなどの漸近情報がさらにある場合にのみ役立ちますk ~ log n。特定の問題に関するこれ以上の情報がなければ、スターリングの公式の情報を引き出すことはできません。

前述の問題の場合、kとnが大きい場合（および大きくない場合でも）にC（n、k）を計算する最も直接的な方法は、次を使用することです。

log C(n, k) = log (n!) - (log (k!) + log ((n - k)!))

と

n! = gamma(n + 1).

事実、ログガンマの実装を導入するのは非常に簡単であり、次のようになります。

C(n, k) = exp (f(n + 1) - f(k + 1) - f(n - k + 1))

ここでf = log gamma。

数値レシピでログガンマを計算するための数値アルゴリズムを見つけることができます。古いバージョンがそこにあり、第6章にサンプル実装があります。

于 2011-01-23T17:07:43.577 に答える
3

多様性は人生のスパイスなので、別のアプローチは次のとおりです。値（N Choose K）/ 2 ^ Nは、平均N/2および標準偏差Sqrt[N]/ 2の正規分布に近づき、非常に高速になります。したがって、（N Choose K）を2 ^ N * Normdist（x、0,1）/ stdとして近似できます。ここで、x =（k-N / 2）/ stdであり、stdはSqrt [N]/2です。
Normdist（x、0,1）= Exp（-x ^ 2/2）* 1 /（Sqrt（2 * Pi））

エラーに関しては、数値が大きいほどこれははるかに良くなるはずです。Nを113（？）として使用して簡単にチェックすると、0.3％未満の最大係数のパーセントとして最大エラーが示されます。

スターリングの公式を使用するよりも優れているとは言えませんが、n ^ nの計算の一部を回避できる可能性があると考えてください。これらの係数の対数を計算することは、非常に簡単な計算です。

于 2011-01-23T18:02:34.333 に答える