计算组合的金额 [英] Calculating the Amount of Combinations

问题描述

干杯，

我知道你能得到的组合用下面的公式金额（不重复和顺序并不重要）：

I know you can get the amount of combinations with the following formula (without repetition and order is not important):

// Choose r from n

n! / r!(n - r)!

不过，我不知道如何实现这在C ++，因为例如用

However, I don't know how to implement this in C++, since for instance with

n = 52

n! = 8,0658175170943878571660636856404e+67

数甚至无符号__int64变得太大了（或无符号长长）。有一些变通方法来实现的公式，没有任何第三方BIGINT-libraries？

the number gets way too big even for unsigned __int64 (or unsigned long long). Is there some workaround to implement the formula without any third-party "bigint" -libraries?

推荐答案

下面是一个古老的算法是准确，不溢出，除非其结果是大的很长很长

Here's an ancient algorithm which is exact and doesn't overflow unless the result is to big for a 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卷的艺术：半数值算法我觉得

This algorithm is also in Knuth's "The Art of Computer Programming, 3rd Edition, Volume 2: Seminumerical Algorithms" I think.

更新：有一个小的可能性，该算法将溢出就行了：

UPDATE: There's a small possibility that the algorithm will overflow on the line:

r *= n--;

为非常 n很大。一个天真的上限为的sqrt（的std :: numeric_limits的＆LT;长长＆GT; :: MAX（））这意味着 N 小于rougly 40亿。

for very large n. A naive upper bound is sqrt(std::numeric_limits<long long>::max()) which means an n less than rougly 4,000,000,000.

这篇关于计算组合的金额的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！