代码之家 › 专栏 › 技术社区 › Kudayar Pirimbaev

C++:组合/多集函数(阶乘溢出)

factorial combinatorics algorithm c++

1

Kudayar Pirimbaev · 技术社区 · 13 年前

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

enter image description here

问题是阶乘很容易溢出,那么基本上这个问题有什么解决方案?

由于它是TopCoder中一个问题的子问题,因此我有以下约束:

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

2) 我无法加载外部库。

3 回复 | 直到 10 年前

1

5

taocp 13 年前

你真的不需要计算 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) 如果是长双,并且n没有那么大,这种方式应该有效。否则,您需要定义自己的BigInteger类以避免溢出,并定义 + 运算符适用于BigIntegers,后者通常表示为字符数组或字符串。

2

0

Community Mohan Dere 9 年前

阶乘是相当大的数字(它们不适合64位的字)。所以你需要使用 bignums (任意精度算术)来完整地计算它们。考虑使用 GMPlib 为此目的(或语言和实现中的代码,例如带有 SBCL ,这本身就赋予了它们)

另请参阅 this 和 that 一个和你的问题非常相似的答案。

3

0

Arslan Ali 13 年前

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