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

我必须实现一个计算来自一组n个元素的m个元素的组合和多重集的问题。他们的公式是以下物质：C++：组合/多重集函数（阶乘溢出）

enter image description here

的问题是，用阶乘很容易溢出，所以基本上可以解决方案是怎样的这个问题？

由于它是在TopCoder的问题的一个子问题，我已经以下约束条件：

1）一种程序，必须用C++编写。

2）我无法加载外部库。

来源

2013-03-27 Kudayar Pirimbaev

重写C（n，m）的显式项。在你的问题中你所拥有的那个通常是理论上最方便的工作，但是当你真的需要计算它的时候，就会有一个不会很快溢出。 – us2012 2013-03-27 19:40:45

是的，好吧，我做到了 – 2013-03-27 19:46:27

你并不需要直接计算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类以避免溢出并定义Big运算符如何工作，BigInteger通常表示为字符或字符串数组。

来源

2013-03-27 19:46:14 taocp

它应该是第二个作为条件的j还是我错过了一点？ – 2013-03-27 19:49:29

@KudayarPirimbaev对不起，错字，第二个循环变量应该是j，而不是i。我更新了代码。好赶上，谢谢！ – taocp 2013-03-27 19:50:43

好的，谢谢，我不能相信我还没有想出这种不同的方法 – 2013-03-27 19:53:33

因子是相当大的数字（它们不适合64位字）。因此，您需要使用bignums（任意精度算术）来完整计算它们。考虑使用GMPlib用于这一目的（或代码的语言和执行，例如Common Lisp的有SBCL，这使他们本身）

又见this和that答案非常相似，你的问题。

来源

2013-03-27 19:25:49

那么如果我不能使用外部库并且必须用C++编写它呢？因为我在TopCoder中编写它，所以我有一些限制 – 2013-03-27 19:35:27

@KudayarPirimbaev：TopCoder至少可以让你使用C++，Java，C＃和VB。如果你想要走这条路线，那么其中的4条中有3条具有内置于标准库中的任意长度的整数。 – cHao 2013-03-27 19:57:58

因为我知道只有C++，我不能简单地改变语言来解决一个问题，但我知道他们是建立，谢谢，只是为了扩展我的编程范围，我问了约束，学习新的东西，你知道 – 2013-03-27 23:41:48

而不是使用递归方法计算可能导致堆栈溢出的阶乘，请使用迭代方法！即使是更大的数字，这也可以避免溢出。

来源

2013-03-27 19:49:50

数字溢出，而不是堆栈 – 2013-03-27 19:50:25

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

回答

相关问题