这是计算nCr的更好方法
方法1：
C（n，r）= n！/（nr）！r！
方法2：
在wilf的“ Combinatorial Algorithms ”一书中，我发现了这个：
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)
如您所见，最终解决方案不需要任何乘法。 在每种formsC（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）的更好方法？
这两种方法都可以节省时间，但第一种方法很容易出现整数溢出 。
方法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!整除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]; }
然后你可以在O(1)时间内查找任何C(n, r) 。
如果你需要一个特定的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开始，则需要另一个变量来存储被覆盖的值。
我认为你的递归方法应该可以有效地与DP一起工作。 但是一旦限制增加，它就会开始出现问题。 见http://www.spoj.pl/problems/MARBLES/
这是我在网上评委和编码比赛中使用的function。 所以它的工作速度非常快。
long combi(int n,int k) { long ans=1; k=k>nk?nk: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的有效实施
您的递归方法很好，但使用DP与您的方法将减少再次解决子问题的开销。现在我们已经有两个条件 –
nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r); nCr(n,0)=nCr(n,n)=1;
现在我们可以通过将子结果存储在二维arrays中来轻松构建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); }
现在，如果你想进一步加强，那么得到二项式系数的素数因子化可能是计算它的最有效方法，特别是如果乘法是昂贵的。
我所知道的最快的方法是弗拉基米尔的方法 。 通过将nCr分解为素因子，可以避免一起划分。 正如Vladimir所说，你可以使用Eratosthenes筛子非常有效地做到这一点。同时，使用Fermat的小定理来计算nCr mod MOD（其中MOD是素数）。
unsigned long long ans = 1,a=1,b=1; int k = r,i=0; if (r > (nr)) k = nr; for (i = n ; k >=1 ; k--,i--) { a *= i; b *= k; if (a%b == 0) { a = (a/b); b=1; } } ans = a/b;