Calculer le coefficient binomial en C++ et Python
En combinatoire, le coefficient binomial est utilisé pour désigner le nombre de façons possibles de choisir un sous-ensemble d'objets d'une taille k dans un ensemble plus grand de taille n avec \( k\le n\).
Le coefficient binomial est noté \(\binom{n}{k}\) $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
Le coefficient binomial indique le nombre de combinaisons possibles de k objets à partir de n.
Exemple
Le nombre de façons possibles de choisir 2 objets parmi un ensemble de 5 objets est égal à $$\binom{5}{2} = \frac{5!}{2!(3)!} = \frac{5\times4\times3\times2\times1}{(2\times1)\times(3\times2\times1)}=5\times2=10$$
Lorsque nous traitons des combinaisons, nous devons garder à l'esprit que :
- L'ordre dans lequel les k objets sont sélectionnés n'a pas d'importance ;
- Chaque objet ne peut être sélectionné qu'une seule fois.
Écrivez un programme qui prend deux valeurs n et k et renvoie la valeur du coefficient binomial \(\binom{n}{k}\).
Entrée
Une ligne contient deux valeurs n et k
Sortie
La valeur du coefficient binomial \(\binom{n}{k}\)
Exemples
| Entrée du programme | Sortie du programme |
|---|---|
| 5 2 | 10 |
| 100 5 | 75287520 |
| 70 3 | 54740 |
Solution 1 : récursive
Une importante relation, la formule de Pascal, lie les coefficients binomiaux : pour tout couple (n,k) d'entiers naturels : $$\binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}$$ avec \(\binom{n}{0}=1\) et \(\binom{n}{n}=1\)
Voici une implémentation récursive simple qui suit simplement la structure récursive mentionnée ci-dessus.
#include <iostream>
using namespace std;
int coefBinomial(int n, int k){
if (k > n)
return 0;
if (k == 0 || k == n)
return 1;
return coefBinomial(n-1, k-1) + coefBinomial(n-1, k);
}
int main()
{
int n, k;
cin >> n >> k;
cout << coefBinomial(n,k);
return 0;
}
import sys
def coefBinomial(n, k):
if k > n:
return 0
if k == 0 or k == n:
return 1
return coefBinomial(n-1, k-1) + coefBinomial(n-1, k)
n,k = map(int, sys.stdin.readline().strip().split())
print(coefBinomial(n,k))
Complexité :
- Complexité temporelle : O(n*max(k,n-k))
- Complexité spatiale : O(n*max(k,n-k))
Solution 2 : Programmation dynamique
Il convient de noter que la fonction ci-dessus calcule encore et encore les mêmes sous-problèmes. Voir l'arbre de récurrence suivant pour n = 5 et k = 2. La fonction C(3, 1) est appelée deux fois. Pour de grandes valeurs de n, il y aura de nombreux sous-problèmes communs.
Étant donné que les mêmes sous-problèmes sont appelés à nouveau, ce problème a la propriété chevauchement de sous-problème, de sorte que le problème peut être résolu à l'aide de la programmation dynamique.
#include <iostream>
using namespace std;
int coefBinomial(int n, int k){
int C[n + 1][k + 1];
int i, j;
for (i = 0; i <= n; i++) {
for (j = 0; j <= min(i, k); j++) {
// cas de base
if (j == 0 || j == i)
C[i][j] = 1;
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
return C[n][k];
}
int main()
{
int n, k;
cin >> n >> k;
cout << coefBinomial(n,k);
return 0;
}
import sys
def coefBinomial(n, k):
C = [[0 for x in range(k+1)] for x in range(n+1)]
for i in range(n+1):
for j in range(min(i, k)+1):
# cas de base
if j == 0 or j == i:
C[i][j] = 1
else:
C[i][j] = C[i-1][j-1] + C[i-1][j]
return C[n][k]
n,k = map(int, sys.stdin.readline().strip().split())
print(coefBinomial(n,k))
Complexité :
- Complexité temporelle : O(n*k)
- Complexité spatiale : O(n*k)
Solution 3 : Meilleure solution
Nous pouvons calculer le coefficient binomial en temps linéaire si nous observons ce qui suit : $$\binom{n}{k} = \frac{n!}{k!(n-k)!}=\frac{n\times(n-1)\times(n-2)\times\dots\times(n-k+1)}{k!}$$
Il faut noter que \(\binom{n}{k}=\binom{n}{n-k}\)
#include <iostream>
using namespace std;
int coefBinomial(int n, int k){
if(k>(n-k))
k=n-k;
int coef=1;
/*
Calculer la valeur de [n * (n-1) *---* (n-k + 1)]
/ [k * (k-1) *----* 1]
*/
for(int i=0;i<k;i++){
coef *= (n-i);
coef /= (i+1);
}
return coef;
}
int main()
{
int n, k;
cin >> n >> k;
cout << coefBinomial(n,k);
return 0;
}
import sys
def coefBinomial(n, k):
if(k>(n-k)):
k=n-k
coef=1
# Calculer la valeur de [n * (n-1) *---* (n-k + 1)]
# / [k * (k-1) *----* 1]
for i in range(k):
coef=coef*(n-i)
coef=coef//(i+1)
return coef
n,k = map(int, sys.stdin.readline().strip().split())
print(coefBinomial(n,k))
Complexité :
- Complexité temporelle : O(min(k,n-k))
- Complexité spatiale : O(1)
