2

什么是找到可以从 N 个礼物中选择 k 个礼物的方法数量的有效方法,其中 N 可能非常大(N ~ 10^18)。也就是说我们必须计算 N(C)K 或 N 选择 K。K 也可以是 N 的数量级。

4

4 回答 4

5

我想没有快速的方法来计算这么大的数字。您可以使用斯特林公式来近似它

于 2011-01-23T16:56:30.510 回答
3

由于多样性是生活的调味品,另一种方法如下。值 (N 选择 K)/2^N 接近具有均值 N/2 和标准偏差 Sqrt[N]/2 的正态分布,而且它的速度非常快。因此,我们可以将 (N 选择 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 回答
3

的值C(n, k)可以接近2^n。(嗯,数量级更小,但这在这里并不重要)。

重要的是要存储 number 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).

事实是,很容易实现 log gamma,然后你就有了

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

哪里f = log gamma

你可以在Numerical Recipes中找到计算 log gamma 的数值算法,那里有一个旧版本,你会在第 6 章找到一个示例实现。

于 2011-01-23T17:07:43.577 回答