Łamigłówka Wieże Hanoi
Na pozycji początkowej znajduje się n krążków, przy czym żaden krążek
większy nie leży na mniejszym:
HH
HHHH
HHHHHHHH
HHHHHHHHHHHH
HHHHHHHHHHHHHHHH
====================== ==================== ==================
Pozycja początkowa Pozycja pośrednia Pozycja końcowa
Przenieść krążki z pozycji początkowej na pozycję końcową z
wykorzystaniem pozycji pośredniej tak, by:
a) każdorazowo przenosić tylko pojedynczy krążek;
b) nigdy nie kłaść krążka większego na mniejszy.
Łamigłówkę tą rozwiązuje następująca rekurencja:
Aby przenieść n krążków z pozycji początkowej na pozycję końcową,
należy:
1. Przenieść n-1 krążków z pozycji początkowej na pozycję pośrednią
z wykorzystaniem pozycji końcowej.
2. Przenieść ostatni krążek z pozycji początkowej na pozycję końcową.
Teraz jesteśmy w podobnej sytuacji jak przed krokiem 1, z tą różnicą
że mamy przenieść n-1 krążków z pozycji pośredniej na pozycję końcową:
obecność największego krążka na pozycji końcowej nie ma bowiem znaczenia
dla dalszego przebiegu rozwiązania.
Wyszukiwarka
Podobne podstrony:
hanoihtml hanoihtml hanoihanoi solverfibonacci,hanoiwięcej podobnych podstron