Tower of Hanoi Algoritm: Python, C++ Koda
Sarah Chen
Vad är Tower of Hanoi?
Tornet i Hanoi är ett matematiskt pussel som består av tre stavar och många skivor placerade över varandra. Det är också känt som Brahma-tornet eller Lucas-tornet, eftersom den franske matematikern Edouard Lucas introducerade det redan 1883. Detta pussel är baserat på legender om att flytta guldskivor mellan tre stavar.
Detta pussel har tre stavar och ett varierande antal staplade skivor. Dessa stavar är designade som cykliska torn. Så de större skivorna i diameter staplas på botten och de mindre skivorna staplas ovanpå.
Till en början får vi tre pinnar eller stavar. Och en av dem (A, som visas i exemplet) har alla diskar staplade. Vi siktar på att flytta en hel stapel med diskar från ett spö (A) till ett annat (C) genom att följa några specifika regler.
Här är den första uppsättningen av pusslet-
Och detta är det sista målet-
Regler för Tower of Hanoi
Här är några viktiga regler för Tower of Hanoi:
- Det initiala tillståndet för detta pussel, alla skivorna kommer att staplas i spö ett.
- Sluttillståndet är att alla skivor från spö ett kommer att staplas på spö två eller spö tre.
- Vi kan flytta en on-disk från ett spö till ett annat när som helst.
- Vi kan bara flytta den översta skivan från stången.
- En disk kan inte placeras över en annan disk, som är mindre.
Den ursprungliga legenden handlade om att flytta 64 skivor. Prästerna kunde flytta en skiva i taget enligt reglerna. Enligt legenden fanns det en profetia om att världen skulle gå under om de kunde slutföra handlingen. I avsnittet med tidskomplexitet kommer vi att visa att en Tower of Hanoi-inställning med n diskar skulle kosta 2^n – 1 drag.
Så, om prästerna kunde kräva 1 sekund för att flytta skivorna, skulle den totala tiden de skulle behöva för att lösa pusslet vara 2^64 – 1 sekund eller 584,942,417,356 26 7 15 år, XNUMX dagar, XNUMX timmar och XNUMX sekunder.
Algoritm för Tower of Hanoi
Ett allmänt sätt att lösa Tower of Hanoi är en rekursiv algoritm. Först måste vi bestämma oss för två stavar eller pinnar som källa och destination, och reservpinnen skulle vara en hjälp eller hjälpare.
Här är stegen för att lösa Tower of Hanoi-pusslet:
- Flytta de översta n-1-skivorna från källpinnen till hjälppinnen.
- Flytta sedan den n:te skivan från källpeggen till destinationspeggen.
- Flytta slutligen resten av n-1-skivorna från hjälppinnen till destinationspinnen.
Anmärkningar: Om vi har en enda disk kan vi flytta den direkt från källa till destination.
Hur man löser Tower of Hanoi Puzzle
Låt oss illustrera algoritmen för tre diskar och betrakta peg A som källan, peg B som hjälparen och peg C som destination
Steg 1) Inledningsvis kommer alla diskar att staplas på peg A.
I detta skede:
Källa = Peg A
Destination = Peg C
Hjälpare = Peg B
Nu måste vi flytta de översta n-1-skivorna från källan till hjälparen.
Notera: Även om vi bara kan flytta en disk åt gången, bryter det vårt problem från ett problem med tre diskar till ett problem med två diskar, vilket är ett rekursivt anrop.
Steg 2) Eftersom vi anropar ett rekursivt anrop från peg A och destinationen är peg B, kommer vi att använda peg C som en hjälpare.
Lägg märke till att vi är i steg ett igen för samma tower of Hanoi problem för två diskar.
Nu måste vi flytta n-1 eller en skiva från källa till hjälpare, flytta den minsta skivan från peg A till peg C.
I detta skede:
Källa = pinne A
Destination = peg B
Hjälpare = pinne C
Steg 3) Sedan, enligt vår algoritm, bör det n:e eller 2:a diskbehovet överföras till destinationen eller peg B.
I detta skede:
Källa = pinne A
Destination = peg B
Hjälpare = pinne C
Steg 4) Nu kommer vi att flytta n-1-skivorna eller skivan ett från hjälparen eller peg C till destinationen eller peg B enligt det tredje steget i vår algoritm.
I detta skede:
Källa = pinne A
Destination = peg B
Hjälpare = pinne C
Steg 5) Efter att ha slutfört det rekursiva samtalet kommer vi att återgå till vår tidigare inställning när det första steget av algoritmen.
Steg 6) Nu, i det andra steget, kommer vi att flytta vår källa till vår destination, som flyttar skiva 3 till peg C från peg A.
I detta skede:
Källa = pinne A
Destination = pinne C
Hjälpare = pinne B
Steg 7) Nu kan vi se det
d är att flytta de återstående skivorna från hjälpare (peg B) till destination (peg C). Vi kommer att använda den initiala källan eller peg A som hjälp i det här fallet.
Steg 8) Eftersom vi inte kan flytta två diskar samtidigt kommer vi att anropa ett rekursivt anrop för disk 1. Enligt det sista steget och vår algoritm, en destination i detta steg är peg A.
I detta skede:
Källa = pinne B
Destination = pinne A
Hjälpare = pinne C
Steg 9) Vårt rekursiva samtal är avslutat nu. Sedan flyttar vi disk 2 från dess källa till dess destination.
I detta skede:
Källa = pinne B
Destination = pinne C
Hjälpare = pinne A
Steg 10) Sedan flyttar vi vår återstående n-1 eller disk 1 från hjälpare till destination.
I detta skede:
Källa = pinne A
Destination = pinne C
Hjälpare = pinne B
Pseudokod för 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
Programkod in 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
Programkod in 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')
Produktion:
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
Komplexiteten av Tower of Hanoi
Här är komplexiteten i tid och rum i Hanois torn:
1) Tidskomplexitet:
Om vi tittar tillbaka på vår algoritm kan vi se att vi introducerar ett rekursivt anrop för (n-1) diskar två gånger. Dessa rekursiva anrop för (n-1) diskar kan delas upp i andra ((n-1)-1) och så vidare tills vi bara får en disk att flytta.
För tre diskar-
- Disk 3 anropar en rekursiv funktion för disk två två gånger.
- Disk 2 anropar en rekursiv funktion för disk ett två gånger.
- Disk 1 kan röra sig inom konstant tid, och tid att lösa för tre diskar.
= 2*(Tid att lösa för två skivor) + konstant Tid att flytta skiva 3
= 2*(2*tid att lösa för en skiva + konstant Tid att flytta skiva 2) + konstant Tid att flytta skiva 3
= (2*2) (konstant tid för att flytta skiva 1) + 2*konstant tid för att flytta skiva 2 + konstant tid för att flytta skiva 3
För n diskar kan det skrivas som –
(2N 1 * konstant tid för att flytta skiva 1 + 2N 2 * konstant tid för att flytta disk 2 + ….
Denna geometriska progression kommer att resultera i O(2N 1) Eller O (2n), vilket är exponentiellt.
2) Rymdens komplexitet
Rymdkomplexiteten för Tower of Hanoi är 0(n). Det beror på att vi måste lagra tallrikarnas sekvens. När vi använder rekursionen använder den stacken. Och den maximala storleken på stacken kan vara "n." Det är därför rymdkomplexiteten blir O(n).
