Algoritmul Turnului Hanoi: Python, C++ Cod

Ce este Turnul din Hanoi?

Turnul din Hanoi este un puzzle matematic format din trei tije și numeroase discuri așezate una peste alta. Este cunoscut și sub numele de Turnul lui Brahma sau turnul Lucas, așa cum l-a introdus matematicianul francez Edouard Lucas în 1883. Acest puzzle se bazează pe legende despre mișcarea discurilor de aur între trei tije.

Acest puzzle are trei tije și un număr variabil de discuri stivuite. Aceste tije sunt proiectate ca turnuri ciclice. Deci, discurile mai mari în diametru sunt stivuite în partea de jos, iar discurile mai mici sunt stivuite deasupra.

Inițial, ni se dau trei cuie sau tije. Și unul dintre ele (A, prezentat în exemplu) are toate discurile stivuite. Ne propunem să mutăm un întreg teanc de discuri de la o tijă (A) la alta (C) respectând niște reguli specifice.

Iată configurația inițială a puzzle-ului -

Și acesta este scopul final -

Regulile Turnului din Hanoi

Iată câteva reguli esențiale pentru Turnul din Hanoi:

• Starea inițială a acestui puzzle, toate discurile vor fi stivuite într-o tijă.
• Starea finală este că toate acele discuri de la tija unu vor fi stivuite pe tija două sau tija trei.
• Putem muta un disc de pe o tijă la alta în orice moment.
• Putem muta doar discul de sus de pe tijă.
• Un disc nu poate fi plasat peste un alt disc, care este mai mic.

Legenda originală era despre mutarea a 64 de discuri. Preoții puteau muta câte un disc, conform regulilor. Potrivit legendei, a existat o profeție conform căreia lumea se va sfârși dacă ar putea duce la bun sfârșit actul. În secțiunea de complexitate a timpului, vom arăta că o setare a Turnului din Hanoi de n discuri ar costa 2^n – 1 mișcare.

Deci, dacă preoții ar putea avea nevoie de 1 secundă pentru a muta discurile, timpul total de care ar avea nevoie pentru a rezolva puzzle-ul ar fi de 2^64 – 1 secundă sau 584,942,417,356 de ani, 26 de zile, 7 ore și 15 secunde.

Algoritm pentru Turnul din Hanoi

O modalitate generală de a rezolva Turnul din Hanoi este un algoritm recursiv. În primul rând, trebuie să decidem asupra a două tije sau cuie ca sursă și destinație, iar cuiul de rezervă ar fi un auxiliar sau un ajutor.

Iată pașii pentru a rezolva puzzle-ul Turnul din Hanoi:

• Mutați discurile superioare n-1 de la suportul sursă la suportul de ajutor.
• După aceea, mutați al n-lea disc de la peg-ul sursă la cel de destinație.
• În cele din urmă, mutați restul n-1 discuri de pe piciorul de ajutor pe piciorul de destinație.

notițe: Dacă avem un singur disc, îl putem muta direct de la sursă la destinație.

Cum să rezolvi puzzle-ul Turnul din Hanoi

Să ilustrăm algoritmul pentru trei discuri și să considerăm peg A ca sursă, peg B ca ajutor și peg C ca destinație

Pas 1) Inițial, toate discurile vor fi stivuite pe suportul A.

În această etapă:

Sursa = Peg A
Destinație = Peg C
Ajutor = Peg B

Acum, trebuie să mutăm discurile de sus n-1 de la sursă la helper.

Notă: Deși putem muta doar un disc la un moment dat, problema noastră trece de la o problemă de 3 discuri la o problemă de 2 discuri, care este un apel recursiv.

Pas 2) Pe măsură ce numim un apel recursiv de la peg A și destinația este peg B, vom folosi peg C ca ajutor.

Observați că suntem din nou la prima etapă pentru aceeași problemă a turnului din Hanoi pentru două discuri.

Acum trebuie să mutăm n-1 sau un disc de la sursă la helper, mutând cel mai mic disc de la peg A la peg C.

În această etapă:

Sursa = peg A
Destinație = peg B
Ajutor = pion C

Pas 3) Apoi, conform algoritmului nostru, al n-lea sau al doilea disc trebuie transferat în destinația sau peg-ul B.

În această etapă:

Sursa = peg A
Destinație = peg B
Ajutor = pion C

Pas 4) Acum, vom muta discurile n-1 sau discul unul de la helper sau peg C la destinație sau peg B conform celei de-a treia etape a algoritmului nostru.

În această etapă:

Sursa = peg A
Destinație = peg B
Ajutor = pion C

Pas 5) După finalizarea apelului recursiv, vom reveni la setarea anterioară la prima etapă a algoritmului.

Pas 6) Acum, în a doua etapă, ne vom muta sursa la destinația noastră, care este mutarea discului 3 la pionul C de la pilonul A.

În această etapă:

Sursa = peg A
Destinație = peg C
Ajutor = chela B

Pas 7) Acum putem vedea asta

d este de a muta discurile rămase de la helper (peg B) la destinație (peg C). Vom folosi sursa inițială sau peg A ca ajutor în acest caz.

Pas 8) Deoarece nu putem muta două discuri simultan, vom apela un apel recursiv pentru discul 1. Conform ultimului pas și a noastră Algoritmul, o destinație în acest pas este chela A.

În această etapă:

Sursa = peg B
Destinație = peg A
Ajutor = pion C

Pas 9) Apelul nostru recursiv este finalizat acum. Apoi mutăm discul 2 de la sursă la destinație.

În această etapă:

Sursa = peg B
Destinație = peg C
Ajutor = chel A

Pas 10) Apoi mutăm n-1 sau discul 1 rămas de la helper la destinație.

În această etapă:

Sursa = peg A
Destinație = peg C
Ajutor = chela B

Pseudocod pentru Turnul din Hanoi

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

Codul programului în 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;
}

producție

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

Codul programului în 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')

ieșire:

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

Complexitatea Turnului din Hanoi

Iată complexitatea în timp și spațiu a Turnului din Hanoi:

1) Complexitatea timpului:

Dacă ne uităm înapoi la algoritmul nostru, putem vedea că introducem un apel recursiv pentru (n-1) discuri de două ori. Acele apeluri recursive pentru (n-1) discuri pot fi împărțite în alte ((n-1)-1) și așa mai departe până când obținem un singur disc de mutat.

Pentru trei discuri-

• Discul 3 apelează de două ori o funcție recursivă pentru discul doi.
• Discul 2 apelează de două ori o funcție recursivă pentru disc.
• Discul 1 se poate mișca într-un timp constant și timp de rezolvat pentru trei discuri.

= 2*(Timp de rezolvare pentru două discuri) + constant Timp de mutare a discului 3

= 2*(2*timp de rezolvare pentru un disc + constantă de timp pentru a muta discul 2) + constantă de timp pentru a muta discul 3

= (2*2) (timp constant pentru mutarea discului 1) + 2*timp constant pentru mutarea discului 2 + timp constant pentru mutarea discului 3

Pentru n discuri, poate fi scris ca –

(2^n-1 * timp constant pentru a muta discul 1 + 2^n-2 * timp constant pentru a muta discul 2 + ....

Această progresie geometrică va avea ca rezultat O(2^n-1) Sau O(2ⁿ), care este exponenţial.

2) Complexitatea spațiului

Complexitatea spațială a Turnului din Hanoi este 0(n). Asta pentru că trebuie să stocăm secvența plăcilor. Când folosim recursiunea, aceasta folosește stiva. Și dimensiunea maximă a stivei poate fi „n”. De aceea complexitatea spațiului devine O(n).