方法1:
C(N,R)= N!/(NR)! - [R!
方法2:
在这本书中组合算法通过维尔夫 ,我发现这一点:
在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)?
这两种方法都可以节省时间,但第一个是很容易出现整数溢出 。
方法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:
在这种方法中,你会真正建立了杨辉三角 。 动态方法是比递归一个快得多(第一个是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开始吧,你需要另一个变量来存储被覆盖的值。
我觉得你的递归方法应与有效的工作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的有效实施
你递推是好的,但使用DP与你的做法会降低again.Now解决子问题的开销,因为我们已经有两个条件 -
nCr(n,r) = nCr(n-1,r-1) + nCr(n-1,r);
nCr(n,0)=nCr(n,n)=1;
现在,我们可以很容易地通过存储在2 d我们的子结果建立一个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);
}
现在,如果你想进一步otimise,获取二项式系数的因式分解是可能来计算的话,特别是如果乘法是昂贵的最有效的方式。
我知道的最快方法是弗拉基米尔的方法 。 一个通过分解nCr的为素数因子避免师一起。 正如普京说,你可以使用埃拉托色尼sieve.Also,使用费马小定理计算nCr的MOD MOD(其中MOD是一个素数)很有效地做到这一点。
使用动态编程,你可以很容易地在这里找到,NCR是解决方案
package com.practice.competitive.maths;
import java.util.Scanner;
public class NCR1 {
public static void main(String[] args) {
try (Scanner scanner = new Scanner(System.in)) {
int testCase = scanner.nextInt();
while (testCase-- > 0) {
int n = scanner.nextInt();
int r = scanner.nextInt();
int[][] combination = combination();
System.out.println(combination[n][r]%1000000007);
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static int[][] combination() {
int combination[][] = new int[1001][1001];
for (int i = 0; i < 1001; i++)
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i)
combination[i][j] = 1;
else
combination[i][j] = combination[i - 1][j - 1] % 1000000007 + combination[i - 1][j] % 1000000007;
}
return combination;
}
}
unsigned long long ans = 1,a=1,b=1;
int k = r,i=0;
if (r > (n-r))
k = n-r;
for (i = n ; k >=1 ; k--,i--)
{
a *= i;
b *= k;
if (a%b == 0)
{
a = (a/b);
b=1;
}
}
ans = a/b;