Wieże Hanoi

Zadanie dotyczy łamigłówki, której celem jest przeniesienie krążków z drążka lewego, na drążek prawy. Krążki są początkowo umieszczone na drążku A w taki sposób, że tylko krążek mniejszy może zostać umieszczony na krążku większym (Rys.1 ).

Rys. 1 Wieże Hanoi.

Algorytm rozwiązania problemu

Wieże Hanoi można łatwo rozwiązać za pomocą prostego algorytmu rekurencyjnego lub iteracyjnego.

•

Oznaczmy kolejne słupki literami A, B i C.

•

Niech n będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek C posługując się słupkiem B jako buforem.

Rozwiązanie rekurencyjne

Algorytm rekurencyjny składa się z następujących kroków: 1. przenieś (rekurencyjnie) n-1 krążków ze słupka A na słupek B posługując się słupkiem C, 2. przenieś jeden krążek ze słupka A na słupek C, 3. przenieś (rekurencyjnie) n-1 krążków ze słupka B na słupek C posługując się słupkiem A

Przykładowa implementacja w języku Prolog hanoi2(N) :- move(N,lewy,srodkowym,prawy).

move(1,L,_,R) :- out(L,R).

move(N,L,M,R) :-

N1 is N-1,

move(N1,L,R,M),

out(L,R),

move(N1,M,L,R).

out(X,Y) :-

write('Przenies '),

write(X),write(' krazek'),

write(' na '),

write(Y), write(' slupek'),nl.

hanoi:-write('Wywolanie: hanoi2(ilosc_krazkow)').

hanoi(X):-write('Wywolanie: hanoi2('),write(X),write(')'),nl.