Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

Calculer le coefficient binomial en C++ et Python

 

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 programmeSortie du programme
5 210
100 575287520
70 354740

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)

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.