Vissza
Labor 9, haladóknak
N rúdas Hanoi tornyai
Adott n rúd. Az első x1 rúdra
különböző átmérőjű korongok vannak
felhúzva, méretük szerint csökkenő sorrendben,
legalul a legnagyobb átmérőjű korong. Írjunk
programot, mely megadja a korongok áthelyezési
sorrendjét az x1
rúdról az utolsó
xn
rúdra figyelembe véve a következő szabályokat:
- egy lépésben egy korongot lehet elmozdítani
- kisebb korongra nem helyezhető nagyobb korong.
Az algoritmus a következő lépésekből áll:
- költöztessük el a felső k (1<=k<n)
darab korongot egy másik rúdra,
- a maradék n-k
korongot költöztessük el a célrúdra,
felhasználva a maradék r-1
rúdat,
- az 1. lépésben elköltoztett k
darab korongot költöztessük át a
célrúdra.
A k optimális
értékének a meghatározása
érdekében a T(n,r) = 2*T(k,r)
+ T(n-k,r-1) minimális kell legyen.