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
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.
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.