Tower of Hanoi Algoritme: Python, C++ Code

by: Sarah Chen Sarah Chen
Hours oppdatert

⚡ Smart oppsummering

Tower of Hanoi-algoritmen er et klassisk rekursivt puslespill som flytter en stabel med disker mellom tre pinner uten å plassere en større disk oppå en mindre, noe som illustrerer del-og-hersk tydelig.

  • 🗼 Oppsett av puslespill: Tre pinner og n disker stablet i avtagende størrelse på kildepinnen, og venter på å bli flyttet til målpinnen gjennom en hjelpepinne.
  • 📜 regler: Bare én disk beveger seg om gangen, bare den øverste disken på en hvilken som helst pinne kan bevege seg, og en større disk kan ikke hvile på en mindre disk.
  • 🔁 Rekursiv idé: Flytt n-1 disker til hjelperpinnen, flytt den største disken til destinasjonspinnen, og flytt deretter de n-1 diskene fra hjelperen til destinasjonen.
  • ️ Tidskompleksitet: Å løse n disker krever 2^n – 1 trekk, noe som gir en eksponentiell O(2^n) tidskompleksitet som vokser veldig raskt når n øker.
  • 🧠 Romkompleksitet: Rekursjonsstakken har plass til opptil n rammer samtidig, så romkompleksiteten til den rekursive løsningen er O(n).
  • 🛠️ Bruksområder: Undervisning i rekursjon, rotasjonsordninger for sikkerhetskopier, stakkbasert dataflyt, robotsekvensering og forståelse av del-og-hersk-algoritmedesign.
Les mer

Hanoi-tårnets algoritme

Hva er Tower of Hanoi?

Hanoi-tårnet er et matematisk puslespill som består av tre stenger og en stabel med skiver av avtagende størrelse plassert oppå hverandre. Det er også kjent som Brahma-tårnet eller Lucas-tårnet, siden den franske matematikeren Edouard Lucas introduserte det i 1883. Puslespillet er basert på legender om å flytte gullskiver mellom tre stenger.

Dette puslespillet har tre stenger og et variabelt antall stablede skiver. Stengene er ordnet som sykliske tårn, slik at de større skivene er stablet nederst og de mindre skivene er stablet oppå.

I utgangspunktet får vi tre pinner eller stenger. En av dem (pinne A i eksemplet) har alle skivene stablet. Målet er å flytte hele stabelen fra én stang (A) til en annen (C) samtidig som man overholder noen få spesifikke regler.

Her er den første oppsetningen av puslespillet:

Problemet med Tower of Hanoi

Problemet med Tower of Hanoi

Og dette er det endelige målet:

Tower of Hanoi

Reglene for Tower of Hanoi

Her er de viktigste reglene for Hanoi-tårnet:

  • I puslespillets starttilstand er alle diskene stablet på stang én.
  • I den endelige tilstanden er alle skivene fra stang én stablet oppå stang to eller stang tre.
  • Bare én disk kan bevege seg fra en stang til en annen om gangen.
  • Bare den øverste skiven på en stang kan beveges.
  • En disk kan ikke plasseres oppå en mindre disk.

Den opprinnelige legenden handlet om å flytte 64 disker. Prestene kunne flytte én disk om gangen i henhold til reglene. I følge legenden var det en profeti om at verden ville gå under hvis de kunne fullføre handlingen. I delen om tidskompleksitet skal vi vise at en Tower of Hanoi-setting med n disker krever 2^n – 1 trekk.

Så, hvis prestene trengte 1 sekund for å flytte én disk, ville den totale tiden for å løse gåten være 2^64 – 1 sekund, eller omtrent 584 942 417 356 år, 26 dager, 7 timer og 15 sekunder.

Algoritme for Tower of Hanoi

Den vanligste måten å løse Hanoi-tårnet på er en rekursiv algoritme. Først velger vi to stenger som kilde og destinasjon; reservepinnen fungerer som hjelpepinnen eller hjelperen.

Her er trinnene for å løse Tower of Hanoi-puslespillet:

  • Flytt de øverste n-1 diskene fra kildepinnen til hjelpepinnen.
  • Flytt den n-te disken fra kildepinnen til målpinnen.
  • Flytt de gjenværende n-1 diskene fra hjelpepinnen til destinasjonspinnen.

OBS: Hvis vi har én enkelt disk, kan vi flytte den direkte fra kilde til destinasjon.

Hvordan løse Tower of Hanoi Puzzle

La oss illustrere algoritmen for tre disker. Tenk på pinne A som kilde, pinne B som hjelper og pinne C som destinasjon.

Trinn 1) I utgangspunktet er alle diskene stablet på pinne A.

Løs Tower of Hanoi Puzzle

På dette stadiet: Kilde = Peg A, Destinasjon = Peg C, Hjelpeenhet = Peg B.

Nå må vi flytte de øverste n-1-diskene fra kilden til hjelperen.

OBS: Selv om vi bare kan flytte én disk om gangen, reduserer dette trinnet vårt 3-diskproblem til et 2-diskproblem, som håndteres av et rekursivt kall.

Trinn 2) Når vi foretar et rekursivt kall fra pinne A med pinne B som destinasjon, bruker vi pinne C som hjelper.

Legg merke til at vi er tilbake på trinn én for det samme Tower of Hanoi-problemet, men nå for to disker. Vi flytter n-1 (det vil si én) disk fra kilde til hjelper, som flytter den minste disken fra pinne A til pinne C.

Løs Tower of Hanoi Puzzle

