Tutte le sfide
Facile 0 risolte 0% di accettazione

Coefficiente binomiale

Conta i modi di scegliere k elementi su n (n su k).

Cosa imparerai

  • Calcolare le combinazioni senza fattoriali
  • Applicare la relazione del triangolo di Tartaglia
  • Gestire il caso k maggiore di n

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

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

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

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.