c++ - C++：组合/多集函数（阶乘溢出）

Question

我必须实现一个问题，从一组 n 个元素中计算 m 个元素的组合和多组。它们的公式如下：

问题是阶乘很容易溢出，所以基本上有什么解决方案可以解决这个问题？

由于它是 TopCoder 中问题的子问题，因此我有以下约束：

1) 程序必须用 C++ 编写。

2）我无法加载外部库。

Answer 1

你真的不需要n!直接计算，这很容易溢出。自从

C(n,m) = C(n-1, m-1) + C(n-1,m)
C(n,0) = C(n,n) =1

您可以建立一个有大小的表格，(n+1,m+1)并使用动态编程以自下而上的方式建立表格。

算法伪代码可能如下所示：

for i ← 0 to n do  // fill out the table row wise
      for j = 0 to min(i, m) do
          if j==0 or j==i then C[i, j] ← 1 
          else C[i, j] ← C[i-1, j-1] + C[i-1, j] 
return C[n, m]

如果您声明c(n,m)为 long double 并且 n 不是那么大，那么这种方式应该可以工作。否则，您需要定义自己的 BigInteger 类以避免溢出，并定义+运算符对 BigInteger 的工作方式，BigInteger 通常表示为字符数组或字符串。

Answer 2

阶乘是相当大的数字（它们不适合 64 位字）。因此，您需要使用bignums（任意精度算术）来完整计算它们。考虑为此目的使用GMPlib（或在语言和实现中编写代码，例如 Common Lisp with SBCL，它本机提供它们）

另请参阅this和that对与您的问题非常相似的答案。

Answer 3

不要使用递归方法来计算可能导致堆栈溢出的阶乘，而是使用迭代方法！即使对于更大的数字，这也可以为您节省溢出。