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

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-

Toren van Hanoi Probleem
Toren van Hanoi Probleem

En dit is het uiteindelijke doel-

Toren van Hanoi

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 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 daad konden voltooien. In de tijd complexIn dit gedeelte zullen we laten zien dat een Tower of Hanoi-setting van n schijven 2^n – 1 zet zou kosten.

Dus als de priesters 1 seconde nodig zouden hebben om de schijven te verplaatsen, zou de totale tijd die ze nodig 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.

Los de Toren van Hanoi-puzzel op

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.

Los de Toren van Hanoi-puzzel op

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.

Los de Toren van Hanoi-puzzel op

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.

Los de Toren van Hanoi-puzzel op

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

Los de Toren van Hanoi-puzzel op

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 verplaatsenneoMeestal zullen we een recursieve oproep voor schijf 1 aanroepen. Volgens de laatste stap en onze algoritme, een bestemming in deze stap is peg A.

Los de Toren van Hanoi-puzzel op

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.

Los de Toren van Hanoi-puzzel op

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.

Los de Toren van Hanoi-puzzel op

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

complexity van de Toren van Hanoi

Hier zijn de Time en Space Complexiteit van de Toren van Hanoi:

1) Tijd complexiteit:

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) Ruimte complexity

De ruimte complexDe sterkte van de Toren van Hanoi is 0(n). Dat komt omdat we de volgorde van de platen moeten opslaan. Wanneer we de recursie gebruiken, gebruikt deze de stapel. En de maximale grootte van de stapel kan ‘n’ zijn. Dat is de reden waarom de ruimte complexiteit wordt O(n).