Cette semaine, c'est Thomas qui vous propose un #KataOfTheWeek : Algorithme mystère
Briefing du Kata : Parlons de ce fameux algorithme, avec des termes bien mathématiques : Soit la fonction récursive T
qui à n
associe un tableau. Le premier élément de la suite est défini comme suit :
T(1) = [0, 1]
Les autres éléments de la fonction T(n + 1)
sont définis en prenant 2 copies T(n)
. On inverse la seconde copie. On place un 0
devant chaque élément de la première copie, et un 1
devant chaque élément de la seconde et on les concatène. Ceci nous donne donc :
T(2) = [00, 01, 11, 10]
T(3) = [000, 001, 011, 010, 110, 111, 101, 100]
T(4) = [0000, 0001, 0011, 0010 ... 1010, 1011, 1001, 1000]
Maintenant parlons d'une autre fonction M(x)
où x
est un entier constitué de n
bit. M(x)
correspondra à la x
ieme entrée du tableau T(n)
convertie du binaire vers la base 10.
Ceci devrait être un peu plus clair avec un exemple… Typiquement M(6) = 5
, parce que 6
est constitué de 3
bits (110
) et que la 6
eme entrée de T(3)
est 101
soit 5
en base 10 ! Je vous laisse le temps de digérer avec d'autres exemples : M(3) = 2
, M(5) = 7
et M(10) = 15
.
Votre mission sera de coder M
dans un premier temps, ensuite si le cœur vous en dit, vous pourrez vous attaquer à I
qui est la fonction inverse. Grosso modo, M(6) = 5
, I(5) = 6
. Donc I(2) = 3
, I(7) = 5
et I(15) = 10
.
J'oubliais, vos fonctions M
et I
doivent pouvoir fournir un résultat en un temps raisonnable (< 5s
) pour des nombres un peu grand (> 100
).
Bon courage !
Saurez-vous résoudre le problème ?
Bon courage ! Retrouvez la solution dans cet article 😉