Problema
Il coefficiente binomiale C(n, k), che si legge «n su k», è il numero di modi di scegliere k elementi tra n elementi distinti quando l'ordine non conta. La formula n! / (k! (n − k)!) va presto in overflow se calcoli prima i fattoriali, quindi costruisci il risultato passo dopo passo oppure usa la relazione del triangolo di Tartaglia C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Implementa binomial_coefficient(n, k).
Input
n: il numero di elementi.
k: quanti elementi scegliere.
Output
Restituisci C(n, k). Se k > n non c'è modo di scegliere, quindi restituisci 0.
Vincoli
0 ≤ n ≤ 66
0 ≤ k ≤ 100
Esempi
Input:
n = 5
k = 2
Output atteso:
expected = 10
Input:
long long n = 5;
long long k = 2;
Output atteso:
long long expected = 10;
Input:
long n = 5;
long k = 2;
Output atteso:
long expected = 10;
Spiegazione
Le coppie che si possono formare con 5 elementi sono 5 × 4 / 2 = 10.
Input:
n = 6
k = 0
Output atteso:
expected = 1
Input:
long long n = 6;
long long k = 0;
Output atteso:
long long expected = 1;
Input:
long n = 6;
long k = 0;
Output atteso:
long expected = 1;
Spiegazione
C'è esattamente un modo di non scegliere nulla: 1.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
I fattoriali dei numeri oltre 20 non stanno in 64 bit, quindi evitali.
Suggerimento 2
Una riga del triangolo di Tartaglia si può aggiornare sul posto, da destra a sinistra.
Suggerimento 3
C(n, k) è uguale a C(n, n − k), e vale 0 quando k > n.
Complessità attesa
tempo O(n · k), spazio aggiuntivo O(k)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.