7

背景：

给定n这样的球：

'a' balls are of colour GREEN
'b' balls are of colour BLUE
'c' balls are of colour RED
...

（当然a + b + c + ... = n）

这些球可以排列的排列数由下式给出：

perm = n! / (a! b! c! ..)

问题1：如何“优雅”地计算，尽可能perm避免整数溢出，并确保计算完成后，我要么有正确的值，要么我知道最终结果会溢出?perm

基本上，我想避免使用像 GNU GMP 这样的东西。

可选地，问题 2：这是一个非常糟糕的主意，我应该继续使用 GMP 吗？

4

5 回答 5

6

这些被称为多项式系数，我将用 表示m(a,b,...)。

您可以通过利用此恒等式有效地计算它们以避免溢出（这应该很容易证明）：

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ...
m(0,0,0,...) = 1 // base case
m(anything negative) = 0 // base case 2

然后使用递归来计算系数是一件简单的事情。请注意，为避免指数运行时间，您需要缓存结果（以避免重新计算）或使用动态编程。

要检查溢出，只需确保总和不会溢出。

是的，使用任意精度库来完成这个简单的任务是一个非常糟糕的主意。

于 2011-12-21T15:11:33.237 回答
5

如果你有大量的 cpu 时间，你可以把所有的阶乘组成列表，然后找到列表中所有数字的素因数分解，然后将顶部的所有数字与底部的数字相消，直到数字完全减少。

于 2011-12-21T14:58:30.973 回答
3

最安全的溢出方式是 Dave 建议的方式。您找到素数p除以总和n!的指数

m = n;
e = 0;
do{
    m /= p;
    e += m;
}while(m > 0);

p减去等因式分解中的指数。a!对所有素数执行此操作<= n，您就有了多项式系数的因式分解。当且仅当最终结果溢出时，该计算才会溢出。但是多项式系数增长得相当快，所以你已经溢出了相当小的n. 对于大量计算，您将需要一个 bignum 库（如果您不需要精确的结果，您可以使用doubles 获得更长的时间）。

即使你使用 bignum 库，也值得避免中间结果变得太大，所以与其计算阶乘并划分巨大的数字，不如按顺序计算部分，

n!/(a! * b! * c! * ...) = n! / (a! * (n-a)!) * (n-a)! / (b! * (n-a-b)!) * ...

为了计算这些因素中的每一个，让我们以第二个为例进行说明，

(n-a)! / (b! * (n-a-b)!) = \prod_{i = 1}^b (n-a+1-i)/i

计算为

prod = 1
for i = 1 to b
    prod = prod * (n-a+1-i)
    prod = prod / i

最后将部分相乘。这需要n除法和n + number_of_parts - 1乘法，保持中间结果适度小。

于 2011-12-21T15:32:09.663 回答
1

根据此链接，您可以将多项式系数计算为多个二项式系数的乘积，从而控制整数溢出。

这将原始问题减少为二项式系数的溢出控制计算。

于 2011-12-21T21:15:22.900 回答
-2

符号：n! = prod(1,n)在哪里 prod 你可能会猜到是什么。

It's very easy, but first you must know that for any 2 positive integers (i, n > 0) that expression is a positive integer: 

prod(i,i+n-1)/prod(1,n)

Thus the idea is to slice the computation of n! in small chunks and to divide asap.

With a, than with b and so on. 

perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!)

Each of these factors is an integer, so if perm will not overflow, neither one of its factors will do.

Though, in the calculation of a such factor could be an overflow in numerator or denominator but that's avoidable doing a multiplication in numerator then a division in alternance:

prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b

In that way every division will yield an integer.

于 2015-08-24T20:04:02.300 回答