Les tours de Hanoï

Le problème

L'exemple le plus classique de procédure récursive est sans conteste celui des tours de Hanoï. On dispose de 3 piquets numérotés 1, 2, 3 de gauche à droite. N rondelles de tailles différentes entourent le piquet 1 formant une tour (la plus grosse rondelle en bas et la plus petite en haut). Le but du jeu consiste à amener toutes les rondelles du piquet 1 au piquet 3 en respectant les deux règles suivantes :

déplacer une rondelle à la fois,
ne jamais mettre une rondelle au dessus d'une plus petite.

Un raisonnement par récurrence correct conduit à un programme de quelques lignes au plus.

Vous pouvez exécuter ce programme ici.

Programmation

On utilisera les structures de piles pour gérer les rondelles sur les piquets. Il convient donc de définir une structure de pile et d'écrire les procédures ou fonctions permettant

d'initialiser une pile,
d'empiler un élément,
de dépiler un élément,
de savoir si une pile est vide ou non,
d'afficher les piles (procédure pouvant être très simple ou très sophistiquée),
de résoudre le problème.

Complexité

Montrer que le nombre de déplacements pour N rondelles est égal à 2^N -1. Pour mémoire, à raison d'un déplacement tous les millième de seconde, cela ferait un peu plus de 584 Milliards d'années à pour N=64 !!!! les bonzes de la ville de Hanoï à l'origine de ce problème pour 64 rondelles avaient de quoi atteindre le Nirvana de Boudha ...