Problème
Cinq amis posent leurs chapeaux en tas, puis chacun en reprend un au hasard. De combien de façons peut-il arriver que personne ne récupère le sien ? Une permutation de n éléments dans laquelle aucun élément ne reste à sa position d'origine s'appelle un dérangement. Les premiers nombres de dérangements sont 1, 0, 1, 2, 9, 44, et ils vérifient D(n) = (n − 1) × (D(n − 1) + D(n − 2)).
Implémentez derangements(n).
Entrée
n : le nombre d'éléments.
Sortie
Renvoyez le nombre de dérangements de n éléments. D(0) vaut 1 (la permutation vide ne déplace aucun élément qui pourrait rester en place) et D(1) vaut 0.
Contraintes
0 ≤ n ≤ 20
Exemples
Entrée :
n = 3
Sortie attendue :
expected = 2
Entrée :
long long n = 3;
Sortie attendue :
long long expected = 2;
Entrée :
long n = 3;
Sortie attendue :
long expected = 2;
Explication
Pour les éléments A, B, C, seules BCA et CAB déplacent tous les éléments, donc la réponse est 2.
Entrée :
n = 4
Sortie attendue :
expected = 9
Entrée :
long long n = 4;
Sortie attendue :
long long expected = 9;
Entrée :
long n = 4;
Sortie attendue :
long expected = 9;
Explication
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Partez de D(0) = 1 et D(1) = 0.
Indice 2
Chaque nouvelle valeur utilise les deux précédentes et la valeur courante de n.
Indice 3
Seules les deux dernières valeurs sont utiles à chaque étape.
Complexité attendue
temps O(n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.