Algorithme de la Tour de Hanoï : Python, C++ Code

Qu'est-ce que la Tour de Hanoï ?

La Tour de Hanoï est un puzzle mathématique composé de trois tiges et de nombreux disques superposés. Elle est également connue sous le nom de Tour de Brahma ou Tour Lucas, comme l'a présenté le mathématicien français Edouard Lucas en 1883. Ce puzzle est basé sur des légendes sur le déplacement de disques d'or entre trois tiges.

Ce puzzle comporte trois tiges et un nombre variable de disques empilés. Ces cannes sont conçues comme des tours cycliques. Ainsi, les disques de plus grand diamètre sont empilés en bas et les disques plus petits sont empilés en haut.

Dans un premier temps, on nous donne trois piquets ou tiges. Et l'un d'eux (A, illustré dans l'exemple) a tous les disques empilés. Notre objectif est de déplacer une pile entière de disques d'une tige (A) à une autre (C) en obéissant à certaines règles spécifiques.

Voici la configuration initiale du puzzle-

Et c'est le but final-

Règles de la Tour de Hanoï

Voici quelques règles essentielles pour la Tour de Hanoï :

L'état initial de ce puzzle, tous les disques seront empilés dans la première tige.
L'état final est que tous les disques de la tige un seront empilés sur la tige deux ou sur la tige trois.
Nous pouvons déplacer un disque d’une tige à une autre à tout moment.
Nous ne pouvons déplacer que le disque supérieur de la tige.
Un disque ne peut pas être placé sur un autre disque, plus petit.

La légende originale parlait du déplacement de 64 disques. Les prêtres pouvaient déplacer un disque à la fois selon les règles. Selon la légende, il y avait une prophétie selon laquelle le monde prendrait fin s'ils parvenaient à accomplir l'acte. Dans la section sur la complexité temporelle, nous montrerons qu'un réglage de la Tour de Hanoï avec n disques coûterait 2 ^ n – 1 coup.

Ainsi, si les prêtres pouvaient avoir besoin d'une seconde pour déplacer les disques, le temps total dont ils auraient besoin pour résoudre le puzzle serait de 1^2 – 64 seconde ou 1 584,942,417,356 26 7 ans, 15 jours, heures et secondes.

Algorithme pour la Tour de Hanoi

Une manière générale de résoudre la Tour de Hanoï est un algorithme récursif. Tout d’abord, nous devons choisir deux tiges ou piquets comme source et destination, et le piquet de rechange serait un auxiliaire ou une aide.

Voici les étapes pour résoudre le puzzle de la Tour de Hanoï :

Déplacez les n-1 premiers disques du rattachement source vers le rattachement auxiliaire.
Ensuite, déplacez le nième disque du rattachement source vers le rattachement de destination.
Enfin, déplacez les n-1 disques restants de la cheville auxiliaire vers la cheville de destination.

Notes: Si nous avons un seul disque, nous pouvons le déplacer directement de la source à la destination.

Comment résoudre le puzzle de la Tour de Hanoi

Illustrons l'algorithme pour trois disques et considérons la cheville A comme source, la cheville B comme assistant et la cheville C comme destination.

Étape 1) Initialement, tous les disques seront empilés sur le plot A.

À ce stade:

Source = cheville A
Destination = cheville C
Aide = cheville B

Maintenant, nous devons déplacer les n-1 premiers disques de la source vers l'assistant.

Remarque : Bien que nous ne puissions déplacer qu'un seul disque à la fois, cela fait passer notre problème d'un problème à 3 disques à un problème à 2 disques, ce qui est un appel récursif.

Étape 2) Comme nous appelons un appel récursif depuis le piquet A et que la destination est le piquet B, nous utiliserons le piquet C comme assistant.

Notez que nous sommes à nouveau à la première étape pour le même problème de tour de Hanoi pour deux disques.

Nous devons maintenant déplacer n-1 ou un disque de la source vers l'assistant, en déplaçant le plus petit disque de la cheville A à la cheville C.

À ce stade:

Source = cheville A
Destination = piquet B
Aide = cheville C

Étape 3) Ensuite, selon notre algorithme, le nième ou le deuxième disque nécessaire doit être transféré vers la destination ou le chevillement B.

À ce stade:

Source = cheville A
Destination = piquet B
Aide = cheville C

Étape 4) Maintenant, nous allons déplacer les n-1 disques ou le disque un de l'assistant ou du chevillement C vers la destination ou le chevillement B selon la troisième étape de notre algorithme.

À ce stade:

Source = cheville A
Destination = piquet B
Aide = cheville C

