Hanojská věž – Algoritmus a implementace v Javě
Úvod | Algoritmus | Implementace v Javě | Základní pojmy | Část 1: Hlavní metoda | Část 2: Rekurzivní metoda | Úkolové příklady | Část 3: Optimalizace kódu| Závěr | Část 4: Další varianty hry | | | FAQ
Table of Contents
Úvod
Hanojská věž je klasická logická hra, která se skládá ze tří tyčí a několika disků různých velikostí. Cílem hry je přesunout všechny disky z jedné tyče na druhou, a to podle určitých pravidel. Hanojská věž je nejen zábavnou hrou, ale také skvělou ukázkou rekurzivního myšlení v programování. V tomto článku si ukážeme, jak napsat implementaci Hanojské věže v jazyce Java.
Algoritmus
Algoritmus Hanojské věže je založen na principu rekurze. Hra se skládá z následujících kroků:
* Pokud je počet disků roven 1, přesuňte jej z výchozí tyče na cílovou tyči.
* Jinak:
* Přesuňte n-1 disků z výchozí tyče na pomocnou tyč.
* Přesuňte poslední disk z výchozí tyče na cílovou tyč.
* Přesuňte n-1 disků z pomocné tyče na cílovou tyč.
Implementace v Javě
Následující kód Java implementuje algoritmus Hanojské věže:
java
public class HanojskaVez {
public static void main(String[] args) {
int pocetDisku = 3; // Změňte na požadovaný počet disků
presunoutVez(pocetDisku, 1, 2, 3);
}
public static void presunoutVez(int pocetDisku, int vychoziTyc, int pomocnaTyc, int cilovaTyc) {
if (pocetDisku == 1) {
presunoutDisk(vychoziTyc, cilovaTyc);
} else {
presunoutVez(pocetDisku - 1, vychoziTyc, cilovaTyc, pomocnaTyc);
presunoutDisk(vychoziTyc, cilovaTyc);
presunoutVez(pocetDisku - 1, pomocnaTyc, vychoziTyc, cilovaTyc);
}
}
public static void presunoutDisk(int vychoziTyc, int cilovaTyc) {
System.out.println("Presunout disk z tyče " + vychoziTyc + " na tyč " + cilovaTyc);
}
}
Základní pojmy
Disk: Kruhový objekt, který se umísťuje na tyče.
Tyč: Vertikální sloupek, na který se umisťují disky.
Výchozí tyč: Tyč, ze které se disky přesouvají.
Cílová tyč: Tyč, na kterou se disky přesouvají.
Pomocná tyč: Tyč, která se používá jako mezičlánek při přesouvání disků.
Část 1: Hlavní metoda
Hlavní metoda main nastavuje počáteční stav hry a inicializuje rekurzivní volání metody presunoutVez.
Část 2: Rekurzivní metoda
Metoda presunoutVez implementuje rekurzivní algoritmus Hanojské věže. Volají se sama sebe s různými parametry a postupně přesouvají disky na cílovou tyč.
Část 3: Optimalizace kódu
Kód lze optimalizovat pomocí techniky známé jako tail rekurze. To znamená, že rekurzivní volání je posledním příkazem v metodě. Díky tomu překladač Java může optimalizovat kód a odstranit potřebu zásobníku volání.
Úkolové příklady
Vyřešte následující úlohy s pomocí algoritmu Hanojské věže:
* Přesuňte 4 disky z první tyče na třetí tyč.
* Přesuňte 5 disků z třetí tyče na první tyč.
* Přesuňte 7 disků z druhé tyče na první tyč.
Část 4: Další varianty hry
Existují i další varianty Hanojské věže, například:
* Přesuňte disky tak, aby se vždy přesunul největší možný disk.
* Použijte více než tři tyče.
* Použijte disky různých tvarů nebo barev.
Část 5: Jak hrát Hanojskou věž
Hanojskou věž můžete hrát ručně nebo pomocí softwarového simulátoru. Zde jsou základní pravidla hry:
* Přesouvejte disky jeden po druhém.
* Nikdy nepokládejte větší disk na menší.
* Používejte pouze tři tyče.
Část 6: Obtížnost hry
Obtížnost Hanojské věže závisí na počtu disků. Čím více disků, tím větší je počet tahů potřebných k vyřešení hry.
Závěr
Hanojská věž je skvělá logická hra, která vyžaduje strategické myšlení a pochopení rekurze. Implementace hry v Javě nám umožňuje lépe porozumět algoritmu a jeho funkčnosti. Doufáme, že jste si tento článek užili a že vám pomůže k lepšímu pochopení a ocenění Hanojské věže.
FAQ
1. Jaká je složitost algoritmu Hanojské věže?
O(2n), kde n je počet disků.
2. Můžete použít více než tři tyče?
Ano, existují varianty hry s více tyčemi.
3. Existují nějaké speciální strategie pro hru Hanojská věž?
Ano, jednou ze strategií je přesouvat vždy největší možný disk.
4. Jaký je rekord v počtu tahů pro Hanojskou věž?
64 tahů pro 16 disků.
5. Jaká je nejlepší implementace Hanojské věže v Javě?
Rekurzivní implementace s tail rekurzí.
6. Jaký je účel pomocné tyče v Hanojské věži?
Umožňuje uložit dočasně disky, aby bylo možné přesunout jiné disky.
7. Jaký je historický původ Hanojské věže?
Podle legendy postavil tuto hru hindský mnich kolem roku 100 př. n. l.
8. Má Hanojská věž nějaké praktické využití?
Byla použita ve studiu algoritmů, umělé inteligence a řešení problémů.