Tower of Hanoi Algoritm: Python, C++ Code

Vad är Tower of Hanoi?

Hanois torn är ett matematiskt pussel som består av tre stavar och en stapel skivor av minskande storlek placerade ovanpå varandra. Det är också känt som Brahmas torn eller Lucas-tornet, eftersom den franske matematikern Edouard Lucas introducerade det 1883. Pusslet är baserat på legender om att flytta guldskivor mellan tre stavar.

Detta pussel har tre stavar och ett variabelt antal staplade skivor. Stavarna är arrangerade som cykliska torn, så de större skivorna är staplade längst ner och de mindre skivorna är staplade ovanpå.

Inledningsvis får vi tre pinnar eller stavar. En av dem (pinne A i exemplet) har alla skivor staplade. Målet är att flytta hela stapeln från en stav (A) till en annan (C) samtidigt som man följer några specifika regler.

Här är den ursprungliga uppställningen av pusslet:

Tornet i Hanoi problem

Och detta är det slutgiltiga målet:

Regler för Tower of Hanoi

Här är de viktigaste reglerna för Hanois torn:

• I pusslets initiala tillstånd är alla skivor staplade på stång ett.
• I sluttillståndet staplas alla skivor från stång ett på stång två eller stång tre.
• Endast en skiva kan röra sig från en stång till en annan åt gången.
• Endast den översta skivan på en stång kan flyttas.
• En disk kan inte placeras ovanpå en mindre disk.

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 om tidskomplexitet kommer vi att visa att en Hanoi-tornuppsättning med n skivor kräver 2^n – 1 drag.

Så, om prästerna behövde 1 sekund för att flytta en disk, skulle den totala tiden för att lösa pusslet vara 2^64 – 1 sekund, eller ungefär 584 942 417 356 år, 26 dagar, 7 timmar och 15 sekunder.

Algoritm för Tower of Hanoi

Det vanligaste sättet att lösa Hanoi-tornet är en rekursiv algoritm. Först väljer vi två stavar som källa och destination; reservpinnen fungerar som hjälppinne eller hjälptång.

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 den n:te disken från källpinnen till destinationspinnen.
• Flytta de återstående n-1 diskarna från hjälppinnen till destinationspinnen.

Obs: Om vi ​​har en enda disk kan vi flytta den direkt från källan till destinationen.

Hur man löser Tower of Hanoi Puzzle

Låt oss illustrera algoritmen för tre skivor. Betrakta peg A som källa, peg B som hjälp och peg C som destination.

Steg 1) Ursprungligen staplas alla skivor på pinne 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.

Obs: Även om vi bara kan flytta en disk åt gången, reducerar detta steg vårt 3-diskproblem till ett 2-diskproblem, vilket hanteras av ett rekursivt anrop.

Steg 2) När vi gör ett rekursivt anrop från peg A med peg B som destination, använder vi peg C som hjälpare.

Observera att vi är tillbaka på steg ett för samma problem med Hanoi-tornet, men nu för två skivor. Vi flyttar n-1 (det vill säga en) skiva från källan till hjälpskivan, vilket flyttar den minsta skivan från pinne A till pinne C.

I detta skede: Källa = peg A, Destination = peg B, Hjälpare = peg C.

Steg 3) Enligt algoritmen överförs nu den n:te (2:a) disken till destinationen, peg B.

I detta skede: Källa = peg A, Destination = peg B, Hjälpare = peg C.

Steg 4) Nu flyttar vi n-1-disken (disk ett) från hjälppinne C till destinationspinne B, enligt algoritmens tredje steg.

I detta skede: Källa = peg A, Destination = peg B, Hjälpare = peg C.

Steg 5) Efter att ha slutfört det rekursiva anropet återgår vi till vår tidigare inställning i algoritmens första steg.

Steg 6) I det andra steget flyttar vi disk 3 från källpinne A till destinationspinne C.

I detta skede: Källa = peg A, Destination = peg C, Hjälpare = peg B.

Steg 7) Nästa uppgift är att flytta de återstående diskarna från hjälpen (peg B) till destinationen (peg C). Vi kommer att använda den ursprungliga källan (peg A) som hjälp den här gången.

Steg 8) Eftersom vi inte kan flytta två diskar samtidigt gör vi ett rekursivt anrop för disk 1. Enligt vår algoritm, destinationen i detta steg är peg A.

I detta skede: Källa = peg B, Destination = peg A, Hjälpare = peg C.

Steg 9) Vårt rekursiva anrop är slutfört. Vi flyttar nu disk 2 från dess källa till dess destination.

I detta skede: Källa = peg B, Destination = peg C, Hjälpare = peg A.

Steg 10) Vi avslutar med att flytta den återstående n-1 disken (disk 1) från hjälparen till destinationen.

I detta skede: Källa = peg A, Destination = peg C, Hjälpare = peg B.

Pseudo Code för Hanois torn

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 tids- och rumskomplexiteten i Hanois torn:

1) Tidskomplexitet:

Om vi ​​tittar tillbaka på algoritmen gör vi ett rekursivt anrop för (n-1) diskar två gånger per anrop. Varje (n-1) rekursion delas upp i ((n-1)-1) rekursioner, och så vidare, tills vi når basfallet med en enda disk.

För tre skivor:

• Disk 3 anropar den rekursiva funktionen för disk 2 två gånger.
• Disk 2 anropar den rekursiva funktionen för disk 1 två gånger.
• Skiva 1 rör sig i konstant tid, vilket ger tid att lösa för tre diskar.

Uttryckt som en återkommande händelse:

= 2 × (Tid att lösa för två skivor) + konstant tid att flytta skiva 3

= 2 × (2 × tid att lösa för en disk + konstant tid att flytta disk 2) + konstant tid att flytta disk 3

= (2 × 2) × konstant tid för att flytta disk 1 + 2 × konstant tid för att flytta disk 2 + konstant tid för att flytta disk 3

För n diskar blir detta:

2^{N 1} × konstant tid att flytta skiva 1 + 2^{N 2} × konstant tid för att flytta disk 2 + ….

Denna geometriska progression summerar till O(2ⁿ – 1), vilket förenklar O (2ⁿ), en exponentiell tidskomplexitet.

2) Rymdkomplexitet:

Rymdkomplexiteten för Hanoi-tornet är O(n). Rekursionen använder anropsstacken, och stackens maximala djup är lika med n, antalet diskar. Det är därför rymdkomplexiteten är O(n).

Vanliga frågor