On a codé une chaîne de caractères en adoptant la transformation suivante :
Caractère
"A"
"B"
"C"
...
"Z"
Code
"1"
"2"
"3"
...
"26"
Ainsi, la chaîne "ABC" est devenue "123".
Cette méthode de chiffrement très rudimentaire présente plusieurs défauts. L'un d'entre eux est qu'elle n'est pas « injective » : plusieurs chaînes de départ peuvent donner le même code d'arrivée. En effet, le code "123" peut être déchiffré de plusieurs façons :
"1"+"2"+"3" qui donne "ABC" ;
"12""3" qui donne "LC" ;
"1"+"23" qui donne "AW".
Le code "123" peut donc être déchiffré de 3 façons différentes.
Écrire en python la fonction nb_chaines qui prend en paramètres une chaîne de caractères non vide code uniquement composée de chiffres ("0", "1", ..., "9") et renvoie le nombre de façons dont cette chaîne peut être déchiffrée.
On garantit que le code passé en paramètre correspond toujours à au moins une chaîne de caractères. On précise de plus que les chaînes "0", "01", "02", ..., "09" ne correspondent à aucun caractère (en effet "01" est différent de "1").
Exemples
>>> nb_chaines("5")# "E"1>>> nb_chaines("11")# "AA" ou "K"2>>> nb_chaines("123")# "ABC" ou "LC" ou "AW" 3>>> nb_chaines("11111111")# "AAAAAAAA" ou "AAAAAAK" ou ...34>>> nb_chaines("10101010")# "JJJJ"1
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
On peut résoudre le problème initial en parcourant le code au fur et à mesure. À chaque étape on fait une ou deux hypothèses (le chiffre à l'indice i est un code et/ou le couple des deux chiffres aux indices i et i+1 est un code).
Si l'on est en train de décoder le chiffre à l'indice i on peut se demander :
est-ce que ce chiffre est égal à "0" ? Tous les codes débutant par "0" ("0", "01", ..., "09") sont invalides. Dans ce cas, le décodage étudié est incorrect ;
s'il est différent "0", on peut :
passer au chiffre suivant d'indice i+1;
se demander si le couple des deux chiffres aux indices i et i+1 est valide (de "10" à "26"). Dans ce cas, on peut aussi sauter un chiffre et passer à celui d'indice i+2.
Si en effectuant ce parcours, on parvient à lire le code en entier (jusqu'à l'indice i==len(code)) alors ce décodage est valide.
On a ici décrit une approche récursive explorant les différents décodages jusqu'au cas de base que représente la fin du code. Il est aussi possible de procéder de façon itérative en « remontant » le code. On est alors certain de ne rencontrer que des décodages « valides ».
On notera enfin que différentes hypothèses (étude du chiffre à l'indice i ou du couple code[i]+code[i+1]) peuvent amener à l'étude de la même situation. Par exemple lors de l'étude du code "123", étudier "1" puis "2" ou étudier en une fois "12" amène dans les deux cas à étudier le chiffre "3".
Les sous-problèmes sont donc interdépendants. Afin d'éviter de répéter certains calculs (« combien de chaînes peuvent être décodées à partir du caractère d'indice i=2 ?»), on pourra conserver les résultats intermédiaires.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)