Nejprve stručně shrneme základní pravidla řešení Hanojské věže: Hlavolam se skládá ze tří kolíků (věží). Na začátku je na jednom z nich nasazeno několik kotoučů různých poloměrů, seřazených od největšího (vespod) po nejmenší (nahoře). Úkolem řešitele je přemístit všechny kotouče na druhou věž (třetí přitom využije jako pomocnou pro dočasné odkládání) podle následujících pravidel:
- V jednom tahu lze přemístit jen jeden kotouč.
- Jeden tah sestává z vzetí vrchního kotouče z některé věže a jeho položení na vrchol jiné věže.
- Je zakázáno položit větší kotouč na menší.
Jednoduché řešení Hanojské věže:
Střídavě se přesunuje nejmenší kotouč a jiný kotouč než nejmenší. Přesunuje-li se nejmenší kotouč, pak se vždy přesune o jednu věž dál ve stále stejném směru, a to doprava při celkovém sudém počtu kotoučů a doleva při lichém (předpokládáme, že věže stojí v řadě vedle sebe, počáteční je nejvíce vlevo a cílová nejvíce vpravo). Je-li již nejmenší kotouč na poslední věži v tomto směru, přesune se na věž na protějším konci. Má-li být přesunut jiný kotouč než nejmenší, je to možné provést vždy jen jediným způsobem. Tímto způsobem lze hlavolam vyřešit na nejmenší možný počet tahů.
Rekurzívní řešení Hanojské věže
Řešení pomocí rekurze vychází z úvahy, že řešení musí obsahovat nejméně jeden tah, v němž je přesunut největší kotouč. Ten však lze přesunout jen tehdy, jsou-li všechny ostatní kotouče nasazeny na třetí věži. Označme počet kotoučů n. Nejprve tedy přesuneme n–1 kotoučů (všechny kromě největšího) na odkládací věž, pak přesuneme největší kotouč z počáteční věže na cílovou a nakonec přesuneme n–1 kotoučů z odkládací věže na cílovou. Přesun n–1 kotoučů ovšem můžeme vykonat pomocí rekurzívního volání tohoto algoritmu pro n–1 kotoučů, protože největší kotouč nám přitom nevadí (na něj můžeme položit jakýkoli jiný, takže můžeme postupovat, jako by nebyl). Přesný postup je tedy následující:
- Je-li n>1, pak rekurzívním voláním této procedury přesuneme n–1 kotoučů (tj. všechny kromě největšího) z počáteční věže na odkládací.
- Přesuneme největší kotouč z počáteční věže na cílovou.
- Je-li n>1, pak rekurzívním voláním této procedury přesuneme n–1 kotoučů z odkládací věže na cílovou.
Z rekurzívního řešení lze dokázat matematickou indukcí, že pro n kotoučů potřebujeme 2n–1 tahů:
- Pro n=1 stačí jediný tah.
- Předpokládejme, že pro n–1 kotoučů potřebujeme 2n–1–1 tahů. Pak pro n kotoučů potřebujeme 2n–1–1 tahů pro bod 1, jediný tah pro bod 2 a 2n–1–1 tahů pro bod 3, tedy celkem 2n–1–1+1+2n–1–1 = 2n–1 tahů.
Jak vás tento hlavolam zaujal?
Celkové hodnocení uživateli 4 / 5. Celkem hodnotilo 10
