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 xieme 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 6eme 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 😉