Tower of Hanoi Algoritme: Python, C++ Kode
Sarah Chen
Hvad er Tower of Hanoi?
The Tower of Hanoi er et matematisk puslespil, der består af tre stænger og adskillige skiver placeret over hinanden. Det er også kendt som Brahma-tårnet eller Lucas-tårnet, som den franske matematiker Edouard Lucas introducerede det tilbage i 1883. Dette puslespil er baseret på legender om at flytte guldskiver mellem tre stænger.
Dette puslespil har tre stænger og et variabelt antal stablede skiver. Disse stænger er designet som cykliske tårne. Så de større skiver i diameter stables på bunden, og de mindre skiver stables ovenpå.
I første omgang får vi tre pinde eller stænger. Og en af dem (A, vist i eksemplet) har alle diskene stablet. Vi sigter efter at flytte en hel stak disks fra en stang (A) til en anden (C) ved at overholde nogle specifikke regler.
Her er den indledende opsætning af puslespillet-
Og dette er det endelige mål-
Regler for Tower of Hanoi
Her er nogle væsentlige regler for Tower of Hanoi:
- Den indledende tilstand af dette puslespil, alle skiverne vil blive stablet i stang en.
- Den endelige tilstand er, at alle de diske fra stang en vil blive stablet på stang to eller stang tre.
- Vi kan flytte en on-disk fra en stang til en anden til enhver tid.
- Vi kan kun flytte den øverste skive fra stangen.
- En disk kan ikke placeres over en anden disk, som er mindre.
Den oprindelige legende handlede om at flytte 64 diske. Præsterne kunne flytte en disk ad gangen efter reglerne. Ifølge legenden var der en profeti om, at verden ville ende, hvis de kunne fuldføre handlingen. I afsnittet om tidskompleksitet vil vi vise, at en Tower of Hanoi-indstilling på n diske ville koste 2^n – 1 træk.
Så hvis præsterne kunne bruge 1 sekund til at flytte skiverne, ville den samlede tid, de ville bruge for at løse gåden, være 2^64 – 1 sekund eller 584,942,417,356 år, 26 dage, 7 timer og 15 sekunder.
Algoritme for Tower of Hanoi
En generel måde at løse Hanois tårn på er en rekursiv algoritme. Først skal vi beslutte os for to stænger eller pinde som kilde og destination, og reservepinden ville være en hjælpe eller hjælper.
Her er trinene til at løse Tower of Hanoi-puslespillet:
- Flyt de øverste n-1 diske fra kildepinden til hjælpepinden.
- Flyt derefter den n'te disk fra source-peg til destinations-peg.
- Til sidst flytter du de resterende n-1 diske fra hjælpepinden 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 og betragte peg A som kilden, peg B som hjælperen og peg C som destinationen
Trin 1) Til at begynde med vil alle diskene blive stablet på pind A.
På dette tidspunkt:
Kilde = Peg A
Destination = Peg C
Hjælper = Peg 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, bryder det vores problem fra et 3-disk problem til et 2-disk problem, som er et rekursivt kald.
Trin 2) Da vi kalder et rekursivt kald fra peg A og destinationen er peg B, vil vi bruge peg C som en hjælper.
Bemærk, at vi er på fase et igen for det samme tårn i Hanoi-problemet for to diske.
Nu skal vi flytte n-1 eller en disk fra kilde til hjælper, flytte den mindste disk fra pind A til pind C.
På dette tidspunkt:
Kilde = pind A
Destination = pind B
Hjælper = pind C
Trin 3) Derefter, ifølge vores algoritme, skal det n. eller 2. diskbehov overføres til destinationen eller peg B.
På dette tidspunkt:
Kilde = pind A
Destination = pind B
Hjælper = pind C
Trin 4) Nu vil vi flytte n-1 diske eller disk en fra hjælper eller pind C til destinationen eller pind B i henhold til tredje fase af vores algoritme.
På dette tidspunkt:
Kilde = pind A
Destination = pind B
Hjælper = pind C
Trin 5) Efter at have afsluttet det rekursive opkald, vil vi vende tilbage til vores tidligere indstilling, når den første fase af algoritmen.
Trin 6) Nu, i anden fase, vil vi flytte vores kilde til vores destination, som flytter disk 3 til pind C fra pind A.
På dette tidspunkt:
Kilde = pind A
Destination = pind C
Hjælper = pind B
Trin 7) Nu kan vi se det
d er at flytte de resterende diske fra hjælper (peg B) til destination (peg C). Vi vil bruge den indledende kilde eller pind A som en hjælper i dette tilfælde.
Trin 8) Da vi ikke kan flytte to diske samtidigt, vil vi kalde et rekursivt kald for disk 1. Ifølge det sidste trin og vores algoritme, en destination i dette trin er peg A.
På dette tidspunkt:
Kilde = pind B
Destination = pind A
Hjælper = pind C
Trin 9) Vores rekursive opkald er afsluttet nu. Så flytter vi disk 2 fra sin kilde til sin destination.
På dette tidspunkt:
Kilde = pind B
Destination = pind C
Hjælper = pind A
Trin 10) Så flytter vi vores resterende n-1 eller disk 1 fra hjælper til destination.
På dette tidspunkt:
Kilde = pind A
Destination = pind C
Hjælper = pind B
Pseudokode for Tower of 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
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;
}
Produktion
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 tid og rum kompleksiteten af Tower of Hanoi:
1) Tidskompleksitet:
Hvis vi ser tilbage på vores algoritme, kan vi se, at vi introducerer et rekursivt kald for (n-1) diske to gange. Disse rekursive kald for (n-1) diske kan opdeles i andre ((n-1)-1) og så videre, indtil vi kun får én disk at flytte.
Til tre diske-
- Disk 3 kalder en rekursiv funktion for disk to to gange.
- Disk 2 kalder en rekursiv funktion for disk en to gange.
- Disk 1 kan bevæge sig inden for konstant tid, og tid til at løse for tre diske.
= 2*(Tid til at løse for to diske) + konstant Tid til at flytte disk 3
= 2*(2*tid til at løse for en 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 kan det skrives som –
(2n-1 * konstant tid til at flytte disk 1 + 2n-2 * konstant tid til at flytte disk 2 + ….
Denne geometriske progression vil resultere i O(2n-1), Eller O (2n), som er eksponentiel.
2) Rumkompleksitet
Rumkompleksiteten af Tower of Hanoi er 0(n). Det er fordi vi skal gemme rækkefølgen af pladerne. Når vi bruger rekursion, bruger den stakken. Og den maksimale størrelse på stakken kan være "n." Det er derfor rumkompleksiteten bliver O(n).
