Łamigłówka Wieże Hanoi w języku C++ [Algorytm]

Rozwiązując Łamigłówkę Wieże Hanoi, rozwijasz swoje umiejętności analityczne, logiczne myślenie, jak również zdolność do rozwiązywania problemów. Oczywiście jest to świetny sposób na poprawę swoich umiejętności programistycznych i wyzwanie dla początkujących koderów.

Co to jest Wieża Hanoi?

Wieża Hanoi to matematyczna łamigłówka, która składa się z trzech palików i pewnej, z góry określonej ilości dysków. Zadanie polega na przeniesieniu wszystkich dysków na inny pręt przy zachowaniu ustalonych zasad:

• Jednocześnie można przenosić tylko jeden dysk.
• Najwyższy dysk jedynie można przenieść z jednego stosu na szczyt innego stosu lub na pusty pręt.
• Większych dysków nie można umieszczać na mniejszych dyskach.

Zaczynasz grę posiadając kilka (im więcej, tym trudniej) krążków różnej średnicy nałożonych na pionowy palik. Krążki są ułożone w taki sposób, że nad danym krążkiem nie może się znajdować krążek większy, czyli na większy krążek jest nałożony mniejszy. Dodatkowo posiadasz dwa paliki. Zatem Twoim zadaniem jest przenieść wszystkie krążki z palika, na którym się znajdują, na inny pusty palik. Aby tego dokonać, trzeba wykorzystać trzeci palik. Zabawa się kończy po przeniesieniu wszystkich dysków na inny palik.

Podejście rekurencyjne

Zamysł polega na zastosowaniu podejścia rekurencyjnego do rozwiązania tego problemu. W związku z tym rozwiążemy przykładowy problem dla N = 3 (trzy krążki). Spójrz na animację rozwiązania takiej łamigłówki:

Zatem minimalna liczba ruchów potrzebnych do rozwiązania problemu Wieży Hanoi wynosi 2^N – 1, gdzie N to liczba dysków.

Opis kolejnych kroków dla łamigłówki z trzema dyskami:

• Przenieś dysk 1 z wieży A do wieży B.
• Przenieś dysk 2 z wieży A do wieży C.
• Przenieś dysk 1 z wieży B do wieży C.
• Przenieś dysk 3 z wieży A do wieży B.
• Przenieś dysk 1 z wieży C do wieży A.
• Przenieś Dysk 2 z wieży C do wieży B.
• Przenieś dysk 1 z wieży A do wieży B.

Teraz przejdźmy do praktyki, gdzie przedstawiam zapis algorytmu w języku C++ pozwalający na wyznaczenie kolejnych kroków przełożeń krążków, a następnie go objaśnię.

Listing programu „Łamigłówka Wieże Hanoi”:

#include <iostream>
using namespace std;
int n;

void hanoi(int z, int d, int ile)
{
  if (ile>1)
    {
      hanoi(z,6-z-d,ile-1);
      hanoi(z,d,1);
      hanoi(6-z-d,d,ile-1);
    }
    else
    {
      cout << z << " --> " << d << "\n";
    }
}

int main()
{
  cout << "Ile krazkow chcesz przeniesc?\n";
  cin >> n;
  hanoi(1,3,n);
}

Objaśnienie listingu:

Definiujemy procedurę hanoi, które jako parametry przekazujemy 3 liczby: numer palika, z którego przekładamy krążki, numer palika, na który przekładamy krążki oraz ilość przekładanych krążków. Pewnie zastanawia Cię, dlaczego definiujemy ilość przekładanych krążków, skoro można przekładać tylko po jednym krążku. Ale o tym za chwilę.

Zakładamy, że wszystkie krążki (ich ilość określamy podczas wykonywania programu) znajdują się na paliku 1, a mamy je przenieść na palik 3. Palik 2 służy nam do pomocy. Po wczytaniu liczby n określającej ilość krążków na paliku 1 wywołujemy procedurę hanoi:

hanoi(1,3,n)

Procedura ta przeniesie n krążków (czyli wszystkie) z palika 1 na palik 3. A jak? Bardzo prosto. Najpierw sprawdzana jest ilość krążków do przeniesienia. Jeśli wywołaliśmy procedurę podając ich ilość równą 1 to krążek zostanie po prostu przełożony (linijka 13). Jeśli zażądaliśmy od procedury przeniesienia większej ilości krążków będzie musiała to zrobić na raty. Najpierw na palik pomocniczy zostaną przeniesione wszystkie krążki oprócz ostatniego (linijka 9). Następnie ten, który pozostał (linijka 10). Ostatecznie należy przenieść krążki z palika pomocniczego na docelowy (linijka 11).

