Algoritmul Turnului Hanoi: Python, C++ Code

prin: Sarah Chen Sarah Chen
Hours Actualizat

⚡ Rezumat inteligent

Algoritmul Turnului din Hanoi este un puzzle recursiv clasic care mută o stivă de discuri între trei cuie fără a plasa niciodată un disc mai mare peste unul mai mic, ilustrând clar metoda „împarte și cucerește”.

  • 🗼 Pregătirea puzzle-ului: Trei cuie și n discuri stivuite în dimensiuni descrescătoare pe cuiul sursă, așteptând să fie mutate la cuiul destinație printr-un cui ajutor.
  • 📜 reguli: Doar un disc se mișcă odată, doar discul de sus al oricărui cui se poate mișca, iar un disc mai mare nu se poate sprijini pe un disc mai mic.
  • 🔁 Idee recursivă: Mutați n-1 discuri pe cuiul ajutor, mutați cel mai mare disc pe cuiul destinație, apoi mutați cele n-1 discuri de la ajutor la destinație.
  • ⏱️ Complexitatea timpului: Rezolvarea a n discuri necesită 2^n – 1 mutări, rezultând o complexitate temporală exponențială O(2^n) care crește foarte rapid pe măsură ce n crește.
  • 🧠 Complexitatea spațială: Stiva recursivă suportă până la n cadre simultan, deci complexitatea spațială a soluției recursive este O(n).
  • 🛠️ Aplicații: Predarea recursivității, schemelor de rotație a copiilor de rezervă, mișcării datelor bazate pe stivă, secvențierii robotice și înțelegerea proiectării algoritmului de tip „împarte și cucerește”.
Citește mai mult

Algoritmul Turnului din Hanoi

Ce este Turnul din Hanoi?

Turnul Hanoi este un puzzle matematic format din trei tije și o stivă de discuri de dimensiuni descrescătoare, așezate unul peste altul. Este cunoscut și sub numele de Turnul lui Brahma sau turnul Lucas, deoarece matematicianul francez Edouard Lucas l-a introdus în 1883. Puzzle-ul se bazează pe legende despre mutarea discurilor de aur între trei tije.

Acest puzzle are trei tije și un număr variabil de discuri stivuite. Tijele sunt aranjate ca turnuri ciclice, astfel încât discurile mai mari sunt stivuite în partea de jos, iar discurile mai mici sunt stivuite în partea de sus.

Inițial, ni se dau trei cuie sau tije. Una dintre ele (cuiul A în exemplu) are toate discurile stivuite. Scopul este de a muta întreaga stivă de la o tijă (A) la alta (C), respectând câteva reguli specifice.

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

Problema Turnului din Hanoi

Problema Turnului din Hanoi

Și acesta este scopul final:

Turnul din Hanoi

Regulile Turnului din Hanoi

Iată regulile esențiale pentru Turnul Hanoi:

  • În starea inițială a puzzle-ului, toate discurile sunt stivuite pe tija unu.
  • În starea finală, toate discurile de la tija unu sunt stivuite pe tija doi sau pe tija trei.
  • Doar un disc se poate mișca de la o tijă la alta la un moment dat.
  • Doar discul de sus al unei tije poate fi mișcat.
  • Un disc nu poate fi plasat peste un disc mai mic.

Legenda originală era despre mutarea a 64 de discuri. Preoții puteau muta câte un disc pe rând, conform regulilor. Conform legendei, exista o profeție conform căreia lumea se va sfârși dacă ar putea finaliza actul. În secțiunea despre complexitatea timpului, vom arăta că o decor de tip Turnul Hanoi cu n discuri necesită 2^n – 1 mutări.

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

Algoritm pentru Turnul din Hanoi

Cea mai comună metodă de a rezolva Turnul Hanoi este un algoritm recursiv. Mai întâi, alegem două tije ca sursă și destinație; cuiul de rezervă acționează ca auxiliar sau 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.
  • Mută ​​al n-lea disc de la cuiul sursă la cuiul destinație.
  • Mutați cele n-1 discuri rămase de la cuiul ajutor la cuiul destinație.

Notă: 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. Considerăm cuiul A ca sursă, cuiul B ca ajutor și cuiul C ca destinație.

Pas 1) Inițial, toate discurile sunt stivuite pe cuiul A.

Rezolva puzzle turnul din Hanoi

În această etapă: Sursa = Peg A, Destinația = Peg C, Asistentul = 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 odată, acest pas reduce problema noastră cu 3 discuri la o problemă cu 2 discuri, care este rezolvată printr-un apel recursiv.

Pas 2) Deoarece efectuăm un apel recursiv de la peg-ul A cu peg-ul B ca destinație, folosim peg-ul C ca ajutor.

Observați că ne-am întors la etapa unu pentru aceeași problemă a Turnului Hanoi, dar acum pentru două discuri. Mutăm n-1 (adică un) disc de la sursă la helper, ceea ce mută cel mai mic disc de la cuiul A la cuiul C.

Rezolva puzzle turnul din Hanoi

În această etapă: Sursa = punctul A, Destinația = punctul B, Ajutorul = punctul C.

Pas 3) Conform algoritmului, al n-lea (al doilea) disc este acum transferat la destinație, cuiul B.

Rezolva puzzle turnul din Hanoi

În această etapă: Sursa = punctul A, Destinația = punctul B, Ajutorul = punctul C.

