Tower of Hanoi Algoritme: Python, C++ Kode
Sarah Chen
Hva er Tower of Hanoi?
Tower of Hanoi er et matematisk puslespill som består av tre stenger og tallrike disker plassert over hverandre. Det er også kjent som Tower of Brahma eller Lucas-tårnet, slik den franske matematikeren Edouard Lucas introduserte det tilbake i 1883. Dette puslespillet er basert på legender om å flytte gullskiver mellom tre stenger.
Dette puslespillet har tre stenger og et variabelt antall stablede disker. Disse stengene er designet som sykliske tårn. Så de større skivene i diameter er stablet på bunnen, og de mindre skivene er stablet på toppen.
Til å begynne med får vi tre knagger eller stenger. Og en av dem (A, vist i eksempelet) har alle diskene stablet. Vi tar sikte på å flytte en hel stabel med disker fra en stang (A) til en annen (C) ved å følge noen spesifikke regler.
Her er det første oppsettet av puslespillet-
Og dette er det endelige målet-
Reglene for Tower of Hanoi
Her er noen viktige regler for Tower of Hanoi:
- Den opprinnelige tilstanden til dette puslespillet, alle diskene vil bli stablet i stang én.
- Den endelige tilstanden er at alle diskene fra stang en vil bli stablet på stang to eller stang tre.
- Vi kan flytte en on-disk fra en stang til en annen til enhver tid.
- Vi kan bare flytte den øverste skiven fra stangen.
- En disk kan ikke plasseres over en annen disk, som er mindre.
Den opprinnelige legenden handlet om å flytte 64 disker. Prestene kunne flytte en disk om gangen i henhold til reglene. Ifølge legenden var det en profeti om at verden ville ende hvis de kunne fullføre handlingen. I tidskompleksitetsdelen vil vi vise at en Tower of Hanoi-innstilling på n disker vil koste 2^n – 1 trekk.
Så hvis prestene kunne kreve 1 sekund for å flytte diskene, ville den totale tiden de ville trenge for å løse gåten være 2^64 – 1 sekund eller 584,942,417,356 26 7 15 år, XNUMX dager, XNUMX timer og XNUMX sekunder.
Algoritme for Tower of Hanoi
En generell måte å løse Tower of Hanoi på er en rekursiv algoritme. Først må vi bestemme oss for to stenger eller knagger som kilde og destinasjon, og reservepinnen vil være en hjelpe- eller hjelper.
Her er trinnene for å løse Tower of Hanoi-puslespillet:
- Flytt de øverste n-1 diskene fra kildepinnen til hjelpepinnen.
- Etterpå flytter du den n'te disken fra kildepinnen til destinasjonspinnen.
- Til slutt flytter du resten av n-1 diskene fra hjelpepinnen til destinasjonspinnen.
Merknader: Hvis vi har en 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 og vurdere peg A som kilden, peg B som hjelperen og peg C som destinasjon
Trinn 1) Til å begynne med vil alle diskene bli stablet på pinne A.
På dette stadiet:
Kilde = Peg A
Destinasjon = Peg C
Hjelper = 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, bryter det problemet vårt fra et 3-disk-problem til et 2-disk-problem, som er et rekursivt kall.
Trinn 2) Ettersom vi kaller et rekursivt anrop fra peg A og målet er peg B, vil vi bruke peg C som en hjelper.
Legg merke til at vi er på trinn én igjen for det samme tårnet i Hanoi-problemet for to disker.
Nå må vi flytte n-1 eller en disk fra kilde til hjelper, flytte den minste disken fra pinne A til pinne C.
På dette stadiet:
Kilde = pinne A
Destinasjon = pinne B
Hjelper = pinne C
Trinn 3) Deretter, i henhold til vår algoritme, skal det n-te eller andre diskbehovet overføres til destinasjonen eller peg B.
På dette stadiet:
Kilde = pinne A
Destinasjon = pinne B
Hjelper = pinne C
Trinn 4) Nå vil vi flytte n-1-diskene eller disken en fra hjelperen eller pinne C til destinasjonen eller pinne B i henhold til den tredje fasen av algoritmen vår.
På dette stadiet:
Kilde = pinne A
Destinasjon = pinne B
Hjelper = pinne C
Trinn 5) Etter å ha fullført den rekursive samtalen, vil vi gå tilbake til vår forrige innstilling når den første fasen av algoritmen.
Trinn 6) Nå, i det andre trinnet, vil vi flytte kilden vår til destinasjonen vår, som flytter disk 3 til pinne C fra pinne A.
På dette stadiet:
Kilde = pinne A
Destinasjon = pinne C
Hjelper = knagg B
Trinn 7) Nå kan vi se det
d er å flytte de gjenværende diskene fra hjelperen (pinnen B) til destinasjonen (pinnen C). Vi vil bruke den opprinnelige kilden eller pinne A som en hjelper i dette tilfellet.
Trinn 8) Siden vi ikke kan flytte to disker samtidig, vil vi kalle et rekursivt kall for disk 1. I henhold til siste trinn og vår algoritme, en destinasjon i dette trinnet er pinne A.
På dette stadiet:
Kilde = pinne B
Destinasjon = pinne A
Hjelper = pinne C
Trinn 9) Vår rekursive samtale er fullført nå. Deretter flytter vi disk 2 fra kilden til destinasjonen.
På dette stadiet:
Kilde = pinne B
Destinasjon = pinne C
Hjelper = pinne A
Trinn 10) Deretter flytter vi vår gjenværende n-1 eller disk 1 fra hjelper til destinasjon.
På dette stadiet:
Kilde = pinne A
Destinasjon = pinne C
Hjelper = knagg 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;
}
Produksjon
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 kompleksiteten i tid og rom til Tower of Hanoi:
1) Tidskompleksitet:
Hvis vi ser tilbake på algoritmen vår, kan vi se at vi introduserer et rekursivt kall for (n-1) disker to ganger. Disse rekursive kallene for (n-1) disker kan brytes ned i andre ((n-1)-1) og så videre til vi bare får én disk å flytte.
For tre disker-
- Disk 3 kaller en rekursiv funksjon for disk to to ganger.
- Disk 2 kaller en rekursiv funksjon for disk én to ganger.
- Disk 1 kan bevege seg innenfor konstant tid, og tid til å løse for tre disker.
= 2*(Tid for å løse for to disker) + konstant Tid for å flytte disk 3
= 2*(2*tid å 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 kan det skrives som –
(2n-1 * konstant tid for å flytte disk 1 + 2n-2 * konstant tid for å flytte disk 2 + ….
Denne geometriske progresjonen vil resultere i O(2n-1) Eller O(2n), som er eksponentiell.
2) Romkompleksitet
Romkompleksiteten til Tower of Hanoi er 0(n). Det er fordi vi må lagre rekkefølgen på platene. Når vi bruker rekursjonen, bruker den stabelen. Og den maksimale størrelsen på stabelen kan være "n." Det er derfor romkompleksiteten blir O(n).
