Hanoi torni algoritm: Python, C++ kood

Mis on Hanoi torn?

Hanoi torn on matemaatiline pusle, mis koosneb kolmest vardast ja paljudest üksteise peale asetatud ketastest. Seda tuntakse ka kui Brahma torni või Lucase torni, kuna prantsuse matemaatik Edouard Lucas tutvustas seda juba aastal 1883. See pusle põhineb legendidel kuldketaste liigutamisest kolme varda vahel.

Sellel puslel on kolm varrast ja muutuv arv virnastatud kettaid. Need vardad on konstrueeritud tsükliliste tornidena. Niisiis, suurema läbimõõduga kettad on virnastatud põhja ja väiksemad kettad on virnastatud.

Esialgu antakse meile kolm pulka või varda. Ja ühes neist (näites näidatud A) on kõik kettad virnastatud. Meie eesmärk on teisaldada terve virn kettaid ühelt vardalt (A) teisele (C), järgides teatud reegleid.

Siin on mõistatuse esialgne seadistus -

Ja see on viimane eesmärk -

Hanoi torni reeglid

Siin on mõned olulised reeglid Hanoi torni jaoks:

• Selle pusle esialgne olek, kõik kettad on virnastatud varras üks.
• Lõppseisund on see, et kõik need esimese varda kettad asetatakse teise või kolmanda varda peale.
• Saame igal ajal liigutada ketta ühelt vardalt teisele.
• Saame varda küljest liigutada ainult kõige ülemist ketast.
• Ketast ei saa asetada teise ketta peale, mis on väiksem.

Algne legend rääkis 64 ketta teisaldamisest. Preestrid võisid vastavalt reeglitele liigutada ühte ketast korraga. Legendi järgi oli ennustus, et maailmalõpp saabub, kui nad teo lõpule jõuavad. Ajalise keerukuse osas näitame, et n kettast koosnev Tower of Hanoi seadistus maksaks 2^n – 1 liigutus.

Seega, kui preestrid võiksid nõuda ketaste liigutamiseks 1 sekundit, oleks mõistatuse lahendamiseks kuluv koguaeg 2^64 – 1 sekund ehk 584,942,417,356 26 7 15 aastat, XNUMX päeva, XNUMX tundi ja XNUMX sekundit.

Hanoi torni algoritm

Üks üldine viis Hanoi torni lahendamiseks on rekursiivne algoritm. Esiteks peame allika ja sihtkohana otsustama kahe varda või pulga kasuks ning varupulk oleks abi- või abipulk.

Siin on sammud Hanoi torni mõistatuse lahendamiseks:

• Liigutage ülemised n-1 kettad lähtepulgalt abipulgale.
• Seejärel liigutage n-s ketas lähtepunktist sihtpunkti.
• Lõpuks teisaldage ülejäänud n-1 ketast abipulgalt sihtpunkti.

märkused: kui meil on üks ketas, saame selle otse allikast sihtkohta teisaldada.

Kuidas lahendada Hanoi torni mõistatus

Illustreerime kolme ketta algoritmi ja vaatleme allikana pulka A, abimehena pulti B ja sihtkohana puud C.

Step 1) Esialgu asetatakse kõik kettad pulgale A.

Selles etapis:

Allikas = Peg A
Sihtkoht = pulk C
Abimees = pulk B

Nüüd peame ülemised n-1 kettad allikast abistajasse teisaldama.

Märge: Kuigi me saame liigutada ainult ühte ketast korraga, muudab see meie probleemi kolme ketta probleemist kahe ketta probleemiks, mis on rekursiivne kõne.

Step 2) Kuna me nimetame rekursiivset kõnet pulgalt A ja sihtpunktiks on pulk B, kasutame abivahendina pulti C.

Pange tähele, et oleme taas esimeses etapis sama Hanoi torni kahe ketta probleemi jaoks.

Nüüd peame teisaldama n-1 ehk ühe ketta allikast abistaja juurde, liigutades väikseima ketta pulgalt A pulgale C.

Selles etapis:

Allikas = pulk A
Sihtkoht = pulk B
Abimees = pulk C

Step 3) Seejärel tuleks vastavalt meie algoritmile n-nda või 2. ketta vajadus kanda sihtkohta või pulgasse B.

Selles etapis:

Allikas = pulk A
Sihtkoht = pulk B
Abimees = pulk C

Step 4) Nüüd teisaldame n-1 ketast või ketta ühe abimehest või puldist C sihtkohta või pulgasse B vastavalt meie algoritmi kolmandale etapile.

Selles etapis:

Allikas = pulk A
Sihtkoht = pulk B
Abimees = pulk C

Step 5) Pärast rekursiivse kõne lõpetamist naaseme oma eelmise seadistuse juurde, kui algoritmi esimene etapp.

Step 6) Nüüd, teises etapis, teisaldame oma allika sihtkohta, milleks on ketta 3 teisaldamine pulgalt A pulgale C.

Selles etapis:

Allikas = pulk A
Sihtkoht = pulk C
Abimees = pulk B

Step 7) Nüüd näeme seda

d on ülejäänud ketaste teisaldamine abist (pulk B) sihtkohta (pulk C). Kasutame sel juhul abistajana algallikat ehk pulka A.

Step 8) Kuna me ei saa kahte ketast korraga liigutada, kutsume välja ketta 1 rekursiivse kutse. Vastavalt viimasele sammule ja meie algoritm, on selle etapi sihtkoht pulk A.

Selles etapis:

Allikas = pulk B
Sihtkoht = pulk A
Abimees = pulk C

Step 9) Meie rekursiivne kõne on nüüd lõpetatud. Seejärel teisaldame ketta 2 allikast sihtkohta.

Selles etapis:

Allikas = pulk B
Sihtkoht = pulk C
Abimees = pulk A

Step 10) Seejärel viime oma ülejäänud n-1 või ketta 1 abimehest sihtkohta.

Selles etapis:

Allikas = pulk A
Sihtkoht = pulk C
Abimees = pulk B

Hanoi torni pseudokood

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

Programmi kood sisse 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;
}

Väljund

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

Programmi kood sisse 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')

Väljund:

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

Hanoi torni keerukus

Siin on Hanoi torni aja ja ruumi keerukus:

1) Aja keerukus:

Kui vaatame oma algoritmile tagasi, näeme, et me võtame kaks korda sisse (n-1) ketaste rekursiivse kutse. Neid (n-1) ketaste rekursiivseid väljakutseid saab jaotada muudeks ((n-1)-1) ja nii edasi, kuni liigutatakse ainult üks ketas.

Kolme ketta jaoks -

• Disk 3 kutsub kaks korda rekursiivset funktsiooni kettale kaks.
• Disk 2 kutsub kaks korda ketta XNUMX rekursiivset funktsiooni.
• 1. ketas saab liikuda konstantse aja ja kolme ketta lahendamise aja piires.

= 2*(Kahe ketta lahendamise aeg) + konstantne 3. ketta liigutamise aeg

= 2*(2*ühe ketta lahendamise aeg + konstant 2. ketta liigutamise aeg) + konstant 3. ketta liigutamise aeg

= (2*2) (püsiv aeg ketta 1 liigutamiseks) + 2*püsiv aeg ketta 2 liigutamiseks + konstantne aeg ketta 3 liigutamiseks

n ketta puhul saab selle kirjutada järgmiselt -

(2^n-1 * konstantne aeg ketta 1 + 2 liigutamiseks^n-2 * konstantne aeg ketta 2 liigutamiseks + ….

Selle geomeetrilise progressiooni tulemuseks on O(2^n-1) Või O(2ⁿ), mis on eksponentsiaalne.

2) Ruumi keerukus

Hanoi torni ruumiline keerukus on 0 (n). Seda seetõttu, et peame salvestama plaatide järjestuse. Kui me kasutame rekursiooni, kasutab see virna. Ja virna maksimaalne suurus võib olla "n". Sellepärast muutub ruumi keerukus O(n).