Tower of Hanoi Algoritme: Python, C++ Code

⚡ Smart opsummering

Tower of Hanoi-algoritmen er et klassisk rekursivt puslespil, der flytter en stak diske mellem tre pinde, uden at placere en større disk oven på en mindre, hvilket tydeligt illustrerer del-og-hersk-princippet.

🗼 Opsætning af puslespil: Tre pinde og n diske stablet i aftagende størrelse på kildepinnen og venter på at blive flyttet til destinationspinnen via en hjælpepind.
📜 Regler: Kun én disk bevæger sig ad gangen, kun den øverste disk på en hvilken som helst pind kan bevæge sig, og en større disk kan ikke hvile på en mindre disk.
🔁 Rekursiv idé: Flyt n-1 diske til hjælperpinnen, flyt den største disk til destinationspinnen, og flyt derefter de n-1 diske fra hjælper til destination.
⏱️ Tidskompleksitet: At løse n diske kræver 2^n – 1 træk, hvilket giver en eksponentiel O(2^n) tidskompleksitet, der vokser meget hurtigt, når n stiger.
🧠 Rumkompleksitet: Rekursionsstakken kan rumme op til n frames ad gangen, så rumkompleksiteten af den rekursive løsning er O(n).
🛠️ Applikationer: Undervisning i rekursion, backuprotationsordninger, stakbaseret dataflytning, robotsekventering og forståelse af del-og-hersk algoritmedesign.

Læs mere

Hvad er Tower of Hanoi?

Hanoi-tårnet er et matematisk puslespil, der består af tre stave og en stak skiver af aftagende størrelse placeret oven på hinanden. Det er også kendt som Brahma-tårnet eller Lucas-tårnet, da den franske matematiker Edouard Lucas introducerede det i 1883. Puslespillet er baseret på legender om at flytte guldskiver mellem tre stave.

Dette puslespil har tre stænger og et variabelt antal stablede skiver. Stængerne er arrangeret som cykliske tårne, så de større skiver er stablet i bunden og de mindre skiver er stablet ovenpå.

I starten får vi tre pinde eller stænger. En af dem (pind A i eksemplet) har alle skiverne stablet. Målet er at flytte hele stakken fra en stang (A) til en anden (C), mens man overholder et par specifikke regler.

Her er den indledende opsætning af puslespillet:

Problemet med Tower of Hanoi

Og dette er det endelige mål:

Regler for Tower of Hanoi

Her er de vigtigste regler for Hanoi-tårnet:

I puslespillets oprindelige tilstand er alle diske stablet på stang et.
I den endelige tilstand er alle skiver fra stang et stablet oven på stang to eller stang tre.
Kun én disk kan bevæge sig fra en stang til en anden ad gangen.
Kun den øverste skive på en stang kan bevæges.
En disk kan ikke placeres oven på en mindre disk.

Den oprindelige legende handlede om at flytte 64 diske. Præsterne kunne flytte én disk ad gangen i henhold til reglerne. Ifølge legenden var der en profeti om, at verden ville gå under, hvis de kunne fuldføre handlingen. I afsnittet om tidskompleksitet vil vi vise, at en Hanoi-tårnopsætning med n diske kræver 2^n – 1 træk.

Så hvis præsterne havde brug for 1 sekund til at flytte én disk, ville den samlede tid til at løse gåden være 2^64 – 1 sekund, eller omtrent 584,942,417,356 år, 26 dage, 7 timer og 15 sekunder.

Algoritme for Tower of Hanoi

Den mest almindelige måde at løse Hanoi-tårnet på er en rekursiv algoritme. Først vælger vi to stænger som kilde og destination; reservepinden fungerer som hjælpe- eller hjælpeelement.

Her er trinene til at løse Tower of Hanoi-puslespillet:

Flyt de øverste n-1 diske fra kildepinden til hjælpepinden.
Flyt den n'te disk fra kildepinnen til destinationspinnen.
Flyt de resterende n-1 diske fra hjælpepinnen til destinationspinnen.

Bemærk: Hvis vi har en enkelt disk, kan vi flytte den direkte fra kilde til destination.

Sådan løses Tower of Hanoi-puslespil

Lad os illustrere algoritmen for tre diske. Betragt pind A som kilde, pind B som hjælper og pind C som destination.

Trin 1) I starten er alle diskene stablet på pind A.

På dette stadie: Kilde = Pind A, Destination = Pind C, Hjælper = Pind B.

Nu skal vi flytte de øverste n-1 diske fra kilden til hjælperen.

Bemærk: Selvom vi kun kan flytte én disk ad gangen, reducerer dette trin vores 3-diskeproblem til et 2-diskeproblem, som håndteres af et rekursivt kald.

Trin 2) Når vi foretager et rekursivt kald fra pind A med pind B som destination, bruger vi pind C som hjælper.

Bemærk at vi er tilbage ved trin et for det samme Tower of Hanoi-problem, men nu for to diske. Vi flytter n-1 (dvs. én) disk fra kilde til hjælper, hvilket flytter den mindste disk fra pind A til pind C.

På dette stadie: Kilde = pind A, Destination = pind B, Hjælper = pind C.

Trin 3) Ifølge algoritmen overføres den n'te (2.) disk nu til destinationen, pind B.

På dette stadie: Kilde = pind A, Destination = pind B, Hjælper = pind C.

Trin 4) Nu flytter vi den n-1 disk (disk et) fra hjælperpind C til destinationspind B, i henhold til algoritmens tredje trin.

På dette stadie: Kilde = pind A, Destination = pind B, Hjælper = pind C.

