Exercice 2

A chaque execution de la procédure Hanoï on associe une chaîne de caractères de la façon suivante: Un déplacement d'une rondelle du piquet 1 vers le piquet 3 est noté par le symbole a, du piquet 1 vers le piquet 2 par le symbole b et du piquet 2 vers le piquet 3 par c. Les déplacements inverses sont notés par les mêmes lettres avec une barre dessus (). Ainsi la chaîne de caractères correspondant au déplacement de deux rondelles du piquet 1 vers le piquet 3 selon l'algorithme décrit en cours est : Celle correspondant au déplacement de trois rondelles du piquet 1 vers le piquet 3 est :

1. Donner la chaîne correspondant au déplacement de 4 rondelles.
2. Quelle est la longueur de la chaine correspondant au déplacement de n rondelles ?
3. En s' aidant des transformations suivantes sur les caractères donnez un procédé de calcul de la chaîne en connaissant .

4. Montrez que lorsque l'on supprime les barres au dessus des caractères intervenant dans la chaîne on obtient une chaîne très régulière.
5. En déduire une procédure itérative permettant de résoudre le problème des tours de Hanoï.