Structure de données et algorithmes - Tour de Hanoi

Tour de Hanoi, est un puzzle mathématique qui se compose de trois tours (chevilles) et plus d'un anneaux est comme représenté -

Ces anneaux sont de tailles différentes et empilés dans un ordre croissant, c'est-à-dire que le plus petit se place sur le plus grand. Il existe d'autres variantes du puzzle où le nombre de disques augmente, mais le nombre de tours reste le même.

Règles

La mission est de déplacer tous les disques vers une autre tour sans violer la séquence d'arrangement. Quelques règles à suivre pour la tour de Hanoi sont:

• Un seul disque peut être déplacé entre les tours à un moment donné.
• Seul le disque "supérieur" peut être supprimé.
• Aucun grand disque ne peut reposer sur un petit disque.

Voici une représentation animée de la résolution d'un puzzle de la Tour de Hanoi avec trois disques.

Le puzzle de la tour de Hanoi avec n disques peut être résolu au minimum 2ⁿ−1pas. Cette présentation montre qu'un puzzle avec 3 disques a pris2³ - 1 = 7 pas.

Algorithme

Pour écrire un algorithme pour la tour de Hanoi, nous devons d'abord apprendre à résoudre ce problème avec moins de disques, disons → 1 ou 2. Nous marquons trois tours avec un nom, source, destination et aux(uniquement pour aider à déplacer les disques). Si nous n'avons qu'un seul disque, il peut facilement être déplacé de la source à la destination.

Si nous avons 2 disques -

• Tout d'abord, nous déplaçons le plus petit disque (du haut) vers aux peg.
• Ensuite, nous déplaçons le plus grand disque (du bas) vers la cheville de destination.
• Et enfin, nous déplaçons le plus petit disque de aux à destination.

Alors maintenant, nous sommes en mesure de concevoir un algorithme pour la tour de Hanoi avec plus de deux disques. Nous divisons la pile de disques en deux parties. Le plus grand disque (n ^ème disque) est dans une partie et tous les autres (n-1) disques sont dans la seconde partie.

Notre objectif ultime est de déplacer le disque nde la source à la destination, puis placez-y tous les autres disques (n1). On peut imaginer appliquer la même chose de manière récursive pour tout ensemble donné de disques.

Les étapes à suivre sont -

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Un algorithme récursif pour la tour de Hanoi peut être piloté comme suit -

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Pour vérifier l'implémentation en programmation C, cliquez ici .