Algoritam kule Hanoi: Python, C++ Kodirati

Što je toranj u Hanoju?

Hanojski toranj je matematička zagonetka koja se sastoji od tri šipke i brojnih diskova postavljenih jedan preko drugog. Poznata je i kao Brahmin toranj ili Lucasov toranj, kako ju je predstavio francuski matematičar Edouard Lucas davne 1883. godine. Ova zagonetka temelji se na legendama o pomicanju zlatnih diskova između tri šipke.

Ova slagalica ima tri šipke i različiti broj naslaganih diskova. Te šipke su dizajnirane kao ciklički tornjevi. Dakle, diskovi većeg promjera slažu se na dno, a manji diskovi na vrh.

U početku su nam dana tri klina ili šipke. A jedan od njih (A, prikazan u primjeru) ima sve diskove naslagane. Cilj nam je premjestiti cijelu hrpu diskova s jedne šipke (A) na drugu (C) poštujući neka posebna pravila.

Ovdje je početna postavka zagonetke-

I ovo je konačni cilj-

Pravila tornja u Hanoju

Evo nekih osnovnih pravila za Hanojski toranj:

Početno stanje ove slagalice, svi će diskovi biti složeni u šipku jedan.
Konačno stanje je da će svi oni diskovi iz šipke jedan biti naslagani na šipku dva ili šipku tri.
Možemo premjestiti disk s jedne šipke na drugu u bilo kojem trenutku.
Sa šipke možemo pomaknuti samo gornji disk.
Disk se ne može staviti preko drugog diska, koji je manji.

Izvorna legenda govorila je o premještanju 64 diska. Svećenici su prema pravilima mogli pomicati jedan po jedan disk. Prema legendi, postojalo je proročanstvo da će svijet završiti ako uspiju dovršiti čin. U odjeljku o vremenskoj složenosti, pokazat ćemo da bi postavka Hanojskog tornja od n diskova koštala 2^n – 1 potez.

Dakle, ako bi svećenicima bila potrebna 1 sekunda da pomaknu diskove, ukupno vrijeme koje bi im bilo potrebno za rješavanje zagonetke bilo bi 2^64 – 1 sekunda ili 584,942,417,356 godina, 26 dana, 7 sati i 15 sekundi.

Algoritam za Hanojski toranj

Jedan opći način rješavanja Hanojskog tornja je rekurzivni algoritam. Prvo se trebamo odlučiti za dva štapa ili klina kao izvor i cilj, a rezervni klin bi bio pomoćni ili pomoćni.

Evo koraka za rješavanje zagonetke Hanojskog tornja:

Pomaknite gornjih n-1 diskova s izvornog klina na pomoćni klin.
Nakon toga, premjestite n-ti disk s izvornog klina na odredišni klin.
Na kraju, premjestite ostatak n-1 diskova s pomoćnog klina na odredišni klin.

bilješke: Ako imamo jedan disk, možemo ga izravno premjestiti s izvora na odredište.

Kako riješiti zagonetku Tower of Hanoi

Ilustrirajmo algoritam za tri diska i razmotrimo klin A kao izvor, klin B kao pomoćnik, a klin C kao odredište

Korak 1) U početku će svi diskovi biti složeni na klin A.

U ovoj fazi:

Izvor = Peg A
Odredište = klin C
Pomoćnik = Peg B

Sada moramo premjestiti gornjih n-1 diskova iz izvora u pomoćnik.

Bilješka: Iako možemo premještati samo jedan po jedan disk, to razbija naš problem s problema s 3 diska na problem s 2 diska, što je rekurzivan poziv.

Korak 2) Budući da pozivamo rekurzivni poziv iz klina A, a odredište je klin B, koristit ćemo klin C kao pomoćnika.

Primijetite da smo ponovno na prvoj fazi za isti problem kule u Hanoju za dva diska.

Sada moramo premjestiti n-1 ili jedan disk od izvora do pomoćnika, pomicanjem najmanjeg diska od klina A do klina C.

