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.
Solution

> Haut de la page