Hanojská věž - Algoritmus a implementace v Javě

Obsah

Hanojská věž – Algoritmus a jeho realizace v Javě

Úvod

Hanojská věž, známá také jako Věž z Hanoje, je populární hlavolam, jehož základem jsou tři kolíky a několik disků odlišné velikosti. Úkolem je přesunout všechny disky z jednoho kolíku na druhý, přičemž platí specifická pravidla. Tato hra není jen zdrojem zábavy, ale i výborným příkladem rekurzivního uvažování v programování. V tomto článku si ukážeme, jak vytvořit implementaci Hanojské věže v programovacím jazyce Java.

Algoritmus

Algoritmus Hanojské věže se opírá o rekurzivní princip. Postup je definován takto:

Je-li počet disků roven jedné, přesuneme tento disk z počátečního kolíku na cílový.
V opačném případě:
- Přesuneme n-1 disků z počátečního kolíku na pomocný kolík.
- Přesuneme zbývající disk z počátečního kolíku na cílový kolík.
- Přesuneme n-1 disků z pomocného kolíku na cílový kolík.

Realizace v Javě

Níže uvedený Java kód představuje implementaci algoritmu Hanojské věže:

    
public class HanojskaVez {

    public static void main(String[] args) {
        int pocetDisku = 3; // Nastavte požadovaný počet disků
        prelozVez(pocetDisku, 1, 2, 3);
    }

    public static void prelozVez(int pocetDisku, int zdrojovyKolik, int pomocnyKolik, int cilovyKolik) {
        if (pocetDisku == 1) {
            presunDisk(zdrojovyKolik, cilovyKolik);
        } else {
            prelozVez(pocetDisku - 1, zdrojovyKolik, cilovyKolik, pomocnyKolik);
            presunDisk(zdrojovyKolik, cilovyKolik);
            prelozVez(pocetDisku - 1, pomocnyKolik, zdrojovyKolik, cilovyKolik);
        }
    }

    public static void presunDisk(int zdrojovyKolik, int cilovyKolik) {
        System.out.println("Přesun disk z kolíku " + zdrojovyKolik + " na kolík " + cilovyKolik);
    }
}

Klíčové koncepty

Disk: Kruhový objekt, který se umisťuje na kolíky.

Kolík: Vertikální sloupek, na který se disky umisťují.

Výchozí kolík: Kolík, z něhož se disky přesouvají.

Cílový kolík: Kolík, kam se disky přesouvají.

Pomocný kolík: Kolík, který se využívá pro dočasné odkládání disků během přesunu.

Část 1: Základní metoda

Základní metoda main slouží k nastavení počátečního stavu hry a spuštění rekurzivní metody prelozVez.

Část 2: Rekurzivní procedura

Metoda prelozVez implementuje rekurzivní algoritmus pro řešení Hanojské věže. Volá sama sebe s modifikovanými parametry, čímž docílí postupného přesouvání disků na určený cílový kolík.

Část 3: Vylepšení kódu

Kód je možné vylepšit pomocí optimalizační techniky známé jako „tail recursion“. To znamená, že rekurzivní volání je posledním příkazem v rámci metody. Díky tomu může kompilátor Java provést optimalizaci kódu a vyhnout se nadměrnému využívání zásobníkového prostoru.

Praktické příklady

Zkuste pomocí algoritmu Hanojské věže vyřešit následující zadání:

Přesuňte 4 disky z prvního kolíku na třetí kolík.
Přesuňte 5 disků z třetího kolíku na první kolík.
Přesuňte 7 disků z druhého kolíku na první kolík.

Část 4: Alternativní provedení hry

Existují i další varianty Hanojské věže, například:

Přesun disků tak, aby se vždy přesunul největší možný disk.
Využití více než tří kolíků.
Použití disků s různými tvary či barvami.

Část 5: Jak hrát Hanojskou věž

Hanojskou věž lze hrát jak manuálně, tak s pomocí softwarových simulací. Zde jsou základní pravidla hry:

Disky se přesouvají po jednom.
Nikdy se nesmí umístit větší disk na menší.
Používají se pouze tři kolíky.

Část 6: Obtížnost hry

Náročnost Hanojské věže je přímo závislá na počtu disků. Čím více disků, tím větší počet kroků je potřeba k vyřešení hlavolamu.

Závěrem

Hanojská věž je poutavý logický hlavolam, který rozvíjí strategické myšlení a podporuje pochopení principu rekurze. Implementací této hry v jazyce Java můžeme lépe porozumět jejímu algoritmu a funkcionalitě. Doufáme, že tento článek byl pro vás přínosný a pomůže vám k hlubšímu pochopení a ocenění Hanojské věže.

Časté otázky

1. Jaká je časová složitost algoritmu Hanojské věže?
O(2ⁿ), kde n je počet disků.

2. Je možné použít více než tři kolíky?
Ano, existují varianty hry s větším počtem kolíků.

3. Existují nějaké specifické strategie pro hru Hanojská věž?
Ano, jednou z doporučených strategií je vždy přesouvat největší možný disk.

4. Jaký je rekord v počtu kroků pro Hanojskou věž?
64 kroků pro 16 disků.

5. Jaká je nejefektivnější implementace Hanojské věže v Javě?
Rekurzivní implementace s optimalizací tail recursion.

6. Jaká je role pomocného kolíku v Hanojské věži?
Umožňuje dočasné odkládání disků, aby bylo možné přesunout jiné disky.

7. Jaký je historický původ Hanojské věže?
Legenda praví, že hru vymyslel hinduistický mnich okolo roku 100 př. n. l.

8. Má Hanojská věž nějaké praktické využití?
Používá se při studiu algoritmů, v oblasti umělé inteligence a při řešení problémů.