Tours de Hanoï

Le problème des tours de Hanoi est un grand classique de la récursivité car la solution itérative est relativement complexe. On dispose de 3 tours appelées A, B et C. La tour A contient n disques empilés par ordre de taille décroissante qu’on veut déplacer sur la tour B dans le même ordre en respectant les contraintes suivantes :

-          On ne peut déplacer qu’un disque à la fois

-          On ne peut empiler un disque que sur un disque plus grand ou sur une tour vide.

Ainsi, le paramétrage de la procédure déplacer sera le suivant :
Procédure déplacer(n : Entier ; A, B, C : Caractère)
Lorsque la tour A ne contient qu’un seul disque, la solution est évidente : il s’agit de réaliser un transfert de la tour A vers B. Ce cas constitue donc la condition de sortie (point d’appui).

Ainsi, pour déplacer n disques de A vers B en utilisant éventuellement C, il faut :
1- déplacer (n-1) disques de A vers C en utilisant éventuellement B
2- réaliser un transfert du disque de A sur B
3- déplacer (n-1) disques de C vers B en utilisant éventuellement A

Procédure déplacer (n : Entier; A,B,C : Caractère);
Début
Si (n=1) Alors Ecrire(A,' -> ',B)
Sinon
déplacer(n-1, A, C, B); Ecrire(A,' -> ',B);
déplacer(n-1, C, B, A);
FinSi
Fin

Voici le résultat de l’exécution de cette procédure avec 3 disques placés initialement sur A

Complexité de l’algorithme tours de hanoi :

Combien de mouvements au minimum pour déplacer une tour de n disques. La complexité exacte de l'algorithme présenté ci-dessus est en 2ⁿ-1 pour n disques à déplacer de la tour A vers la tour B. Avec la notation asymptotique, on dit qu'il s'agit là d'une complexité exponentielle, c'est à dire en O(2ⁿ).