Toren van Hanoi-algoritme: Python, C++ Code

Wat is de toren van Hanoi?

De Toren van Hanoi is een wiskundige puzzel die bestaat uit drie staven en een stapel schijven van afnemende grootte die op elkaar gestapeld zijn. Hij staat ook bekend als de Toren van Brahma of de Lucas-toren, omdat de Franse wiskundige Edouard Lucas hem in 1883 introduceerde. De puzzel is gebaseerd op legendes over het verplaatsen van gouden schijven tussen drie staven.

Deze puzzel bestaat uit drie staven en een variabel aantal gestapelde schijven. De staven zijn gerangschikt in cyclische torens, waarbij de grotere schijven onderaan en de kleinere schijven bovenaan gestapeld zijn.

Aanvankelijk krijgen we drie pinnen of staven. Op één ervan (pin A in het voorbeeld) liggen alle schijven gestapeld. Het doel is om de hele stapel van de ene staaf (A) naar de andere (C) te verplaatsen, waarbij een aantal specifieke regels in acht moeten worden genomen.

Hier volgt de beginopstelling van de puzzel:

Toren van Hanoi Probleem

En dit is het uiteindelijke doel:

Regels van de Toren van Hanoi

Hier volgen de belangrijkste regels voor de Toren van Hanoi:

• In de beginfase van de puzzel liggen alle schijven op staaf één gestapeld.
• In de eindtoestand zijn alle schijven van staaf één op staaf twee of staaf drie gestapeld.
• Er kan slechts één schijf tegelijk van de ene stang naar de andere bewegen.
• Alleen de bovenste schijf op een stang kan worden bewogen.
• Een schijf kan niet bovenop een kleinere schijf worden geplaatst.

De oorspronkelijke legende ging over het verplaatsen van 64 schijven. De priesters konden, volgens de regels, één schijf tegelijk verplaatsen. Volgens de legende was er een profetie dat de wereld zou vergaan als ze de handeling zouden voltooien. In het gedeelte over tijdcomplexiteit zullen we aantonen dat een Toren van Hanoi-opstelling met n schijven 2^n – 1 zetten vereist.

Als de priesters dus 1 seconde nodig hadden om één schijf te verplaatsen, zou de totale tijd om de puzzel op te lossen 2^64 – 1 seconden bedragen, oftewel ongeveer 584,942,417,356 jaar, 26 dagen, 7 uur en 15 seconden.

Algoritme voor de toren van Hanoi

De meest gebruikelijke manier om de Toren van Hanoi op te lossen is met een recursief algoritme. Eerst kiezen we twee staven als begin- en eindpunt; de reservestaaf fungeert als hulpstaaf.

Hier zijn de stappen om de Tower of Hanoi-puzzel op te lossen:

• Verplaats de bovenste n-1 schijven van de bronpin naar de helperpin.
• Verplaats de n-de schijf van de bronpin naar de bestemmingspin.
• Verplaats de resterende n-1 schijven van de hulppin naar de bestemmingspin.

Let op: Als we één schijf hebben, kunnen we die direct van de bron naar de bestemming verplaatsen.

Hoe de Toren van Hanoi-puzzel op te lossen

Laten we het algoritme illustreren voor drie schijven. Beschouw pin A als de bron, pin B als de hulppin en pin C als de bestemming.

Stap 1) Aanvankelijk worden alle schijven op pen A gestapeld.

In dit stadium: Bron = Pin A, Bestemming = Pin C, Hulpmiddel = Pin B.

Nu moeten we de bovenste n-1-schijven van de bron naar de helper verplaatsen.

Let op: Hoewel we maar één schijf tegelijk kunnen verplaatsen, reduceert deze stap ons probleem met 3 schijven tot een probleem met 2 schijven, dat wordt opgelost door een recursieve aanroep.

Stap 2) Omdat we een recursieve aanroep doen vanuit pin A met pin B als bestemming, gebruiken we pin C als hulppin.

Merk op dat we weer bij stap één zijn voor hetzelfde probleem van de Toren van Hanoi, maar nu met twee schijven. We verplaatsen n-1 (dat wil zeggen, één) schijf van de bron naar de hulpschijf, waardoor de kleinste schijf van pin A naar pin C wordt verplaatst.

