Program hanoi.exe.

Opis programu “Wieże Hanoi”

Program, gra “Wieże Hanoi” jest komputerową adaptacją azjatyckiej legendy:

“W wielkiej świątyni Benares w Hanoi, pod kopułą, która zaznacza środek świata, znajduje się płytka z brązu, na której umocowane są trzy diamentowe igły, wysokie na łokieć i cienkie jak talia osy. Na jednej z tych igieł, w momencie stworzenia świata, Bóg umieścił 64 krążki ze szczerego złota. Największy z nich leży na płytce z brązu, a pozostałe jeden na drugim, idąc malejąco od największego do najmniejszego. Jest to wieża Brahma. Bez przerwy we dnie i w nocy kapłani przekładają krążki z jednej diamentowej igły na drugą, przestrzegając niewzruszonych praw Brahma. Prawa te chcą, aby kapłan na służbie brał tylko jeden krążek na raz i aby umieszczał go na jednej z igieł w ten sposób, by nigdy nie znalazł się pod nim krążek mniejszy. Wówczas, gdy 64 krążki zostaną przełożone z igły, na której umieścił je Bóg w momencie stworzenia świata, na jedną z dwóch pozostałych igieł, wieża, świątynia, bramini rozsypią się w proch i w jednym oka mgnieniu nastąpi koniec świata”.

Oczywiście, nie musimy przejmować się przepowiednią zawartą w tej legendzie, ponieważ, jak wykażemy później, czas potrzebny na przełożenie 64 krążków jest bardzo, bardzo długi.

Program “Wieże Hanoi” po uruchomieniu przedstawia 3 krążki ułożone na 1-szej igle - rys.1. Zadaniem gracza jest przełożyć te krążki na 3-cią igłę.

Rys.1. Plansza początkowa programu “Wieże Hanoi”.

Przekładanie krążków wykonujemy przy pomocy myszki. Bierzemy dany krążek, podnosimy go do góry, umieszczamy nad odpowiednią igłą i puszczamy go. Zwracam uwagę, aby nie przesuwać krążka w dół po igle, tylko puścić go gdy znajduje się nad igłą. Krążek sam opadnie na dół, zatrzymując się na najwyżej leżącym krążku. Należy pamiętać aby zachować zasadę, że można przekładać tylko krążki mniejsze na większe. Komputer zresztą nie pozwala zrobić inaczej.

Program umożliwia zmianę ilości krążków w zakresie 1 - 8. W tym celu należy myszką nacisnąć znak dla zwiększenia ilości krążków, lub nacisnąć znak dla zmniejszenia ilości krążków.

Program ma opcję automatycznego przenoszenia krążków. Aby z niej skorzystać należy najpierw nacisąć przycisk "Od nowa" a następnie nacisnąć przycisk “Automatycznie”. Wówczas komputer bardzo szybko przełoży wszystkie krążki z 1-szej igły na 3-cią.

Przekładanie ręczne nie jest trudne pod warunkiem, że odkryje się rekurencyjną zasadę przekładania. Odkrywanie zasady należy rozpocząć od mniejszej ilości krążków, najlepiej od jednego.

Jeśli mamy jeden krążek to bez problemu przenosimy go na 3-cią igłę wykonując 1 ruch.

Jeśli mamy dwa krążki to przenosimy najpierw 1-szy krążek na 2-gą igłę, traktując ją jako igłę roboczą, następnie 2-gi krążek na 3-cią igłę a na koniec 1-szy krążek z 2-giej igły na 3-cią. Wykonamy przy tym 3 ruchy.

Jeśli mamy do przełożenia trzy krążki to przenosimy najpierw dwa krążki na 2-gą igłę, tak jak to zrobiliśmy wyżej, wykorzystując tym razem jako roboczą 3-cią igłę (wykonamy 3 ruchy), następnie przenosimy 3-ci krążek na 3-cią igłę (1 ruch) a na koniec przenosimy dwa krążki z 2-giej igły na 3-cią, wykorzystując teraz jako roboczą igłę 1-szą (3 ruchy). Razem wykonamy 7 ruchów.

Ogólnie zasada przekładania krążków ma następującą rekurencyjną postać: Jeśli N=1 to przenosimy jeden krążek z 1-szej igły na 3-cią. Jeśli N>1 wtedy przenosimy najpierw N-1 krążków na 2-gą igłę, następnie krążek N-ty na 3-cią igłę i na koniec N-1 krążków z 2-ej igły na 3-cią. Łącznie wykonamy 2n -1 ruchów.

Widać więc, że przepowiednia zawarta w legendzie długo się nie spełni, ponieważ dla 64 krążków ilość ruchów wynosi 264 -1 i jest to olbrzymia, 19-cyfrowa liczba. Jeśli przyjąć, że każdy ruch trwa 1 sekundę to przełożenie 64 krążków będzie trwać setki miliardów lat. Nawiasem mówiąc legenda zacytowana na początku, została wymyślone przez francuskiego profesora matematyki E. Lucasa około 1883r.

Gra w wieże Hanoi ma ważne znaczenie w matematyce, ponieważ pokazuje, jak rekurencja w prosty sposób opisuje skomplikowany proces. (Prostotę opisu proszę jednak nie mylić z szybkością działania. Zazwyczaj procedury rekurencyjne działają dłużej niż procedury iteracyjne). Poniższy program wykonuje przekładanie krążków według opisanej wyżej procedury rekurencyjnej.

program Wieze_Hanoi;
uses crt;
const ilosc=3;
tw: array[1..3] of integer=(ilosc,0,0);
var n:integer;
t: array[1..3,1..ilosc] of integer;
procedure wypisz_stan;
begin
for n:=ilosc downTo 1 do writeLn(' ',t[1,n],' ',t[2,n],' ',t[3,n]);
writeLn; readLn;
end;
procedure przeloz_krazek(skad, dokad : integer);
begin
tw[dokad]:=tw[dokad]+1; t[dokad,tw[dokad]]:=t[skad,tw[skad]];
t[skad,tw[skad]]:=0; tw[skad]:=tw[skad]-1;
wypisz_stan;
end;
procedure przeloz_krazki(ile,skad,dokad,roboczy:integer);
begin
if ile=1 then przeloz_krazek(skad,dokad)
else begin
przeloz_krazki(ile-1,skad,roboczy,dokad);
przeloz_krazek(skad,dokad);
przeloz_krazki(ile-1,roboczy,dokad,skad)
end;
end;
begin
clrScr;
for n:=1 to ilosc do t[1,n]:=ilosc-n+1;
wypisz_stan;
przeloz_krazki(ilosc,1,3,2);
end.

Proszę porównać jak procedura przeloz_krazki zawarta w tym programie idealnie pasuje do sposobu przekładania krążków opisanym wcześniej.

Życzę powodzenia w przekładaniu krążków. Eugeniusz Jakubas

Program hanoi.exe.