Algoritmus Hanojské věže: Python, C++ Code

⚡ Chytré shrnutí

Algoritmus Hanojské věže je klasická rekurzivní hádanka, která přesouvá hromádku disků mezi třemi kolíky, aniž by umístila větší disk na menší, což jasně ilustruje princip rozděl a panuj.

🗼 Příprava hádanky: Tři kolíky a n disků naskládaných v klesající velikosti na zdrojovém kolíku, čekající na přesun do cílového kolíku pomocí pomocného kolíku.
📜 Pravidla: Vždy se pohybuje pouze jeden disk, pohybovat se může pouze horní disk libovolného kolíku a větší disk nemůže spočívat na menším disku.
🔁 Rekurzivní myšlenka: Přesuňte n-1 disků na pomocný kolík, přesuňte největší disk na cílový kolík a poté přesuňte n-1 disků z pomocného kolíku do cílového.
⏱️ Časová složitost: Řešení n disků vyžaduje 2^n – 1 tahů, což dává exponenciální časovou složitost O(2^n), která velmi rychle roste s rostoucím n.
🧠 Prostorová složitost: Rekurzní zásobník pojme až n snímků najednou, takže prostorová složitost rekurzivního řešení je O(n).
🛠️ Aplikace: Výuka rekurze, schémat rotace záloh, přesunu dat na základě zásobníku, robotického sekvenování a pochopení návrhu algoritmů typu „rozděl a panuj“.

Přečíst více

Co je Hanojská věž?

Hanojská věž je matematická hádanka skládající se ze tří tyčí a hromádky disků zmenšující se velikosti umístěných na sobě. Je také známá jako Brahmova věž nebo Lucasova věž, protože ji v roce 1883 představil francouzský matematik Édouard Lucas. Hádanka je založena na legendách o přesouvání zlatých disků mezi třemi tyčemi.

Tato skládačka má tři tyče a proměnlivý počet naskládaných disků. Tyče jsou uspořádány jako cyklické věže, takže větší disky jsou naskládané dole a menší disky jsou naskládané nahoře.

Zpočátku máme tři kolíky nebo tyče. Na jednom z nich (v příkladu kolík A) jsou naskládané všechny disky. Cílem je přesunout celou hromádku z jedné tyče (A) na druhou (C) a přitom dodržet několik specifických pravidel.

Zde je počáteční nastavení skládačky:

Problém Hanojské věže

A toto je konečný cíl:

Pravidla Hanojské věže

Zde jsou základní pravidla pro Hanojskou věž:

V počátečním stavu skládačky jsou všechny disky naskládány na tyči jedna.
V konečném stavu jsou všechny disky z tyče jedna naskládány na tyči dva nebo tyči tři.
V daném okamžiku se z jedné tyče na druhou může pohybovat pouze jeden disk.
Pohybovat lze pouze nejvyšším diskem na tyči.
Disk nelze umístit na menší disk.

Původní legenda vyprávěla o pohybu 64 disků. Kněží mohli podle pravidel pohybovat vždy jen o jeden disk. Podle legendy existovalo proroctví, že pokud se jim podaří tento čin dokončit, nastane konec světa. V části o časové složitosti ukážeme, že pro postavení Hanojské věže z n disků je potřeba 2^n – 1 tahů.

Takže pokud by kněží potřebovali 1 sekundu na posunutí jednoho disku, celkový čas na vyřešení hádanky by byl 2^64 – 1 sekundy, neboli zhruba 584 942 417 356 let, 26 dní, 7 hodin a 15 sekund.

Algoritmus pro Hanojskou věž

Nejběžnějším způsobem řešení Hanojské věže je rekurzivní algoritmus. Nejprve vybereme dva pruty jako zdroj a cíl; náhradní kolík slouží jako pomocný prvek.

Zde jsou kroky k vyřešení hádanky Hanojské věže:

Přesuňte horních n-1 disků ze zdrojového pegu na pomocný kolík.
Přesuňte n-tý disk ze zdrojového kolíku na cílový kolík.
Přesuňte zbývajících n-1 disků z pomocného kolíku na cílový kolík.

Poznámka: Pokud máme jeden disk, můžeme ho přesunout přímo ze zdroje do cíle.

Jak vyřešit hádanku Hanojská věž

