这是更好的方式来计算nCr的

这是更好的方式来计算nCr的

本文介绍了这是更好的方式来计算nCr的的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

方法1:
C(N,R)= N!/(N-R)! - [R!

Approach 1:
C(n,r) = n!/(n-r)!r!

方法2:
在这本书中的Combinatorial通过维尔夫算法,我发现这一点:
C(N,R)可以写成 C(N-1,R)+ C(N-1,R-1)

Approach 2:
In the book Combinatorial Algorithms by wilf, i have found this:
C(n,r) can be written as 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- = = R1或R2 = = 1。

As you can see, the final solution doesn't need any multiplication. In every form C(n,r), either n==r or r==1.

下面是示例codeI已经实现了:

Here is the sample code i have implemented:

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,也有重叠的子问题,我们呼吁递归再次解决同样的子问题。我们可以通过使用动态规划避免它。

In the approach 2, there are overlapping sub-problems where we are calling recursion to solve the same sub-problems again. We can avoid it by using Dynamic Programming.

我想知道哪个是更好的方式来计算C(N,R)?

I want to know which is the better way to calculate C(n,r)?.

推荐答案

这两种方法都可以节省时间,但第一个是很容易出现的。

Both approaches will save time, but the first one is very prone to integer overflow.

方法一:

此方法会产生的结果在最短的时间内(在大多数 N / 2 迭代),和溢出的可能性,可以通过仔细做乘法减少:

This approach will generate result in shortest time (in at most n/2 iterations), and the possibility of overflow can be reduced by doing the multiplications carefully:

long long C(int n, int r) {
    if(r > n / 2) 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;
}

这code将开始小端分子的增殖,并作为任何 K 产品连续整数的整除 ķ!,就不会有整除问题。但溢出的可能性还是存在的,另外一个有用的技巧,可以划分 N - R + I 由他们GCD前做乘法和除法(和还是的可能发生溢出)。

This code will start multiplication of the numerator from the smaller end, and as the product of any k consecutive integers is divisible by k!, there will be no divisibility problem. But the possibility of overflow is still there, another useful trick may be dividing n - r + i and i by their GCD before doing the multiplication and division (and still overflow may occur).

方法2:

在这种方法中,你会真正建立在杨辉三角。动态方法比递归快得多(第一个是为O(n ^ 2),而另一个是指数)。但是,你需要使用为O(n ^ 2)内存了。

In this approach, you'll be actually building up the Pascal's Triangle. The dynamic approach is much faster than the recursive one (the first one is O(n^2) while the other is exponential). However, you'll need to use O(n^2) memory too.

# 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)通过覆盖三角形的同一行,从上到下。

If you need a particular C(n, r) (i.e. the full triangle is not needed), then the memory consumption can be made O(n) by overwriting the same row of the triangle, top to bottom.

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

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开始,你就需要另一个变量来存储值被覆盖。

The inner loop is started from the end to simplify the calculations. If you start it from index 0, you'll need another variable to store the value being overwritten.

这篇关于这是更好的方式来计算nCr的的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-03 13:08