c++ - 计算组合数量

Question

干杯，

我知道你可以用下面的公式得到组合的数量(不重复，顺序不重要):

// Choose r from nn! / r!(n - r)!

但是，我不知道如何在 C++ 中实现这一点，例如

n = 52n! = 8,0658175170943878571660636856404e+67

即使对于 unsigned __int64(或 unsigned long long)，这个数字也会变得太大。是否有一些解决方法可以在没有任何第三方“bigint”-库的情况下实现公式？

Answer 1

这是一个古老的算法，它是精确的并且不会溢出，除非结果对于 long long 来说太大了。

unsigned long long
choose(unsigned long long n, unsigned long long k) {
    if (k > n) {
        return 0;
    }
    unsigned long long r = 1;
    for (unsigned long long d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}

我认为这个算法也在 Knuth 的“计算机编程艺术，第 3 版，第 2 卷:半数值算法”中。

更新:算法溢出的可能性很小:

r *= n--;

对于非常大的n。一个天真的上限是 sqrt(std::numeric_limits<long long>::max())这意味着 n大约不到 4,000,000,000。