Algoritmus Hanojské věže: Python, C++ Kód

Co je Hanojská věž?

Hanojská věž je matematický hlavolam sestávající ze tří tyčí a mnoha disků umístěných přes sebe. Je také známá jako věž Brahma nebo Lucasova věž, jak ji představil francouzský matematik Edouard Lucas již v roce 1883. Tato hádanka je založena na legendách o pohybu zlatých kotoučů mezi třemi tyčemi.

Toto puzzle má tři tyče a proměnný počet naskládaných disků. Tyto tyče jsou navrženy jako cyklické věže. Takže větší disky o průměru jsou naskládány na spodní straně a menší disky jsou naskládány nahoře.

Zpočátku dostáváme tři kolíky nebo tyče. A jeden z nich (A, zobrazený v příkladu) má všechny disky naskládané. Naším cílem je přesunout celý stoh disků z jedné tyče (A) na druhou (C) při dodržení určitých specifických pravidel.

Zde je počáteční nastavení hádanky -

A to je konečný cíl -

Pravidla Hanojské věže

Zde jsou některá základní pravidla pro Hanojskou věž:

Počáteční stav této hádanky, všechny disky budou naskládány do tyče jedna.
Konečný stav je, že všechny disky z tyče jedna budou naskládány na tyč dvě nebo tyč tři.
Kdykoli můžeme přesunout na disk z jedné tyče na druhou.
Z tyče můžeme přesunout pouze nejhořejší kotouč.
Disk nelze umístit přes jiný disk, který je menší.

Původní legenda byla o přesunu 64 disků. Kněží mohli pohybovat po jednom disku podle pravidel. Podle legendy existovalo proroctví, že svět skončí, pokud se jim podaří tento čin dokončit. V sekci časové složitosti si ukážeme, že nastavení Hanojské věže na n disků by stálo 2^n – 1 tah.

Pokud by tedy kněží mohli vyžadovat 1 sekundu na přesunutí disků, celkový čas, který by potřebovali k vyřešení hádanky, by byl 2^64 – 1 sekunda nebo 584,942,417,356 26 7 15 let, XNUMX dní, XNUMX hodin a XNUMX sekund.

Algoritmus pro Hanojskou věž

Jedním z obecných způsobů, jak vyřešit Hanojskou věž, je rekurzivní algoritmus. Nejprve se musíme rozhodnout pro dva pruty nebo kolíky jako zdroj a cíl a náhradní kolík by byl pomocný nebo pomocník.

Zde jsou kroky k vyřešení hádanky Hanojské věže:

Přesuňte horních n-1 disků ze zdrojového pegu na pomocný kolík.
Poté přesuňte n-tý disk ze zdrojového pegu do cílového pegu.
Nakonec přesuňte zbývajících n-1 disků z pomocného pegu na cílový kolík.

Pozor: Pokud máme jeden disk, můžeme jej přímo přesunout ze zdroje do cíle.

Jak vyřešit hádanku Hanojská věž

Pojďme si ilustrovat algoritmus pro tři disky a uvažujme peg A jako zdroj, peg B jako pomocník a peg C jako cíl

Krok 1) Zpočátku budou všechny disky naskládány na kolík A.

V tomto stádiu:

Zdroj = Peg A
Cíl = Peg C
Pomocník = Peg B

Nyní potřebujeme přesunout horních n-1 disků ze zdroje do pomocníka.

Poznámka: Přestože můžeme přesunout pouze jeden disk najednou, přeruší to náš problém z problému se 3 disky na problém se 2 disky, což je rekurzivní volání.

Krok 2) Protože voláme rekurzivní volání z pegu A a cílem je peg B, použijeme peg C jako pomocníka.

Všimněte si, že jsme opět v první fázi stejného problému Hanojské věže pro dva disky.

Nyní potřebujeme přesunout n-1 nebo jeden disk ze zdroje na pomocníka a přesunout nejmenší disk z kolíku A na kolík C.

V tomto stádiu:

Zdroj = kolík A
Cíl = kolík B
Pomocník = kolík C