ARTICOLE SIMILARE

Pas 4) Acum, mutăm discul n-1 (discul unu) de la cuiul helper C la cuiul destinație B, urmând a treia etapă a algoritmului.

Rezolva puzzle turnul din Hanoi

În această etapă: Sursa = punctul A, Destinația = punctul B, Ajutorul = punctul C.

Pas 5) După finalizarea apelului recursiv, revenim la setările anterioare din prima etapă a algoritmului.

Pas 6) În a doua etapă, mutăm discul 3 de la cuiul sursă A la cuiul destinație C.

În această etapă: Sursa = punctul A, Destinația = punctul C, Ajutorul = punctul B.

Pas 7) Următoarea sarcină este mutarea discurilor rămase de la suport (peg B) la destinație (peg C). De data aceasta vom folosi sursa originală (peg A) ca suport.

Rezolva puzzle turnul din Hanoi

Pas 8) Deoarece nu putem muta două discuri simultan, facem un apel recursiv pentru discul 1. Conform instrucțiunilor noastre Algoritmul, destinația în acest pas este cuiul A.

Rezolva puzzle turnul din Hanoi

În această etapă: Sursa = punctul B, Destinația = punctul A, Ajutorul = punctul C.

Pas 9) Apelul nostru recursiv este complet. Acum mutăm discul 2 de la sursă la destinație.

Rezolva puzzle turnul din Hanoi

În această etapă: Sursa = punctul B, Destinația = punctul C, Ajutorul = punctul A.

Pas 10) Terminăm prin mutarea discului n-1 rămas (discul 1) de la helper la destinație.

Rezolva puzzle turnul din Hanoi

În această etapă: Sursa = punctul A, Destinația = punctul C, Ajutorul = punctul B.

Pseudo Code pentru Turnul 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;
}

ieșire:

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 temporală și spațială a Turnului Hanoi:

1) Complexitatea timpului:

Privind retrospectiv la algoritm, facem un apel recursiv pentru (n-1) discuri de două ori per apel. Fiecare recursiune (n-1) se descompune în ((n-1)-1) recursii și așa mai departe, până când ajungem la cazul de bază cu un singur disc.

Pentru trei discuri:

  • Discul 3 apelează funcția recursivă pentru discul 2 de două ori.
  • Discul 2 apelează funcția recursivă pentru discul 1 de două ori.
  • Discul 1 se mișcă în timp constant, oferind timpul necesar pentru a rezolva pentru trei discuri.

Exprimată ca recurență:

= 2 × (Timpul necesar pentru rezolvarea a două discuri) + timpul constant necesar pentru mutarea discului 3

= 2 × (2 × timpul necesar pentru rezolvarea unui disc + timpul constant necesar pentru mutarea discului 2) + timpul constant necesar pentru mutarea discului 3

= (2 × 2) × timpul constant pentru mutarea discului 1 + 2 × timpul constant pentru mutarea discului 2 + timpul constant pentru mutarea discului 3

Pentru n discuri, aceasta devine:

2n-1 × timp constant pentru a muta discul 1 + 2n-2 × timpul constant necesar pentru mutarea discului 2 + ….

Această progresie geometrică se însumează cu O(2n – 1), ceea ce simplifică la O(2n), o complexitate temporală exponențială.

2) Complexitatea spațiului:

Complexitatea spațială a Turnului Hanoi este O(n). Recursivitatea folosește stiva de apeluri, iar adâncimea maximă a stivei este egală cu n, numărul de discuri. De aceea, complexitatea spațială este O(n).

Întrebări frecvente

Algoritmul Turnului din Hanoi este o procedură recursivă care mută n discuri de la un peg sursă la un peg destinație folosind un peg helper, fără a plasa niciodată un disc mai mare peste unul mai mic.

Numărul minim de mutări pentru n discuri este 2^n – 1. Trei discuri au nevoie de 7 mutări, patru discuri au nevoie de 15, iar zece discuri au nevoie de 1,023 de mutări.

Complexitatea temporală este O(2^n) deoarece fiecare disc suplimentar dublează lucrul mecanic. Recurența T(n) = 2T(n-1) + 1 dă 2^n – 1, care este exponențială.

Complexitatea spațiului este O(n) deoarece stiva de apeluri recursive conține un cadru pentru fiecare disc procesat. Adâncimea maximă de recursiune atinge n, deci memoria auxiliară necesară este liniară în funcție de numărul de discuri.

Da. O soluție iterativă folosește o buclă cu un model fix: la mutările impare, cel mai mic disc se schimbă ciclic între cuie, iar la mutările pare se face singura mutare legală care nu este cea mai mică.

Algoritmul predă recursivitatea, modelează scheme de rotație de rezervă pentru stocare, ghidează secvențierea brațului robotic și apare în testele de neuropsihologie care măsoară capacitatea de planificare.

Agenții de învățare prin consolidare rezolvă problema Turnului Hanoi tratând fiecare configurație a discului ca o stare și fiecare mișcare ca o acțiune. Este un punct de referință comun pentru planificare și învățarea politicilor ierarhice.

Da. GitHub Copilot, ChatGPT și Gemini genera soluții recursive ale Turnului Hanoi în Python, C++ și JavaDezvoltatorii ar trebui să verifice în continuare cazurile de bază și ordinea argumentelor.

Rezumați această postare cu: