Tous les défis
Facile 0 résolus 0 % de réussite

Coefficient binomial

Compter les façons de choisir k éléments parmi n (k parmi n).

Ce que vous allez apprendre

  • Calculer des combinaisons sans factorielles
  • Appliquer la formule de Pascal
  • Gérer le cas où k est supérieur à n

Problème

Le coefficient binomial C(n, k), qui se lit « k parmi n », est le nombre de façons de choisir k éléments parmi n éléments distincts, sans tenir compte de l'ordre. La formule n! / (k! (n − k)!) déborde très vite si l'on calcule d'abord les factorielles : construisez plutôt la réponse pas à pas, ou utilisez la formule de Pascal C(n, k) = C(n − 1, k − 1) + C(n − 1, k).

Implémentez binomial_coefficient(n, k).

Entrée

n : le nombre d'éléments.

k : le nombre d'éléments à choisir.

Sortie

Renvoyez C(n, k). Si k > n, aucun choix n'est possible : renvoyez 0.

Contraintes

0 ≤ n ≤ 66

0 ≤ k ≤ 100

Exemples

Exemple 1
Entrée :
n = 5
k = 2

Sortie attendue :
expected = 10
Entrée :
long long n = 5;
long long k = 2;

Sortie attendue :
long long expected = 10;
Entrée :
long n = 5;
long k = 2;

Sortie attendue :
long expected = 10;

Explication

On peut former 5 × 4 / 2 = 10 paires avec 5 éléments.

Exemple 2
Entrée :
n = 6
k = 0

Sortie attendue :
expected = 1
Entrée :
long long n = 6;
long long k = 0;

Sortie attendue :
long long expected = 1;
Entrée :
long n = 6;
long k = 0;

Sortie attendue :
long expected = 1;

Explication

Il y a exactement une façon de ne rien choisir : 1.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Les factorielles des nombres supérieurs à 20 ne tiennent pas sur 64 bits, évitez-les donc.

Indice 2

Une ligne du triangle de Pascal peut être mise à jour sur place, de droite à gauche.

Indice 3

C(n, k) est égal à C(n, n − k), et vaut 0 quand k > n.

Complexité attendue

temps O(n · k), espace supplémentaire O(k)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.