Problema
Cinque amici mettono i cappelli in un mucchio e ognuno ne riprende uno a caso. In quanti modi può succedere che nessuno riprenda il proprio? Una permutazione di n elementi in cui nessun elemento resta nella sua posizione originale si chiama dismutazione (in inglese derangement). I valori iniziano con 1, 0, 1, 2, 9, 44 e seguono la formula D(n) = (n − 1) × (D(n − 1) + D(n − 2)).
Implementa derangements(n).
Input
n: il numero di elementi.
Output
Restituisci il numero di dismutazioni di n elementi. D(0) vale 1 (la permutazione vuota non sposta nulla che potrebbe restare fermo) e D(1) vale 0.
Vincoli
0 ≤ n ≤ 20
Esempi
Input:
n = 3
Output atteso:
expected = 2
Input:
long long n = 3;
Output atteso:
long long expected = 2;
Input:
long n = 3;
Output atteso:
long expected = 2;
Spiegazione
Con gli elementi A, B, C solo BCA e CAB spostano tutti gli elementi, quindi la risposta è 2.
Input:
n = 4
Output atteso:
expected = 9
Input:
long long n = 4;
Output atteso:
long long expected = 9;
Input:
long n = 4;
Output atteso:
long expected = 9;
Spiegazione
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Parti da D(0) = 1 e D(1) = 0.
Suggerimento 2
Ogni valore successivo usa i due precedenti e il valore corrente di n.
Suggerimento 3
In ogni momento servono solo gli ultimi due valori.
Complessità attesa
tempo O(n), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.