哪种是计算nCr的更好方法

一尘不染

哪种是计算nCr的更好方法

algorithm

方法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）的更好方法？

阅读 456

2020-07-28

共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 仍可能发生溢出）。

方法二：

通过这种方法，您实际上将建立Pascal的Triangle。动态方法比递归方法快得多（第一种是递归的，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];

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开始，则需要另一个变量来存储要覆盖的值。

2020-07-28