Krok 3) Potom by podle našeho algoritmu měly být potřeby n-tého nebo druhého disku přeneseny do cíle nebo kolíku B.

V tomto stádiu:

Zdroj = kolík A
Cíl = kolík B
Pomocník = kolík C

Krok 4) Nyní přesuneme n-1 disků nebo disk jeden z pomocníka nebo kolíku C do cíle nebo kolíku B podle třetí fáze našeho algoritmu.

V tomto stádiu:

Zdroj = kolík A
Cíl = kolík B
Pomocník = kolík C

Krok 5) Po dokončení rekurzivního volání se vrátíme k našemu předchozímu nastavení při první fázi algoritmu.

Krok 6) Nyní, ve druhé fázi, přesuneme náš zdroj do našeho cíle, což je přesun disku 3 na kolík C z kolíku A.

V tomto stádiu:

Zdroj = kolík A
Cíl = kolík C
Pomocník = kolík B

Krok 7) Nyní to můžeme vidět

d je přesunout zbývající disky z pomocného (peg B) do cíle (peg C). Jako pomocníka v tomto případě použijeme počáteční zdroj nebo peg A.

Krok 8) Protože nemůžeme přesunout dva disky současně, zavoláme rekurzivní volání pro disk 1. Podle posledního kroku a našeho algoritmus, cílem v tomto kroku je kolík A.

V tomto stádiu:

Zdroj = kolíček B
Cíl = kolík A
Pomocník = kolík C

Krok 9) Náš rekurzivní hovor je nyní dokončen. Poté přesuneme disk 2 ze zdroje na místo určení.

V tomto stádiu:

Zdroj = kolíček B
Cíl = kolík C
Pomocník = kolík A

Krok 10) Potom přesuneme naše zbývající n-1 nebo disk 1 z pomocníka do cíle.

V tomto stádiu:

Zdroj = kolík A
Cíl = kolík C
Pomocník = kolík B

Pseudokód pro Hanojskou věž

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

Kód programu v 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ýstup

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

Kód programu v 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ýstup:

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žitost věže Hanoi

Zde je časová a prostorová složitost Hanojské věže:

1) Časová složitost:

Když se podíváme zpět na náš algoritmus, můžeme vidět, že zavádíme rekurzivní volání pro (n-1) disky dvakrát. Tato rekurzivní volání (n-1) disků lze rozdělit na další ((n-1)-1) a tak dále, dokud nedostaneme k pohybu pouze jeden disk.

Na tři disky -

Disk 3 volá rekurzivní funkci pro disk dva dvakrát.
Disk 2 volá rekurzivní funkci pro disk jedna dvakrát.
Disk 1 se může pohybovat v rámci konstantního času a času pro tři disky.

= 2*(Čas na řešení pro dva disky) + konstanta Čas na přesunutí disku 3

= 2*(2*čas na vyřešení pro jeden disk + konstanta Čas na přesunutí disku 2) + konstanta Čas na přesunutí disku 3

= (2*2) (konstantní čas pro přesun disku 1) + 2*konstantní čas pro přesun disku 2 + konstantní čas pro přesun disku 3

Pro n disků to lze zapsat jako –

(2^n-1* konstantní čas na pohyb disku 1 + 2^n-2 * konstantní čas pro pohyb disku 2 + ….

Výsledkem tohoto geometrického postupu bude O(2^n-1), Nebo O(2ⁿ), který je exponenciální.

2) Prostorová složitost

Prostorová složitost Hanojské věže je 0(n). Je to proto, že musíme uložit pořadí desek. Když používáme rekurzi, používá zásobník. A maximální velikost zásobníku může být „n“. Proto se prostorová složitost stává O(n).

Máš rád:

Co je Hanojská věž?

Pravidla Hanojské věže

Algoritmus pro Hanojskou věž

Jak vyřešit hádanku Hanojská věž

SOUVISEJÍCÍ ČLÁNKY

Pseudokód pro Hanojskou věž

Kód programu v C++

Kód programu v Python

Složitost věže Hanoi