Trin 5) Efter at have gennemført det rekursive kald, vender vi tilbage til vores tidligere indstilling i algoritmens første trin.

Trin 6) I andet trin flytter vi disk 3 fra kildepind A til destinationspind C.

På dette stadie: Kilde = pind A, Destination = pind C, Hjælper = pind B.

Trin 7) Den næste opgave er at flytte de resterende diske fra hjælperen (pig B) til destinationen (pig C). Vi bruger den oprindelige kilde (pig A) som hjælper denne gang.

Trin 8) Da vi ikke kan flytte to diske på én gang, foretager vi et rekursivt kald for disk 1. Ifølge vores algoritme, destinationen i dette trin er pind A.

På dette stadie: Kilde = pind B, Destination = pind A, Hjælper = pind C.

Trin 9) Vores rekursive kald er fuldført. Vi flytter nu disk 2 fra dens kilde til dens destination.

På dette stadie: Kilde = pind B, Destination = pind C, Hjælper = pind A.

Trin 10) Vi afslutter med at flytte den resterende n-1 disk (disk 1) fra hjælper til destination.

På dette stadie: Kilde = pind A, Destination = pind C, Hjælper = pind B.

Kaldenavn Code til Hanoi-tårnet

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

Programkode i 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;
}

Output:

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

Programkode i 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')

Output:

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

Kompleksiteten af Tower of Hanoi

Her er tids- og rumkompleksiteten af Hanoi-tårnet:

1) Tidskompleksitet:

Når vi ser tilbage på algoritmen, foretager vi et rekursivt kald for (n-1) diske to gange pr. kald. Hver (n-1) rekursion opdeles i ((n-1)-1) rekursioner, og så videre, indtil vi når basistilfældet med en enkelt disk.

For tre diske:

Disk 3 kalder den rekursive funktion for disk 2 to gange.
Disk 2 kalder den rekursive funktion for disk 1 to gange.
Disk 1 bevæger sig i konstant tid, hvilket giver tid til at løse tre diske.

Udtrykt som en gentagelse:

= 2 × (Tid til at løse for to diske) + konstant tid til at flytte disk 3

= 2 × (2 × tid til at løse for én disk + konstant tid til at flytte disk 2) + konstant tid til at flytte disk 3

= (2 × 2) × konstant tid til at flytte disk 1 + 2 × konstant tid til at flytte disk 2 + konstant tid til at flytte disk 3

For n diske bliver dette:

2^n-1 × konstant tid til at bevæge disk 1 + 2^n-2 × konstant tid til at bevæge disk 2 + ….

Denne geometriske progression summerer sig til O(2ⁿ – 1), hvilket forenkler til O (2ⁿ), en eksponentiel tidskompleksitet.

2) Rumkompleksitet:

Rumkompleksiteten for Tower of Hanoi er O(n). Rekursionen bruger kaldstakken, og stakkens maksimale dybde er lig med n, antallet af diske. Derfor er rumkompleksiteten O(n).

Ofte Stillede Spørgsmål

Tower of Hanoi-algoritmen er en rekursiv procedure, der flytter n diske fra en kildepind til en destinationspind ved hjælp af én hjælpepind, mens den aldrig placerer en større disk oven på en mindre.

Minimumsantallet af træk for n diske er 2^n – 1. Tre diske kræver 7 træk, fire diske kræver 15, og ti diske kræver 1,023 træk.

Tidskompleksiteten er O(2^n), fordi hver ekstra disk fordobler arbejdet. Rekursionen T(n) = 2T(n-1) + 1 løses til 2^n – 1, hvilket er eksponentielt.

Rumkompleksiteten er O(n), fordi rekursionskaldstakken indeholder én frame for hver disk, der behandles. Den maksimale rekursionsdybde når n, så den nødvendige ekstra hukommelse er lineær i antallet af diske.

Ja. En iterativ løsning bruger en løkke med et fast mønster: ved ulige træk byttes den mindste disk cyklisk mellem pindene, og ved lige træk foretages det eneste lovlige ikke-mindste træk.

Algoritmen lærer rekursion, modellerer backup-rotationsordninger til lagring, guider robotarmssekventering og optræder i neuropsykologiske tests, der måler planlægningsevne.

Forstærkningslæringsagenter løser Tower of Hanoi ved at behandle hver diskkonfiguration som en tilstand og hver bevægelse som en handling. Det er et fælles benchmark for planlægning og hierarkisk politisk læring.

Ja. GitHub Copilot, ChatGPT og Gemini generere rekursive Tower of Hanoi-løsninger i Python, C++og JavaUdviklere bør stadig verificere basistilfælde og argumentrækkefølgen.

Tower of Hanoi Algoritme: Python, C++ Code

Hvad er Tower of Hanoi?

Regler for Tower of Hanoi

Algoritme for Tower of Hanoi

Sådan løses Tower of Hanoi-puslespil

Kaldenavn Code til Hanoi-tårnet

Programkode i C++

Programkode i Python

Kompleksiteten af Tower of Hanoi

Ofte Stillede Spørgsmål

Opsummer dette indlæg med:

Tilmeld dig nyhedsbrevet

Hvad er Tower of Hanoi?

Regler for Tower of Hanoi

Algoritme for Tower of Hanoi

Sådan løses Tower of Hanoi-puslespil

RELATEREDE ARTIKLER

Kaldenavn Code til Hanoi-tårnet

Programkode i C++

Programkode i Python

Kompleksiteten af ​​Tower of Hanoi

Ofte Stillede Spørgsmål

Opsummer dette indlæg med:

Tilmeld dig nyhedsbrevet

Kompleksiteten af Tower of Hanoi