Znázorněme algoritmus pro tři disky. Uvažujme kolík A jako zdroj, kolík B jako pomocníka a kolík C jako cíl.

Krok 1) Zpočátku jsou všechny disky naskládány na kolík A.

V této fázi: Zdroj = Peg A, Cíl = Peg C, Pomocník = Peg B.

Nyní potřebujeme přesunout horních n-1 disků ze zdroje do pomocníka.

Poznámka: I když můžeme přesouvat pouze jeden disk najednou, tento krok redukuje náš problém se třemi disky na problém se dvěma disky, který se řeší rekurzivním voláním.

Krok 2) Když provádíme rekurzivní volání z pegu A s pegem B jako cílem, používáme peg C jako pomocnou funkci.

Všimněte si, že jsme zpět v první fázi pro stejný problém s Hanojskou věží, ale nyní pro dva disky. Přesuneme n-1 (tedy jeden) disk ze zdroje do pomocného, což přesune nejmenší disk z kolíku A na kolík C.

V této fázi: Zdroj = kolík A, Cíl = kolík B, Pomocník = kolík C.

Krok 3) Podle algoritmu je n-tý (2.) disk nyní přesunut do cíle, na peg B.

V této fázi: Zdroj = kolík A, Cíl = kolík B, Pomocník = kolík C.

Krok 4) Nyní přesuneme n-1 disk (disk jedna) z pomocného kolíku C na cílový kolík B, dle třetí fáze algoritmu.

V této fázi: Zdroj = kolík A, Cíl = kolík B, Pomocník = kolík C.

Krok 5) Po dokončení rekurzivního volání se vrátíme k předchozímu nastavení v první fázi algoritmu.

Krok 6) Ve druhé fázi přesuneme disk 3 ze zdrojového kolíku A do cílového kolíku C.

V této fázi: Zdroj = kolík A, Cíl = kolík C, Pomocník = kolík B.

Krok 7) Dalším úkolem je přesunout zbývající disky z pomocného bodu (kolík B) do cílového bodu (kolík C). Tentokrát jako pomocný bod použijeme původní zdroj (kolík A).

Krok 8) Protože nemůžeme přesunout dva disky najednou, provedeme rekurzivní volání pro disk 1. Podle našeho algoritmus, cílem v tomto kroku je kolík A.

V této fázi: Zdroj = kolík B, Cíl = kolík A, Pomocník = kolík C.

Krok 9) Naše rekurzivní volání je dokončeno. Nyní přesuneme disk 2 ze zdroje do cíle.

V této fázi: Zdroj = kolík B, Cíl = kolík C, Pomocník = kolík A.

Krok 10) Dokončíme přesunutím zbývajících n-1 disků (disk 1) z pomocného systému do cílového.

V této fázi: Zdroj = kolík A, Cíl = kolík C, Pomocník = kolík B.

Nepravý Code pro Hanojskou věž

START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
    IF disk == 1 THEN
        move disk from source to dest
    ELSE
        Tower_Of_Hanoi(disk - 1, source, helper, dest)
        move disk from source to dest
        Tower_Of_Hanoi(disk - 1, helper, dest, source)
    END IF
END Procedure

Kód programu v C++

#include <bits/stdc++.h>
using namespace std;
void tower_of_hanoi(int num, string source, string dest, string helper) {
    if (num == 1) {
        cout << " Move disk 1 from tower " << source << " to tower " << dest << endl;
        return;
    }
    tower_of_hanoi(num - 1, source, helper, dest);
    cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl;
    tower_of_hanoi(num - 1, helper, dest, source);
}
int main() {
    int num;
    cin >> num;
    printf("The sequence of moves :\n");
    tower_of_hanoi(num, "I", "III", "II");
    return 0;
}

Výstup:

3
The sequence of moves :
Move disk 1 from tower I to tower III
Move disk 2 from tower I to tower II
Move disk 1 from tower III to tower II
Move disk 3 from tower I to tower III
Move disk 1 from tower II to tower I
Move disk 2 from tower II to tower III
Move disk 1 from tower I to tower III

Kód programu v Python

def tower_of_hanoi(n, source, destination, helper):
    if n == 1:
        print("Move disk 1 from peg", source, "to peg", destination)
        return
    tower_of_hanoi(n - 1, source, helper, destination)
    print("Move disk", n, "from peg", source, "to peg", destination)
    tower_of_hanoi(n - 1, helper, destination, source)