På dette stadiet: Kilde = pinne A, Destinasjon = pinne B, Hjelpeenhet = pinne C.

Trinn 3) I følge algoritmen overføres nå den n-te (2.) disken til destinasjonen, pinne B.

Løs Tower of Hanoi Puzzle

På dette stadiet: Kilde = pinne A, Destinasjon = pinne B, Hjelpeenhet = pinne C.

RELATERTE ARTIKLER

Trinn 4) Nå flytter vi n-1-disken (disk én) fra hjelperpinne C til destinasjonspinne B, ved å følge algoritmens tredje trinn.

Løs Tower of Hanoi Puzzle

På dette stadiet: Kilde = pinne A, Destinasjon = pinne B, Hjelpeenhet = pinne C.

Trinn 5) Etter at det rekursive kallet er fullført, går vi tilbake til vår forrige innstilling i algoritmens første trinn.

Trinn 6) I det andre trinnet flytter vi disk 3 fra kildepinne A til destinasjonspinne C.

På dette stadiet: Kilde = pinne A, Destinasjon = pinne C, Hjelpeenhet = pinne B.

Trinn 7) Den neste oppgaven er å flytte de gjenværende diskene fra hjelperen (pinne B) til destinasjonen (pinne C). Vi bruker den opprinnelige kilden (pinne A) som hjelper denne gangen.

Løs Tower of Hanoi Puzzle

Trinn 8) Siden vi ikke kan flytte to disker samtidig, foretar vi et rekursivt kall for disk 1. I følge vår algoritme, destinasjonen i dette trinnet er pinne A.

Løs Tower of Hanoi Puzzle

På dette stadiet: Kilde = pinne B, Destinasjon = pinne A, Hjelpeenhet = pinne C.

Trinn 9) Vårt rekursive kall er fullført. Vi flytter nå disk 2 fra kilden til destinasjonen.

Løs Tower of Hanoi Puzzle

På dette stadiet: Kilde = pinne B, Destinasjon = pinne C, Hjelpeenhet = pinne A.

Trinn 10) Vi avslutter med å flytte den gjenværende n-1 disken (disk 1) fra hjelperen til destinasjonen.

Løs Tower of Hanoi Puzzle

På dette stadiet: Kilde = pinne A, Destinasjon = pinne C, Hjelpeenhet = pinne B.

Kallenavn Code for 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;
}

Utgang:

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

Utgang:

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 til Tower of Hanoi

Her er tids- og romkompleksiteten til Tower of Hanoi:

1) Tidskompleksitet:

Når vi ser tilbake på algoritmen, foretar vi et rekursivt kall for (n-1) disker to ganger per kall. Hver (n-1) rekursjon deles opp i ((n-1)-1) rekursjoner, og så videre, helt til vi når basistilfellet med én disk.

For tre disker:

  • Disk 3 kaller den rekursive funksjonen for disk 2 to ganger.
  • Disk 2 kaller den rekursive funksjonen for disk 1 to ganger.
  • Disk 1 beveger seg i konstant tid, noe som gir tid til å løse for tre disker.

Uttrykt som en gjentakelse:

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

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

= (2 × 2) × konstant tid for å flytte disk 1 + 2 × konstant tid for å flytte disk 2 + konstant tid for å flytte disk 3

For n disker blir dette:

2n-1 × konstant tid for å bevege disk 1 + 2n-2 × konstant tid for å flytte disk 2 + ….

Denne geometriske progresjonen summerer seg til O(2n – 1), noe som forenkler til O(2n), en eksponentiell tidskompleksitet.

2) Romkompleksitet:

Romkompleksiteten til Tower of Hanoi er O(n). Rekursjonen bruker kallstakken, og den maksimale dybden på stakken er lik n, antallet disker. Det er derfor romkompleksiteten er O(n).

Spørsmål og svar

Tower of Hanoi-algoritmen er en rekursiv prosedyre som flytter n disker fra en kildepinne til en destinasjonspinne ved hjelp av én hjelpepinne, uten å plassere en større disk oppå en mindre.

Minimum antall trekk for n disker er 2^n – 1. Tre disker trenger 7 trekk, fire disker trenger 15, og ti disker trenger 1,023 trekk.

Tidskompleksiteten er O(2^n) fordi hver ekstra disk dobler arbeidet. Rekurrensen T(n) = 2T(n-1) + 1 løses til 2^n – 1, som er eksponensiell.

Romkompleksiteten er O(n) fordi rekursjonskallstakken inneholder én ramme for hver disk som behandles. Den maksimale rekursjonsdybden når n, så det nødvendige hjelpeminnet er lineært i antall disker.

Ja. En iterativ løsning bruker en løkke med et fast mønster: på oddetrekk byttes den minste disken syklisk mellom pinnene, og på partallstrekk utfør det eneste lovlige ikke-minste trekket.

Algoritmen lærer bort rekursjon, modellerer backup-rotasjonsordninger for lagring, veileder sekvensering av robotarmer og vises i nevropsykologiske tester som måler planleggingsevne.

Forsterkningslæringsagenter løser Tower of Hanoi ved å behandle hver diskkonfigurasjon som en tilstand og hver bevegelse som en handling. Det er en vanlig referanse for planlegging og hierarkisk policylæring.

Ja. GitHub Copilot, ChatGPT og Gemini generere rekursive løsninger for Tower of Hanoi i Python, C++og JavaUtviklere bør fortsatt bekrefte basistilfeller og argumentrekkefølgen.

Oppsummer dette innlegget med: