Toren van Hanoi-algoritme: Python, C++ Code
Sara Chen
Wat is de toren van Hanoi?
De Toren van Hanoi is een wiskundige puzzel bestaande uit drie staven en talloze schijven die over elkaar zijn geplaatst. Het staat ook bekend als de Toren van Brahma of de Lucas-toren, zoals de Franse wiskundige Edouard Lucas hem in 1883 introduceerde. Deze puzzel is gebaseerd op legendes over het verplaatsen van gouden schijven tussen drie staven.
Deze puzzel heeft drie staven en een variabel aantal op elkaar gestapelde schijven. Die staven zijn ontworpen als cyclische torens. De grotere schijven in diameter worden dus op de bodem gestapeld en de kleinere schijven bovenaan.
In eerste instantie krijgen we drie pinnen of staven. En in één ervan (A, weergegeven in het voorbeeld) zijn alle schijven gestapeld. We streven ernaar om een hele stapel schijven van de ene staaf (A) naar de andere (C) te verplaatsen door een aantal specifieke regels te volgen.
Hier is de eerste opzet van de puzzel-
En dit is het uiteindelijke doel-
Regels van de Toren van Hanoi
Hier zijn enkele essentiële regels voor de Toren van Hanoi:
- In de begintoestand van deze puzzel worden alle schijven in staaf één gestapeld.
- De uiteindelijke toestand is dat al die schijven van staaf één op staaf twee of staaf drie worden gestapeld.
- We kunnen op elk moment een schijf op de schijf van de ene staaf naar de andere verplaatsen.
- We kunnen alleen de bovenste schijf van de staaf verplaatsen.
- Een schijf kan niet over een andere schijf worden geplaatst, die kleiner is.
De originele legende ging over het verplaatsen van 64 schijven. De priesters mochten één schijf per keer verplaatsen volgens de regels. Volgens de legende was er een profetie dat de wereld zou vergaan als ze de daad konden voltooien. In het gedeelte over tijdcomplexiteit laten we zien dat een Tower of Hanoi-setting van n schijven 2^n – 1 verplaatsing zou kosten.
Dus als de priesters 1 seconde nodig hadden om de schijven te verplaatsen, zou de totale tijd die ze nodig zouden hebben om de puzzel op te lossen 2^64 – 1 seconde of 584,942,417,356 jaar, 26 dagen, 7 uur en 15 seconden zijn.
Algoritme voor de toren van Hanoi
Een algemene manier om de Toren van Hanoi op te lossen is een recursief algoritme. Eerst moeten we beslissen over twee hengels of pinnen als bron en bestemming, en de reservepin zou een hulpmiddel of helper zijn.
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 daarna de zoveelste schijf van de bronpeg naar de bestemmingspeg.
- Verplaats ten slotte de overige n-1 schijven van de hulppeg naar de bestemmingspeg.
Note: Als we één enkele schijf hebben, kunnen we deze rechtstreeks van bron naar bestemming verplaatsen.
Hoe de Toren van Hanoi-puzzel op te lossen
Laten we het algoritme voor drie schijven illustreren en peg A als de bron, peg B als de helper en peg C als de bestemming beschouwen
Stap 1) In eerste instantie worden alle schijven op pin A gestapeld.
In dit stadium:
Bron = Peg A
Bestemming = Peg C
Helper = Pin B
Nu moeten we de bovenste n-1-schijven van de bron naar de helper verplaatsen.
Opmerking: Hoewel we slechts één schijf tegelijk kunnen verplaatsen, verandert ons probleem van een probleem met drie schijven naar een probleem met twee schijven, wat een recursieve aanroep is.
Stap 2) Omdat we een recursieve aanroep van peg A aanroepen en de bestemming peg B is, zullen we peg C als helper gebruiken.
Merk op dat we ons weer in fase één bevinden voor hetzelfde probleem met de toren van Hanoi voor twee schijven.
Nu moeten we n-1 of één schijf van bron naar helper verplaatsen, waarbij we de kleinste schijf van pin A naar pin C verplaatsen.
In dit stadium:
Bron = pin A
Bestemming = pin B
Helper = pin C
Stap 3) Vervolgens moeten, volgens ons algoritme, de n-de of 2e schijfbehoeften worden overgebracht naar de bestemming of peg B.
In dit stadium:
Bron = pin A
Bestemming = pin B
Helper = pin C
Stap 4) Nu zullen we de n-1 schijven of schijf één verplaatsen van helper of peg C naar de bestemming of peg B volgens de derde fase van ons algoritme.
In dit stadium:
Bron = pin A
Bestemming = pin B
Helper = 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) Nu, in de tweede fase, zullen we onze bron naar onze bestemming verplaatsen, namelijk het verplaatsen van schijf 3 naar pin C van pin A.
In dit stadium:
Bron = pin A
Bestemming = pin C
Helper = pin B
Stap 7) Nu kunnen we dat zien
d is om de resterende schijven van helper (pin B) naar bestemming (pin C) te verplaatsen. In dit geval zullen we de oorspronkelijke bron of pin A als hulpmiddel gebruiken.
Stap 8) Omdat we niet twee schijven tegelijk kunnen verplaatsen, zullen we een recursieve aanroep doen voor schijf 1. Volgens de laatste stap en onze algoritme, een bestemming in deze stap is peg A.
In dit stadium:
Bron = pin B
Bestemming = pin A
Helper = pin C
Stap 9) Onze recursieve aanroep is nu voltooid. Vervolgens verplaatsen we schijf 2 van de bron naar de bestemming.
In dit stadium:
Bron = pin B
Bestemming = pin C
Helper = pin A
Stap 10) Vervolgens verplaatsen we onze resterende n-1 of schijf 1 van helper naar bestemming.
In dit stadium:
Bron = pin A
Bestemming = pin C
Helper = pin B
Pseudocode 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;
}
uitgang
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
Dit zijn de tijd- en ruimtecomplexiteit van de Toren van Hanoi:
1) Tijdcomplexiteit:
Als we terugkijken naar ons algoritme, kunnen we zien dat we tweemaal een recursieve oproep voor (n-1) schijven introduceren. Die recursieve oproepen voor (n-1) schijven kunnen worden opgesplitst in andere ((n-1)-1) enzovoort totdat we maar één schijf kunnen verplaatsen.
Voor drie schijven-
- Schijf 3 roept tweemaal een recursieve functie op voor schijf twee.
- Schijf 2 roept tweemaal een recursieve functie op voor schijf één.
- Schijf 1 kan binnen een constante tijd bewegen, en tijd om drie schijven op te lossen.
= 2*(Tijd om op te lossen voor twee schijven) + 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 kan het worden geschreven als –
(2n-1 * constante tijd om schijf 1 + 2 te verplaatsenn-2 * constante tijd om schijf 2 + … te verplaatsen.
Deze geometrische progressie zal resulteren in O(2n-1) Of O (2n), wat exponentieel is.
2) Ruimtelijke complexiteit
De ruimtelijke complexiteit van de Toren van Hanoi is 0(n). Dat komt omdat we de volgorde van de platen moeten opslaan. Wanneer we de recursie gebruiken, gebruiken we de stapel. En de maximale grootte van de stapel kan "n" zijn. Daarom wordt de ruimtelijke complexiteit O(n).
