Cette semaine, c'est Morgan qui vous propose un #KataOfTheWeek : Calcul de sous-factorielles
Briefing du Kata : En mathématiques, la factorielle d'un entier n est le produit de tous les nombres positifs inférieurs ou égaux à n et elle est notée n!. Par exemple :
- 3! = 3 * 2 * 1 = 6
- 5! = 5 * 4 * 3 * 2 * 1 = 120
Plus concrètement, la factorielle représente aussi le nombre de permutations possibles d'un ensemble d'élément. C'est-à-dire que la factorielle de 5 peut représenter le nombre de possibilités pour garer 5 voitures sur 5 places différentes.
La sous-factorielle, aussi appelé dérangement est un peu différente. Elle représente l'ensemble des permutations d'un ensemble d'élément telles qu'aucun des éléments ne se retrouve à sa place initiale. Elle est notée !n.
En reprenant l'exemple des voitures, si on a 3 places initialement associées à 3 voitures :
Place 1Place 2Place 3V1V2V3
Les permutations valables sont donc :
Place 1Place 2Place 3V2V3V1V3V1V2
Donc !3 = 2
Quelques valeurs :
- !0 = 1
- !1 = 0
- !2 = 1
- !3 = 2
- !4 = 9
L'objectif de ce kata est de créer un algorithme récursif qui à partir d'une entrée n
(entier positif) affiche en sortie la valeur de de !n
(sous-factorielle de n
).
Votre programme doit être capable de calculer les valeurs suivantes :
!5 = 44
!10 = 1334961
!15 = 481066515734
Saurez-vous résoudre le problème ?
Bon courage ! Retrouvez la solution dans cet article 😉