Le principe des tours de Hanoï est simple : on dispose de 3 tiges et de n anneaux percés dont le diamètre est croissant. Au départ, les anneaux sont disposés sur une même tige, dans l'ordre des diamètres (le plus gros en bas, le plus petit en haut), formant donc une sorte de pyramide.
Le but est de déplacer les anneaux d'une tige à l'autre, dans l'optique de déplacer l'ensemble de la pyramide sur une autre tige. En déplaçant les anneaux, on doit respecter la règle suivante : un anneau ne peut être déplacé que sur une tige vide ou au dessus d'un anneau plus gros.
Par exemple pour 2 anneaux, on peut faire ces mouvements :

Par contre, si vous avez beaucoup d'anneaux, ça devient très difficile ! Le but de cet exercice est d'écrire un programme qui reçoit un entier n et affiche la liste des mouvements à effectuer pour déplacer les anneaux de la tige A à la tige C. Par exemple, pour 2, il doit afficher :
   Déplacer de A à B
   Déplacer de A à C
   Déplacer de B à C
En utilisant la boucle interactive, la fonction print_string permet d'afficher une chaîne de caractères. La fonction print_newline passe à la ligne suivante.

1) Commencez par écrire une fonction affiche qui prend en argument deux caractères (parmi a, b ou c) et qui affiche le déplacement correspondant. Par exemple, si on tape affiche 'a' 'b', la fonction affiche « Déplacer un anneau de a vers b » (ou une autre phrase de votre choix !). La fonction doit également passer à la ligne après l'affichage (comme ça, l'affichage suivant se fera en dessous, c'est plus lisible).
La seule difficulté est qu'il faut transformer les deux caractères en chaînes de caractères, pour les insérer dans la phrase :
let affiche depart arrivee = let phrase = "Déplacer de "^(String.make 1 depart)^" vers "^(String.make 1 arrivee)
in print_string phrase; print_newline();;
Remarque : au lieu d'utiliser print_newline, on peut créer une nouvelle ligne en ajoutant à la fin de la phrase le caractère spécial \n, qui signifie justement « nouvelle ligne ». Cela donne la fonction :
let affiche depart arrivee = let phrase = "Déplacer de "^(String.make 1 depart)^" vers "^(String.make 1 arrivee)^"\n"
in print_string phrase;;

2) A présent, réfléchissons. En fait, le problème des tours de Hanoï est un problème récursif. Essayez de comprendre pourquoi. Déduisez-en comment on doit faire pour déplacer n anneaux de a vers b.
En fait, pour déplacer n anneaux de a vers b, on n'a qu'une possibilité :
   - il est obligatoire de commencer par déplacer les (n-1) plus petits anneaux, pour débloquer le plus gros : on est amené à une récurrence sur n.
   - une fois qu'il est débloqué, il faut le mettre sur la tige b. Sauf que la tige b doit être libre, car sinon, déplacer le gros anneau est impossible. Ainsi dans l'étape précédente, le déplacement devait se faire en direction de la troisième tige c.
   - une fois qu'il est déplacé, on redéplace les (n-1) autres anneaux sur lui : autre récurrence sur n.
Pour déplacer n anneaux de la tige a vers la tige b, on doit donc faire trois étapes :
   - déplacer (n-1) anneaux de a vers c (appel récursif)
   - déplacer un anneau de a vers b (on utilise la fonction affiche)
   - déplacer (n-1) anneaux de c vers b (appel récursif).

3) Petit utilitaire : on a besoin d'une fonction autre qui prend en argument deux caractères différents parmi 'a', 'b' ou 'c' et qui rend le caractère qui n'est pas présent (par exemple autre 'c' 'a' doit donner 'b')
Le plus simple est d'envisager les six cas possibles :
let autre tige1 tige2 = match tige1 with
   |'a' -> if tige2 = 'b' then 'c' else 'b'
   |'b' -> if tige2 = 'a' then 'c' else 'a'
   |'c' -> if tige2 = 'b' then 'a' else 'b';;
Notez que Caml nous avertit que le filtrage n'est pas exhaustif. Ce n'est pas grave car nous savons que nous n'utiliserons aucun autre caractère.

4) Ecrivez alors une fonction récursive deplacements qui prend en argument le nombre d'anneaux à déplacer, la tige de départ (sous forme d'un caractère : 'a', 'b' ou 'c') et la tige d'arrivée. Elle affiche alors la succession des mouvements pour déplacer les anneaux de la tige de départ à la tige d'arrivée.
Solution

> Haut de la page