In deze fase geldt: Bron = pin A, Bestemming = pin B, Hulpmiddel = pin C.

Stap 3) Volgens het algoritme wordt de n-de (2e) schijf nu overgebracht naar de bestemming, pin B.

In deze fase geldt: Bron = pin A, Bestemming = pin B, Hulpmiddel = pin C.

Stap 4) Nu verplaatsen we de n-1 schijf (schijf één) van hulppen C naar bestemmingspen B, volgens de derde stap van het algoritme.

In deze fase geldt: Bron = pin A, Bestemming = pin B, Hulpmiddel = pin C.

Stap 5) Na het voltooien van de recursieve aanroep keren we terug naar onze vorige instelling in de eerste fase van het algoritme.

Stap 6) In de tweede fase verplaatsen we schijf 3 van bronpen A naar bestemmingspen C.

In dit stadium: Bron = pin A, Bestemming = pin C, Hulpmiddel = pin B.

Stap 7) De volgende stap is het verplaatsen van de resterende schijven van de hulpschijf (pen B) naar de bestemmingsschijf (pen C). We gebruiken hiervoor dit keer de oorspronkelijke bronschijf (pen A) als hulpschijf.

Stap 8) Omdat we niet twee schijven tegelijk kunnen verplaatsen, doen we een recursieve aanroep voor schijf 1. Volgens onze algoritmeDe bestemming in deze stap is pin A.

In dit stadium: Bron = pin B, Bestemming = pin A, Hulpmiddel = pin C.

Stap 9) Onze recursieve aanroep is voltooid. We verplaatsen nu schijf 2 van de bron naar de bestemming.

In dit stadium: Bron = pin B, Bestemming = pin C, Helper = pin A.

Stap 10) We sluiten af ​​door de resterende n-1 schijf (schijf 1) van de helper naar de bestemming te verplaatsen.

In dit stadium: Bron = pin A, Bestemming = pin C, Hulpmiddel = pin B.

Pseudo Code voor de Toren van 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

Programmacode 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;
}

Output:

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

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

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

Complexiteit van de Toren van Hanoi

Hieronder volgt de tijd- en ruimtecomplexiteit van de Toren van Hanoi:

1) Tijdcomplexiteit:

Als we terugkijken naar het algoritme, zien we dat we tweemaal per aanroep een recursieve aanroep doen voor (n-1) schijven. Elke (n-1) recursie wordt opgesplitst in ((n-1)-1) recursies, enzovoort, totdat we het basisgeval met één schijf bereiken.

Voor drie schijven:

• Schijf 3 roept de recursieve functie voor schijf 2 tweemaal aan.
• Schijf 2 roept de recursieve functie voor schijf 1 tweemaal aan.
• Schijf 1 beweegt in constante tijd, waardoor er tijd overblijft om de berekening voor drie schijven uit te voeren.

Uitgedrukt als een herhaling:

= 2 × (Tijd om twee schijven op te lossen) + constante tijd om schijf 3 te verplaatsen

= 2 × (2 × tijd om één schijf op te lossen + constante tijd om schijf 2 te verplaatsen) + constante tijd om schijf 3 te verplaatsen

= (2 × 2) × constante tijd om schijf 1 te verplaatsen + 2 × constante tijd om schijf 2 te verplaatsen + constante tijd om schijf 3 te verplaatsen

Voor n schijven wordt dit:

2^n-1 × constante tijd om schijf 1 + 2 te verplaatsen^n-2 × constante tijd om schijf 2 te verplaatsen + ….

Deze meetkundige reeks heeft een som van O(2).ⁿ – 1), wat vereenvoudigd kan worden tot O (2ⁿ), een exponentiële tijdscomplexiteit.

2) Ruimtecomplexiteit:

De ruimtecomplexiteit van de Toren van Hanoi is O(n). De recursie maakt gebruik van de aanroepstack, en de maximale diepte van de stack is gelijk aan n, het aantal schijven. Daarom is de ruimtecomplexiteit O(n).

Veelgestelde vragen