Quelle est la meilleure façon de calculer nCr

Approche 1:
C (n, r) = n! / (Nr)! R!

Approche 2:
Dans le livre Combinatorial Algorithms de wilf , j’ai trouvé ceci:
C (n, r) peut être écrit en tant que C(n-1,r) + C(n-1,r-1) .

par exemple

 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) 

Comme vous pouvez le constater, la solution finale ne nécessite aucune multiplication. Dans toute forme C (n, r), soit n == r ou r == 1.

Voici l’exemple de code que j’ai implémenté:

 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); } 

Voir la sortie ici.

Dans l’approche 2, il existe des sous-problèmes qui se chevauchent, nous appelons récursivité pour résoudre à nouveau les mêmes sous-problèmes. Nous pouvons l’éviter en utilisant la programmation dynamic .

Je veux savoir quel est le meilleur moyen de calculer C (n, r) ?.

    Les deux approches gagneront du temps, mais la première est très sujette au débordement d’entier .

    Approche 1:

    Cette approche générera des résultats dans les meilleurs délais (au plus n/2 itérations), et la possibilité de débordement peut être réduite en effectuant les multiplications avec précaution:

     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; } 

    Ce code commencera la multiplication du numérateur à partir de l'extrémité la plus petite, et comme le produit de k entiers consécutifs est divisible par k! , il n’y aura pas de problème de divisibilité. Mais la possibilité de débordement est toujours là, une autre astuce utile peut être de diviser n - r + i et i par leur GCD avant de procéder à la multiplication et à la division (et un débordement peut encore se produire).

    Approche 2:

    Dans cette approche, vous construirez réellement le sortingangle de Pascal . L'approche dynamic est beaucoup plus rapide que l'approche récursive (la première est O(n^2) tandis que l'autre est exponentielle). Cependant, vous devrez également utiliser la mémoire O(n^2) .

     # define MAX 100 // assuming we need first 100 rows long long sortingangle[MAX + 1][MAX + 1]; void makeTriangle() { int i, j; // initialize the first row sortingangle[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]; } 

    Ensuite, vous pouvez rechercher n’importe quel C(n, r) dans le temps O(1) .

    Si vous avez besoin d’un C(n, r) (c’est-à-dire que le sortingangle n’est pas nécessaire), vous pouvez utiliser O(n) en mémoire en écrasant la même ligne du sortingangle, de haut en bas.

     # 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]; } 

    La boucle interne est lancée à partir de la fin pour simplifier les calculs. Si vous le démarrez à partir de l'index 0, vous aurez besoin d'une autre variable pour stocker la valeur écrasée.

    Je pense que votre approche récursive devrait fonctionner efficacement avec DP . Mais il va commencer à donner des problèmes lorsque les contraintes augmentent. Voir http://www.spoj.pl/problems/MARBLES/

    Voici la fonction que j’utilise dans les juges en ligne et les concours de codage. Donc ça marche assez vite.

     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; } 

    C'est une implémentation efficace pour votre approche n ° 1

    Votre approche récursive convient, mais utiliser DP avec votre approche réduira à nouveau les frais généraux liés à la résolution de sous-problèmes.Maintenant, nous avons déjà deux conditions-

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

    Maintenant, nous pouvons facilement construire une solution DP en stockant nos sous-résultats dans un tableau 2D.

     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); } 

    Maintenant, si vous souhaitez approfondir la comparaison, il est probablement plus efficace de calculer le coefficient binomial en factorisation, en particulier si la multiplication est coûteuse.

    La méthode la plus rapide que je connaisse est celle de Vladimir . On évite toute division en décomposant nCr en facteurs premiers. Comme le dit Vladimir, vous pouvez le faire assez efficacement en utilisant le tamis d’Eratosthenes. Utilisez également le petit théorème de Fermat pour calculer nCr mod MOD (où MOD est un nombre premier).

     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;