Tutte le sfide
Media 0 risolte 0% di accettazione

Dismutazioni

Conta le permutazioni di n elementi in cui nessun elemento resta al suo posto.

Cosa imparerai

  • Trasformare un ragionamento di conteggio in una ricorrenza
  • Iterare una ricorrenza a partire dai casi base
  • Gestire i casi n = 0 e n = 1

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

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

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

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.