Przykładowo: jeśli chcemy przenieść 4 krążki z palika 1 na 3, to najpierw przenosimy 3 krążki z palika 1 na palik 2 (palik pomocniczy), a następnie przenosimy 4 krążek z 1 na 3 i na końcu przenosimy 3 krążki z palika pośredniego na 3. Przenoszenie na pośredni i z pośredniego na docelowy odbywa się analogicznie.

Za znalezienie numeru palika pośredniego (pomocniczego) odpowiada kod: 

6-z-d 

Litera „z” to numer palika, z którego chcemy przenieść krążki na krążek „d”, a więc jeśli przenosimy krążki z palika 1 na 2, to palik pośredni

6-1-2=3

to palik 3.

Zastosowania Wieży Hanoi w praktyce

• Komputerowe przechowywanie danych: Sekwencja ruchów w Wieży Hanoi służy do określenia optymalnego harmonogramu rotacji taśm z kopiami zapasowymi, zapewniając systematyczne nadpisywanie starszych kopii zapasowych.
• Robotyka: Roboty obsługujące ułożone w stos obiekty korzystają z zasad Wieży Hanoi, aby określić optymalną sekwencję ruchów, zapewniając, że większy obiekt nie zostanie umieszczony na mniejszym.
• Algorytmy komputerowe: Wieża Hanoi została bezpośrednio zaimplementowana do nauczania rekurencji, demonstrując, jak złożony problem można rozbić na prostsze, powtarzalne zadania.
• Produkcja: Na liniach montażowych, gdzie komponenty muszą być ułożone w stosy lub ułożone w określonej kolejności, zasada Wieży Hanoi dotycząca przenoszenia elementów bez umieszczania większego na mniejszym może kierować sekwencją operacji, aby uniknąć błędów i przeróbek.
• Telekomunikacja: W projektach sieci hierarchicznych podejście rekurencyjne Wieży Hanoi można wykorzystać jako model do optymalizacji sekwencji łączących węzłów lub przełączników, która zapewnia, że węzły o większej przepustowości (analogicznie do większych dysków) obsługują większy ruch, a węzły o mniejszej przepustowości (mniejsze dyski) obsługują mniej.
• Logistyka: W magazynowaniu, gdy produkty są przechowywane w pojemnikach lub regałach, zasada Wieży Hanoi może pomóc w rozmieszczeniu towarów w taki sposób, aby były one łatwo dostępne. Na przykład często używane elementy (analogicznie do mniejszych dysków) można umieścić w bardziej dostępnych lokalizacjach, podczas gdy rzadziej używane elementy (większe dyski) można umieścić głębiej lub wyżej.

Legenda Wieży Hanoi

Na koniec ciekawostka związana z tą jakże fascynującą zagadką logiczną, czyli popularna legenda. Według opowieści w indyjskim mieście Waranasi znajduje się świątynia zawierająca duże pomieszczenie, w którym znajdują się trzy zniszczone przez czas słupy. Otaczają go 64 złote dyski. Słuchając poleceń starożytnej przepowiedni, kapłani bramińscy od zarania dziejów poruszają tymi dyskami zgodnie z niezmiennymi regułami układanki Brahmy. Legenda głosi, że gdy kapłani zakończą swoje zadanie, to w tym momencie nastąpi koniec świata.

Jeśli legenda byłaby prawdziwa, to rozwiązanie łamigłówki z 64 dyskami wymagałoby 264 -1 ruchów, czyli 18 446 744 073 709 551 615 ruchów. Nawet gdyby co sekundę wykonywany był jeden ruch, jego ukończenie zajęłoby ponad 580 miliardów lat! Daje to wyobrażenie o wykładniczym wzroście związanym z rozwiązaniem zagadki Wieży Hanoi.

Oczywiście istnieje wiele wersji legendy. Niektórzy przedstawiają świątynię jako klasztor, a inni z kolei księży jako mnichów. Ludzie wspominają różne miejsca na świątynię, np. Hanoi w Wietnamie. Niektóre opowieści mówią, że wieża powstała na początku świata, podczas gdy inni twierdzą, że kapłani i mnisi mogą przenosić tylko jedną sztukę dziennie.

Dla zainteresowanych historią i genezą powstania łamigłówki Wieże Hanoi zapraszam do dodatkowej lektury tutaj.

Łamigłówka Wieże Hanoi: Podsumowanie

Rozwiązanie Łamigłówki Wieże Hanoi w języku C++ to wyzwanie, ale również świetna okazja do nauki i rozwijania umiejętności programistycznych. Dzięki temu prostemu przykładowi kodu możesz zacząć eksperymentować i zgłębiać tajniki programowania. Powodzenia w rozwiązywaniu łamigłówek i w rozwijaniu się jako programista!