W problemie wież z Hanoi mamy trzy pręty oznaczone A, B i C oraz
n okrągłych krążków
o średnicach odpowiednio 1, 2, …,
n. Na początku wszystkie krążki nałożone są na pręt A,
w kolejności od największego do najmniejszego (największy na dole, najmniejszy na górze).
Układ ten (dla
n = 3) został przedstawiony na poniższym rysunku.
Zgodnie z regułami problemu krążki można przekładać między prętami. W jednym ruchu
możliwe jest przełożenie krążka znajdującego się na szczycie jednego z prętów na szczyt innego pręta, pod warunkiem że nie kładziemy przekładanego krążka na krążek mniejszy od
niego. Na przykład na poniższym rysunku krążek 2 możemy przełożyć z pręta A na pręt C,
natomiast niemożliwe jest przełożenie go na pręt B.
Zadanie polega na przełożeniu wszystkich krążków z pręta A na pręt B, przy czym można
korzystać z pomocniczego pręta C. Na poniższym rysunku przedstawiono efekt końcowy.
Problem wież z Hanoi można rozwiązać za pomocą algorytmu rekurencyjnego. W algorytmie
pręty: startowy, docelowy i pomocniczy, podane są jako parametry wejściowe, odpowiednio
x,
y i
z. Algorytm polega na tym, że najpierw przenosimy
n – 1 krążków na pręt pomocniczy
z, potem największy krążek zostaje przeniesiony na pręt docelowy
y, a na koniec
n – 1 krążków zostaje przeniesionych z pręta pomocniczego z na pręt docelowy
y, przy czym pręt startowy
x traktowany jest jako pomocniczy.
Algorytm
Specyfikacja
Dane:
n — liczba całkowita dodatnia,
x — nazwa pręta startowego,
y — nazwa pręta docelowego,
z — nazwa pręta pomocniczego.
Wynik:
ciąg ruchów opisujący rozwiązanie problemu wież z Hanoi z n krążkami, w którym na
początku wszystkie krążki znajdują się na pręcie x, a na końcu mają znaleźć się na
pręcie y, zaś pomocniczym prętem jest z.
Uwaga: Pojedynczy ruch zapisujemy za pomocą znaku =>. Na przykład C => B oznacza
przeniesienie krążka z pręta C na pręt B.
funkcja wieże(
n,
x,
y,
z)
jeżeli n = 1
wypisz x =>
y w przeciwnym razie wieże(
n – 1,
x,
z,
y)
wypisz x =>
y wieże(
n – 1,
z,
y,
x)
Przykład
Wywołanie
wieże(2, A, B, C) spowoduje dwa wywołania rekurencyjne:
wieże(1, A, C, B)
oraz
wieże(1, C, B, A). Ciąg ruchów utworzony przez
wieże(2, A, B, C) ma postać:
A => C, A => B, C => B,
gdzie podkreślone ruchy są utworzone przez rekurencyjne wywołania
wieże(1, A, C, B) oraz
wieże(1, C, B, A).
poleca:
Studentnews.pl