Étape 5) Après avoir terminé l'appel récursif, nous reviendrons à notre paramètre précédent lors de la première étape de l'algorithme.

Étape 6) Maintenant, dans la deuxième étape, nous allons déplacer notre source vers notre destination, qui déplace le disque 3 vers le plot C depuis le plot A.

À ce stade:

Source = cheville A
Destination = piquet C
Aide = cheville B

Étape 7) Maintenant nous pouvons voir ça

d consiste à déplacer les disques restants de l'assistant (peg B) vers la destination (peg C). Nous utiliserons la source initiale ou le rattachement A comme aide dans ce cas.

Étape 8) Comme nous ne pouvons pas déplacer deux disques simultanément, nous ferons un appel récursif pour le disque 1. D'après la dernière étape et notre algorithme, une destination dans cette étape est le piquet A.

À ce stade:

Source = cheville B
Destination = piquet A
Aide = cheville C

Étape 9) Notre appel récursif est maintenant terminé. Ensuite, nous déplaçons le disque 2 de sa source vers sa destination.

À ce stade:

Source = cheville B
Destination = piquet C
Aide = cheville A

Étape 10) Ensuite, nous déplaçons notre n-1 ou disque 1 restant de l'assistant vers la destination.

À ce stade:

Source = cheville A
Destination = piquet C
Aide = cheville B

Pseudo-code de la tour de Hanoï

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
  		IF disk == 1, THEN
      			move disk from source to dest             
   		ELSE
     			Tower_Of_Hanoi (disk - 1, source, helper, dest)     
      			move disk from source to dest          
      			Tower_Of_Hanoi (disk - 1, helper, dest, source)     
   		END IF   
END Procedure

Code de programme dans C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
  if (num == 1) {
    cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
    return;
  }
  tower_of_hanoi(num - 1, source, helper, dest);
  cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
  tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
  int num;
  cin >> num;
  printf("The sequence of moves :\n");
  tower_of_hanoi(num, "I", "III", "II");
  return 0;
}

Sortie

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Code de programme dans Python

def tower_of_hanoi(n, source, destination, helper):
	if n==1:
		print ("Move disk 1 from peg", source," to peg", destination)
		return
	tower_of_hanoi(n-1, source, helper, destination)
	print ("Move disk",n," from peg", source," to peg", destination)
	tower_of_hanoi(n-1, helper, destination, source)		
# n = number of disks
n = 3
tower_of_hanoi(n,' A','B','C')

Sortie :

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Complexité de la Tour de Hanoï

Voici la complexité temporelle et spatiale de la tour de Hanoï :

1) Complexité temporelle :

Si nous revenons sur notre algorithme, nous pouvons voir que nous introduisons deux fois un appel récursif pour (n-1) disques. Ces appels récursifs pour (n-1) disques peuvent être décomposés en d'autres ((n-1)-1) et ainsi de suite jusqu'à ce que nous n'ayons qu'un seul disque à déplacer.

Pour trois disques-

Le disque 3 appelle deux fois une fonction récursive pour le disque deux.
Le disque 2 appelle deux fois une fonction récursive pour le disque un.
Le disque 1 peut se déplacer dans un temps constant et un temps pour résoudre trois disques.

= 2*(Temps de résolution pour deux disques) + Temps constant pour déplacer le disque 3

= 2*(2*temps pour résoudre un disque + temps constant pour déplacer le disque 2) + temps constant pour déplacer le disque 3

= (2*2) (temps constant pour déplacer le disque 1) + 2*temps constant pour déplacer le disque 2 + temps constant pour déplacer le disque 3

Pour n disques, cela peut s’écrire –

(2^n-1* temps constant pour déplacer le disque 1 + 2^n-2 * temps constant pour déplacer le disque 2 +….

Cette progression géométrique se traduira par O(2^n-1) ou O (2ⁿ), ce qui est exponentiel.

2) Complexité spatiale

La complexité spatiale de la Tour de Hanoï est de 0(n). C'est parce que nous devons stocker la séquence des plaques. Lorsque nous utilisons la récursivité, nous utilisons la pile. Et la taille maximale de la pile peut être « n ». C'est pourquoi la complexité spatiale devient O(n).

Tu pourrais aimer:

Qu'est-ce que la Tour de Hanoï ?

Règles de la Tour de Hanoï

Algorithme pour la Tour de Hanoi

Comment résoudre le puzzle de la Tour de Hanoi

ARTICLES LIÉS

Pseudo-code de la tour de Hanoï

Code de programme dans C++

Code de programme dans Python

Complexité de la Tour de Hanoï