Struktura danych i algorytmy - Wieża Hanoi

Wieża Hanoi to matematyczna łamigłówka, która składa się z trzech wież (kołków) i więcej niż jednego pierścienia, jak pokazano -

Pierścienie te mają różne rozmiary i są ułożone w kolejności rosnącej, tj. Mniejszy znajduje się nad większym. Istnieją inne warianty układanki, w których liczba dysków wzrasta, ale liczba wież pozostaje taka sama.

Zasady

Misja polega na przeniesieniu wszystkich dysków do innej wieży bez naruszania kolejności ułożenia. Kilka zasad, których należy przestrzegać w przypadku Wieży Hanoi, to:

W danym momencie między wieżami można przesuwać tylko jeden dysk.
Można usunąć tylko „górny” dysk.
Żaden duży dysk nie może usiąść na małym dysku.

Poniżej znajduje się animowana reprezentacja rozwiązywania zagadki Wieży Hanoi z trzema dyskami.

Puzzle Tower of Hanoi z n dysków można rozwiązać w minimum 2ⁿ−1kroki. Ta prezentacja pokazuje, że zajęła się zagadka z 3 dyskami2³ - 1 = 7 kroki.

Algorytm

Aby napisać algorytm dla Wieży Hanoi, najpierw musimy nauczyć się rozwiązać ten problem przy mniejszej liczbie dysków, powiedzmy → 1 lub 2. Trzy wieże oznaczamy nazwą, source, destination i aux(tylko w celu ułatwienia przenoszenia dysków). Jeśli mamy tylko jeden dysk, można go łatwo przenieść ze źródła na docelowy peg.

Jeśli mamy 2 dyski -

Najpierw przenosimy mniejszy (górny) dysk na kołek aux.
Następnie przenosimy większy (dolny) dysk na kołek docelowy.
I na koniec przenosimy mniejszy dysk z aux na docelowy peg.

Więc teraz jesteśmy w stanie zaprojektować algorytm dla Tower of Hanoi z więcej niż dwoma dyskami. Dzielimy stos dysków na dwie części. Największy dysk (n- ^ty dysk) znajduje się w jednej części, a wszystkie inne (n-1) dyski znajdują się w drugiej części.

Naszym ostatecznym celem jest przeniesienie dysku nze źródła do miejsca docelowego, a następnie umieść na nim wszystkie inne (n1) dyski. Możemy sobie wyobrazić, że zastosujemy to samo w sposób rekurencyjny dla wszystkich podanych zestawów dysków.

Kroki, które należy wykonać to -

Step 1 − Move n-1 disks from source to aux
Step 2 − Move n^th disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Algorytm rekurencyjny dla Tower of Hanoi można sterować następująco:

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Aby sprawdzić implementację w programowaniu w C, kliknij tutaj .