# n = number of disks
n = 3
tower_of_hanoi(n, 'A', 'B', 'C')

Výstup:

Move disk 1 from peg A to peg B
Move disk 2 from peg A to peg C
Move disk 1 from peg B to peg C
Move disk 3 from peg A to peg B
Move disk 1 from peg C to peg A
Move disk 2 from peg C to peg B
Move disk 1 from peg A to peg B

Složitost věže Hanoi

Zde je časová a prostorová složitost Hanojské věže:

1) Časová složitost:

Při pohledu zpět na algoritmus provedeme rekurzivní volání pro (n-1) disků dvakrát za volání. Každá (n-1) rekurze se rozdělí na ((n-1)-1) rekurzí atd., dokud nedosáhneme základního případu s jedním diskem.

Pro tři disky:

Disk 3 volá rekurzivní funkci pro disk 2 dvakrát.
Disk 2 volá rekurzivní funkci pro disk 1 dvakrát.
Disk 1 se pohybuje v konstantním čase, což dává čas potřebný k řešení pro tři disky.

Vyjádřeno jako opakování:

= 2 × (čas potřebný k řešení pro dva disky) + konstantní čas potřebný k přesunutí disku 3

= 2 × (2 × čas potřebný k řešení pro jeden disk + konstantní čas potřebný k přesunu disku 2) + konstantní čas potřebný k přesunu disku 3

= (2 × 2) × konstantní čas pro pohyb disku 1 + 2 × konstantní čas pro pohyb disku 2 + konstantní čas pro pohyb disku 3

Pro n disků to vypadá takto:

2^n-1 × konstantní čas pro pohyb disku 1 + 2^n-2 × konstantní čas potřebný k pohybu disku 2 + ….

Tato geometrická posloupnost se sčítá do O(2ⁿ – 1), což se zjednodušuje na O(2ⁿ), exponenciální časová složitost.

2) Prostorová složitost:

Prostorová složitost Hanojské věže je O(n). Rekurze používá zásobník volání a maximální hloubka zásobníku se rovná n, což je počet disků. Proto je prostorová složitost O(n).

Nejčastější dotazy

Algoritmus Hanojské věže je rekurzivní procedura, která přesouvá n disků ze zdrojového kolíku do cílového kolíku pomocí jednoho pomocného kolíku, přičemž nikdy neumisťuje větší disk na menší.

Minimální počet tahů pro n disků je 2^n – 1. Tři disky potřebují 7 tahů, čtyři disky 15 a deset disků 1 023 tahů.

Časová složitost je O(2^n), protože každý další disk zdvojnásobí práci. Rekurentní rovnice T(n) = 2T(n-1) + 1 se řeší jako 2^n – 1, což je exponenciální.

Prostorová složitost je O(n), protože zásobník rekurzních volání obsahuje jeden rámec pro každý zpracovávaný disk. Maximální hloubka rekurze dosahuje n, takže potřebná pomocná paměť je lineární s počtem disků.

Ano. Iterativní řešení používá smyčku s pevným vzorem: při lichých tazích se cyklicky vyměňuje nejmenší disk mezi kolíčky a při sudých tazích se provádí jediný povolený nenejmenší tah.

Algoritmus učí rekurzi, modeluje schémata zálohování a rotace pro ukládání dat, řídí sekvenování robotického ramene a objevuje se v neuropsychologických testech, které měří schopnost plánování.

Agenti s posilovacím učením řeší Hanojskou věž tak, že každou konfiguraci disku považují za stav a každý pohyb za akci. Jedná se o běžný standard pro plánování a hierarchické učení politik.

Ano. GitHub Copilot, ChatGPT a Gemini generovat rekurzivní řešení Hanojské věže v Python, C++, a JavaVývojáři by si i nadále měli ověřit základní případy a pořadí argumentů.

Algoritmus Hanojské věže: Python, C++ Code

Co je Hanojská věž?

Pravidla Hanojské věže

Algoritmus pro Hanojskou věž

Jak vyřešit hádanku Hanojská věž

Nepravý Code pro Hanojskou věž

Kód programu v C++

Kód programu v Python

Složitost věže Hanoi

Nejčastější dotazy

Shrňte tento příspěvek takto:

Přihlaste se k odběru newsletteru