Zasady gry są następujące:
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. Dodatkowo posiadasz dwa paliki. Twoim zadaniem jest przenieść wszystkie krążki z palika, na którym się znajdują na inny palik wykorzystując do tego palik trzeci. Należy jednak pamiętać o tym, że na mniejszy krążek nie można położyć większego oraz o tym, że krążki można przekładać jedynie po jednej sztuce.
Najpierw przedstawię algorytm pozwalający na wyznaczenie kolejnych przełożeń krążków, a następnie go objaśnię.
#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);}
Definiujemy procedurę hanoi, które jako parametry przekazujemy 3 liczby: numer palika, z którego przekładamy krążki, numer krążka, 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 zarządzaliś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). Ostatnim krokiem jest przeniesienie krążków z palika pomocniczego na docelowy (linijka 11).
Przykładowo: chcemy przenieść 4 krążki z palika 1 na 3. Najpierw przenosimy 3 krążki z palika 1 na palik 2 (palik pomocniczy), 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.