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 回答