U ovoj fazi:

Izvor = klin A
Odredište = klin B
Pomoćnik = klin C

Korak 3) Zatim, prema našem algoritmu, n-ti ili 2. disk treba prenijeti u odredište ili klin B.

U ovoj fazi:

Izvor = klin A
Odredište = klin B
Pomoćnik = klin C

Korak 4) Sada ćemo premjestiti n-1 diskove ili disk jedan od pomoćnika ili klina C do odredišta ili klina B prema trećoj fazi našeg algoritma.

U ovoj fazi:

Izvor = klin A
Odredište = klin B
Pomoćnik = klin C

Korak 5) Nakon dovršetka rekurzivnog poziva, vratit ćemo se na prethodnu postavku kada završi prva faza algoritma.

Korak 6) Sada, u drugoj fazi, premjestit ćemo naš izvor na naše odredište, a to je pomicanje diska 3 na klin C od klina A.

U ovoj fazi:

Izvor = klin A
Odredište = klin C
Pomoćnik = klin B

Korak 7) Sada to možemo vidjeti

d je premjestiti preostale diskove od pomoćnog (kolčić B) do odredišta (kolčić C). Koristit ćemo početni izvor ili klin A kao pomoć u ovom slučaju.

Korak 8) Kako ne možemo pomicati dva diska istovremeno, pozvat ćemo rekurzivni poziv za disk 1. Prema zadnjem koraku i našem algoritam, odredište u ovom koraku je klin A.

U ovoj fazi:

Izvor = klin B
Odredište = klin A
Pomoćnik = klin C

Korak 9) Naš rekurzivni poziv je sada završen. Zatim pomičemo disk 2 od izvora do odredišta.

U ovoj fazi:

Izvor = klin B
Odredište = klin C
Pomoćnik = klin A

Korak 10) Zatim premještamo naš preostali n-1 ili disk 1 od pomoćnika do odredišta.

U ovoj fazi:

Izvor = klin A
Odredište = klin C
Pomoćnik = klin B

Pseudo šifra za Hanojski toranj

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

Programski kod u 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;
}

Izlaz

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

Programski kod u 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')

Izlaz:

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

Složenost Hanojskog tornja

Ovo je vremenska i prostorna složenost Hanojskog tornja:

1) Vremenska složenost:

Ako se osvrnemo na naš algoritam, možemo vidjeti da dva puta uvodimo rekurzivni poziv za (n-1) diskove. Ti rekurzivni pozivi za (n-1) diskove mogu se rastaviti na druge ((n-1)-1) i tako dalje dok ne dobijemo samo jedan disk za pomicanje.

Za tri diska-

Disk 3 dvaput poziva rekurzivnu funkciju za disk dva.
Disk 2 dvaput poziva rekurzivnu funkciju za disk jedan.
Disk 1 može se kretati unutar konstantnog vremena i vremena za rješavanje za tri diska.

= 2*(vrijeme za rješavanje za dva diska) + konstantno vrijeme za pomicanje diska 3

= 2*(2*vrijeme za rješavanje za jedan disk + konstantno vrijeme za pomicanje diska 2) + konstantno vrijeme za pomicanje diska 3

= (2*2) (konstantno vrijeme za pomicanje diska 1) + 2*konstantno vrijeme za pomicanje diska 2 + konstantno vrijeme za pomicanje diska 3

Za n diskova, može se napisati kao –

(2^n-1* konstantno vrijeme za pomicanje diska 1 + 2^n-2 * konstantno vrijeme za pomicanje diska 2 + ….

Ova geometrijska progresija rezultirat će O(2^n-1) Ili O(2ⁿ), koji je eksponencijalan.

2) Složenost prostora

Prostorna složenost Hanojskog tornja je 0(n). To je zato što moramo pohraniti redoslijed ploča. Kada koristimo rekurziju, ona koristi stog. A maksimalna veličina hrpe može biti "n." Zbog toga kompleksnost prostora postaje O(n).

Možda ti se svidi: