这是计算nCr的更好方法

Question

方法1:
C(n,r)= n!/(nr)!r!

方法2:
在wilf的" 组合算法 "一书中,我发现:
C(n,r)可以写成C(n-1,r) + C(n-1,r-1).

例如

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

如您所见,最终解决方案不需要任何乘法.在每种形式C(n,r)中,n == r或r == 1.

这是我实现的示例代码:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

请参见此处的输出

在方法2中,存在重叠的子问题,我们正在调用递归来再次解决相同的子问题.我们可以通过使用动态编程来避免它.

我想知道哪个是计算C(n,r)的更好方法？

Answer 1

这两种方法都可以节省时间,但第一种方法很容易出现整数溢出.

方法1:

这种方法将在最短的时间内生成结果(在大多数n/2迭代中),并且可以通过仔细进行乘法来减少溢出的可能性:

long long C(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

此代码将从较小的一端开始乘以分子,并且当任何k连续整数的乘积可被整除时k!,将不存在可除性问题.但溢出的可能性仍然存在,另一个有用的技巧,可以划分n - r + i并i通过做乘法和除法(和之前的GCD 仍可能发生溢出).

方法2:

在这种方法中,你将实际构建Pascal的三角形.动态方法比递归方法快得多(第一个是O(n^2)另一个是指数的).但是,您也需要使用O(n^2)内存.

# define MAX 100 // assuming we need first 100 rows
long long triangle[MAX + 1][MAX + 1];

void makeTriangle() {
    int i, j;

    // initialize the first row
    triangle[0][0] = 1; // C(0, 0) = 1

    for(i = 1; i < MAX; i++) {
        triangle[i][0] = 1; // C(i, 0) = 1
        for(j = 1; j <= i; j++) {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

long long C(int n, int r) {
    return triangle[n][r];
}

然后,你可以查找任何C(n, r)的O(1)时间.

如果你需要一个特定的C(n, r)(即不需要完整的三角形),那么可以O(n)通过从上到下覆盖三角形的同一行来进行内存消耗.

# define MAX 100
long long row[MAX + 1]; // initialized with 0's by default if declared globally

int C(int n, int r) {
    int i, j;

    // initialize by the first row
    row[0] = 1; // this is the value of C(0, 0)

    for(i = 1; i <= n; i++) {
        for(j = i; j > 0; j--) {
             // from the recurrence C(n, r) = C(n - 1, r - 1) + C(n - 1, r)
             row[j] += row[j - 1];
        }
    }

    return row[r];
}

内循环从末尾开始以简化计算.如果从索引0开始,则需要另一个变量来存储被覆盖的值.

Answer 2

我认为你的递归方法应该有效地工作DP.但是一旦限制增加,它就会开始出现问题.见http://www.spoj.pl/problems/MARBLES/

这是我在网上评委和编码比赛中使用的功能.所以它的工作速度非常快.

long combi(int n,int k)
{
    long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

这是您的方法#1的有效实施

Answer 3

你的递归方法很好，但在你的方法中使用 DP 将减少再次解决子问题的开销。现在因为我们已经有两个条件 -

nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);

nCr(n,0)=nCr(n,n)=1;

现在我们可以通过将子结果存储在二维数组中来轻松构建 DP 解决方案 -

int dp[max][max];
//Initialise array elements with zero
int nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1; //Base Case
       if(r==0) return dp[n][r] = 1; //Base Case
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r]; // Using Subproblem Result
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

现在，如果您想进一步优化，获得二项式系数的质因数分解可能是计算它的最有效方法，尤其是在乘法很昂贵的情况下。

我所知道的最快的方法是Vladimir's method。一种是通过将 nCr 分解为质因数来避免所有除法。正如 Vladimir 所说，您可以使用 Eratosthenes 筛法非常有效地完成此操作。此外，使用费马小定理来计算 nCr mod MOD（其中 MOD 是质数）。