计算大组合

Question

如何计算类似于（100,000选择50,000）的组合？

到目前为止，我已经尝试了三种不同的方法，但显然每一种都失败了：

1）动态规划-数组的大小变得如此之大，导致它出现了段错误。

unsigned long long int grid[p+1][q+1];

//Initialise x boundary conditions
for (long int i = 0; i < q; ++i) {
  grid[p][i] = 1;
}

//Initialise y boundary conditions
for (long int i = 0; i < p; ++i) {
  grid[i][q] = 1;
}


for (long int i = p - 1; i >= 0; --i) {
  for (long int j = q - 1; j >= 0; --j) {
     grid[i][j] = grid[i+1][j] + grid[i][j+1];
   }
}

2) 暴力破解 - 很明显，即使计算100！也是不现实的。

unsigned long long int factorial(long int n)
{
  return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}

3) 乘法公式 - 我无法存储这些值，因为它们非常大

const int gridSize = 100000; //say 100,000
unsigned long long int paths = 1;

for (int i = 0; i < gridSize; i++) {
    paths *= (2 * gridSize) - i;
    paths /= i + 1;
}

// code from (http://www.mathblog.dk/project-euler-15/)

如果需要背景信息，请注意，这是为了解决大规模输入的“m×n网格中有多少条路径”的问题。也许我在错误地攻击这个问题吗？

- Matt Stokes

Answer 1

C(100000, 50000)是一个具有30101位小数的极大数字: http://www.wolframalpha.com/input/?i=C%28100000%2C+50000%29

显然，使用unsigned long long无法存储它。您需要一些任意大小的整数库，例如GMP：http://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

否则，乘法公式应该已经足够。

- Sergii Dymchenko

Answer 2

"How would you compute ..."非常取决于所需的精度。只有使用任意精度数字（例如GMP）才能计算精确结果，但您很可能并不需要确切的结果。在这种情况下，我会使用斯特林公式来近似计算阶乘（http://en.wikipedia.org/wiki/Stirling%27s_approximation），并使用双精度数进行计算。展开式中的项数可用于调节误差。维基百科页面还将为您提供误差估计。

- example

Answer 3

这里是一个可能有用的递归公式：

NCk = (N-1)C(k-1)*N/K

首先对(N-1)C(K-1)使用递归调用，然后在结果上评估NCk。

由于您的数字将非常大，请使用以下其中一种替代方法。

1. GMP
2. 使用自己的实现，在数组中将数字存储为二进制位序列，并使用 Booth算法进行乘法和移位&减法进行除法。

- Vikram Bhat