计算组合数量

Question

计算组合数量

31

您好，

我知道您可以使用以下公式（不考虑重复且顺序不重要）获取组合数：

//从n个物品中选r个
n! / r!(n - r)!

但是，我不知道如何在C++中实现它，因为例如：

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

即使对于 unsigned __int64 或 unsigned long long 类型的变量而言，这个数字也太大了。请问有没有不需要第三方“bigint”库的解决方法？

- nhaa123

有关使用大整数，请参见以下链接：<br> https://dev59.com/5nM_5IYBdhLWcg3w3nXz<br> https://dev59.com/VXNA5IYBdhLWcg3wL62x<br> https://dev59.com/cnVC5IYBdhLWcg3wnCf6<br> - Sajad Bahmani

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- int3 · Answer 1

如果您想要100%确保在数字限制内最终结果不会发生溢出，您可以逐行求和帕斯卡三角形：

for (int i=0; i<n; i++) {
    for (int j=0; j<=i; j++) {
        if (j == 0) current_row[j] = 1;
        else current_row[j] = prev_row[j] + prev_row[j-1];
    }
    prev_row = current_row; // assume they are vectors
}
// result is now in current_row[r-1]

然而，这个算法比乘法慢得多。因此，也许你可以使用乘法来生成所有你知道的“安全”的情况，然后从那里开始使用加法。（或者你可以直接使用一个BigInt库）。