Programování Hanojských věží v jazyce Pascal s využitím rekurze
Tato práce byla ověřena naším učitelem: 14.05.2026 v 14:38
Typ úkolu: Domácí úkol
Přidáno: 12.05.2026 v 13:34
Shrnutí:
Objevte principy řešení Hanojských věží v Pascalu pomocí rekurze a naučte se efektivně implementovat tento klasický algoritmus krok za krokem.
Hanojské věže – program v Pascalu
Úvod
Mezi nejznámější klasické algoritmické úlohy, které se tradičně objevují ve výuce informatiky nejen na středních, ale i vysokých školách po celé České republice, patří bezpochyby problém Hanojských věží. Tuto úlohu jistě mnozí studenti znají nejen z hodin programování, ale také z popisů v učebnicích algoritmizace, například v dílech Jiřího Herouta „Učebnice algoritmů v Pascalu a C“ nebo z výňatků v odborných časopisech zaměřených na výuku počítačové vědy. Co však činí Hanojské věže skutečně výjimečnými, je jejich spojení s rekurzí a schopnost názorně předvést sílu tohoto principu – zvláště v jazycích určených pro výuku, jakým je Pascal.Legenda, která tento problém uvedla do širšího povědomí, hovoří o mnichech v buddhistickém chrámu v Hanoji, kteří mají z přesunu 64 zlatých disků postavit na třech sloupech podle zvláštních pravidel věž – až se jim to podaří, má podle legendy nastat konec světa. Nechme apokalyptické představy stranou a soustřeďme se na skutečný význam tohoto úkolu – jeho nenahraditelnou roli v rozvoji algoritmického myšlení, rozkládání problémů na menší části a seznámení s rekurzí.
Tato práce si klade za cíl představit podstatu problému Hanojských věží, detailně rozebrat konkrétní algoritmus jeho řešení a zaměřit se na způsob implementace právě v jazyce Pascal. Zároveň budou vysvětleny stěžejní koncepty jako rekurze, přechodové stavy a využití základních datových struktur či procedur. Neopomeneme ani rozbor možností prezentace výsledků a efektivní optimalizace tohoto programu v rámci studijní praxe.
---
I. Teoretické základy problému Hanojských věží
1. Popis problému
Problém Hanojských věží lze formulovat následovně: Máme tři sloupce (tyče), na první z nich je v počátečním stavu navlečeno n disků různých velikostí, seřazených od největšího dole po nejmenší. Cílem je přemístit celou sadu disků na jiný sloupec dle následujících pravidel: - Vždy lze přesunout pouze jeden disk najednou. - Nikdy nesmí být větší disk položen na menší. - Disky lze přesunovat pouze mezi třemi stanovenými sloupci.Tento problém je značně didaktický – klade důraz jak na kontrolu správnosti každého kroku, tak na schopnost plánovat postup vpřed, což rozvíjí algoritmické myšlení podobně, jako je tomu u šachových úloh či klasické matematické hry tzv. osmisměrek.
2. Matematické modelování
V teoretické rovině lze zjistit, že minimální počet tahů potřebných k přesunu n disků je přesně \(2^n - 1\). Tento vztah lze dokázat indukcí – u jednoho disku je třeba jediný tah, s n disky nejprve přesuneme n-1 disků na pomocný sloupec, poté hlavní disk a následně opět n-1 disků. Výsledná časová složitost je tedy exponenciálně rostoucí, což je dobře ilustrováno zejména u vyšších hodnot n.3. Význam rekurze
Pokud nahlížíme na úlohu pohledem programátora či matematika, nejvýrazněji vyniká přirozený rekurzivní charakter problému. Celý přesun n disků lze totiž rozdělit na tři dílčí úkoly o menším rozsahu: 1. Přesunout n-1 disků z výchozího sloupce na pomocný. 2. Přemístit největší disk na cílový sloupec. 3. Přesunout n-1 disků z pomocného sloupce na cílový.Toto schéma fascinuje studenty i pedagogy – umožňuje elegantně ukázat sílu rekurzivního rozkladu problémů, což v českých informatických učebnicích často bývá demonstrováno právě Hanojskými věžemi na rozdíl třeba od méně motivačních příkladů s faktoriálem či fibonacciho posloupností.
4. Alternativní přístupy
Na rozdíl od rekurzivního řešení lze problém řešit i iteračně, využitím zásobníkových struktur, což studenti poznávají při rozšířených verzích úkolu či v pokročilejší výuce. Některé didaktické aplikace ve školním prostředí nabízí i grafickou simulaci, například v kombinaci Pascalu s prostředím Lazarus nebo s využitím jednoduchých ASCII vizualizací v textovém režimu. Tyto přístupy názorně ukazují nejen správné provedení jednotlivých tahů, ale i samotné vzory pohybů mezi sloupci.---
II. Jazyk Pascal a jeho vhodnost pro řešení Hanojských věží
1. Charakteristika Pascalu
Pascal je jazyk, který svůj první velký rozmach zažil v 80. a 90. letech 20. století, a to zejména díky své srozumitelnosti a zaměření na výuku algoritmizace. Typickou charakteristikou Pascalu je přehledná syntaxe, přímá práce s procedurami, funkcemi i rozsáhlá podpora práce s rekurzí. Právě to činí z Pascalu ideálního kandidáta pro ukázku řešení Hanojských věží na středních školách i v kurzech základů programování. Slavné jsou zejména pascalovské učebnice autora Jiřího Herouta, kde je tento problém pravidelně zařazován.2. Výhody použití Pascalu
Vedle jednoduché syntaxe nabízí Pascal i přehledný systém deklarací, díky kterému je možné jasně strukturovat i složitější algoritmy. Výhodou je rovněž velmi čitelné odlišení hlavního programu od procedur a funkcí. Jelikož je rekurze základním stavebním kamenem algoritmu Hanojských věží, zmiňovaný jazyk se hojně uplatňuje při demonstračních příkladech na gymnáziích, průmyslových školách i v rámci seminářů na univerzitách.3. Možnosti vstupu a výstupu
Pascal podporuje klasický vstup/výstup skrze příkazy Readln, Writeln a podobné konstrukce. To umožňuje programátorům nejen dynamicky zadat počet disků, ale například i flexibilně pojmenovat jednotlivé sloupce. Výstupní výsledky lze jednoduše zobrazit střídavým výpisem kroků do konzole, popřípadě uložit do souboru či graficky reprezentovat nadstavbovým modulem, např. v prostředí Free Pascalu s knihovnou Graph nebo v Lazarusu v podobě jednoduchých animací.---
III. Detailní rozbor rekurzivního algoritmu pro Hanojské věže
1. Definice základního případu
V každé rekurzivní funkci či proceduře je nutné jasně ošetřit základní případ (tzv. „base case“), jehož dosažení zabrání nekonečné rekurenci. V Hanojských věžích nastává tehdy, když počet přesouvaných disků je roven jedné – v této situaci stačí disk jednoduše přesunout z výchozího na cílový sloupec.2. Rekurzivní případ
Pokud počet přesouvaných disků převyšuje jednu, algoritmus se rozpadá následovně: - Nejprve je nutné (rekurzivně) přemístit n-1 disků z původního sloupce na pomocný (přičemž cílový sloupec dočasně slouží jako pomocný). - Následuje konkrétní přesun největšího disku (toho, který je právě na spodku sledovaného „podproblému“) na cílový sloupec. - Závěrem (opět rekurzivně) přesuneme n-1 disků z pomocného sloupce na cílový (s původním sloupcem jako pomocným).3. Popis parametrování procedury
Hlavní procedura pro řešení Hanojských věží bývá přehledně parametrizována čtyřmi hodnotami: - Počet disků k přesunu (n). - Zdrojový sloupec (odkud disky přesouváme). - Cílový sloupec (kam disky přesouváme). - Pomocný sloupec (sloupec využívaný jako meziuložiště).Každý z těchto parametrů má svůj konkrétní význam v rekurzivní struktuře – výměnou jejich pořadí lze algoritmus nasměrovat ke správné posloupnosti tahů.
4. Ukázka zápisu rekurzivní procedury v Pascalu (pouze struktura)
Struktura procedury může vypadat následovně (v obecné podobě):procedure Hanoi(n, odkud, kam, pomocny); - Pokud n = 1, proveď přesun mezi „odkud“ a „kam“ a vypiš krok. - Jinak: - Zavolej samu sebe pro (n-1, odkud, pomocny, kam). - Proveď přesun n-tého disku mezi „odkud“ a „kam“. - Zavolej samu sebe pro (n-1, pomocny, kam, odkud).
Každý blok lze označit jasným komentářem v programu pro snazší sledování průběhu při studiu a ladění.
---
IV. Implementační detaily v Pascalu
1. Struktura programu
Jednoduchý program tradičně začíná deklarací proměnných pro počet disků a jednotlivé názvy sloupců. Následuje definice hlavní procedury „Hanoi“ s příslušnými parametry, vlastní tělo programu pak zajišťuje zadání počtu disků (např. přes Readln) a volání rekurzivní procedury.2. Způsob výpisu kroků
Každý jednotlivý tah je vypsán v konzoli ve formátu: „Přesuň disk z X na Y“ (např. „Přesuň disk z A na B“). Dochází tak k sekvenčnímu sledování přesunů, což studentům usnadní kontrolu správnosti i sledování logiky algoritmu. V rozšířených verzích lze kroky ukládat např. do pole nebo dynamicky do souboru, což umožňuje pozdější analýzu.3. Optimalizace a ladění
Při implementaci je doporučeno kontrolovat vstupní data – tedy ověřit, že zadán je kladný počet disků v rozumném rozsahu. Pro výukové účely lze nadto zařadit ladicí výstupy, které ukazují, v jaké úrovni rekurze se algoritmus aktuálně nachází, případně jak se mění hodnoty parametrů při voláních hlavní procedury.4. Možné rozšíření programu
Zajímavým rozšířením je napojení na jednoduché grafické prostředí, například pomocí základní konzolové grafiky, kde lze jednotlivé disky a sloupce zobrazit stylizovaně v textu. Pokročilejší studenti mohou řešení obohatit o GUI v Lazarusu, kde lze pozorovat animované přesuny disků, případně zajištění funkcionality pro krokování (pro názornou demonstraci postupu řešení s pauzami mezi kroky).---
V. Analýza výsledků a praktické využití programu
1. Testování programu
V praxi je vhodné ověřit funkci programu na malém množství disků, například pro hodnoty 3 nebo 5, kde lze očekávat počet tahů 7, resp. 31. Takový výstup lze srovnat se známými tabulkami, které jsou běžně dostupné v českých učebnicích informatiky či na vzdělávacích serverech, například „Algoritmy.net“ nebo odborných webinářích pro učitele.2. Výpočet složitosti
Časová složitost algoritmu je \(O(2^n)\), což názorně ukazuje rychlý nárůst potřebného času (a paměťových požadavků při rekurzi) s rostoucím počtem disků. V rámci školních projektů studenti sledují především počet volání procedur (či počet tahů), což je příležitost k upevnění představ o exponenciálním růstu.3. Využití v reálném světě a ve výuce
Program obsahující řešení Hanojských věží je výtečným didaktickým nástrojem. Umožňuje nejen pochopit princip rekurze, ale také demonstrovat principy rozkladu složitých problémů na menší části. Podobné postupy lze následně aplikovat v programování vyhledávacích algoritmů, řešení kombinatorických úloh anebo v optimalizačních úlohách (např. problém obchodního cestujícího).---
Závěr
Problematika Hanojských věží představuje jedno z nejcennějších laboratorních cvičení pro pochopení algoritmického myšlení, zejména v kombinaci s jazykem Pascal, který díky své jednoduchosti a přehlednosti zůstává stále populární v českém školství. Implementace umožňuje studentům osvojit si principy rekurze a pochopit význam správného strukturování kódu i průběžného ladění.Výzvou zůstává další rozvoj programu, například doplnění vizuálního rozhraní či převedení řešení do jiných jazyků jako je Python, C
nebo Java. Aplikace získaných zkušeností s Hanojskými věžemi tvoří pevný základ pro řešení i mnohem náročnějších úloh, které v budoucnu studenti potkají při studiu či v práci programátora.
Závěrem bych chtěl poděkovat všem pedagogům a autorům českých učebnic, kteří Hanojské věže stále zařazují do výuky – bez nich by generace studentů přišly o jedinečnou možnost zažít kouzlo algoritmů na vlastní kůži. Doporučuji všem čtenářům nebát se experimentovat a osvojit si i složitější algoritmické problémy – právě zde začíná cesta k skutečnému programátorskému mistrovství.---
Přílohy
1. Ukázka zdrojového kódu v Pascalu (pro ilustraci, není nutné přesně kopírovat)
```pascal procedure Hanoi(n: integer; odkud, kam, pomocny: char); begin if n = 1 then writeln('Přesuň disk z ', odkud, ' na ', kam) else begin Hanoi(n-1, odkud, pomocny, kam); writeln('Přesuň disk z ', odkud, ' na ', kam); Hanoi(n-1, pomocny, kam, odkud); end; end; ```2. Schematická vizualizace kroků
Například při třech discích: - Přesuň 1 z A na C - Přesuň 2 z A na B - Přesuň 1 z C na B - Přesuň 3 z A na C - Přesuň 1 z B na A - Přesuň 2 z B na C - Přesuň 1 z A na C3. Tabulka počtu tahů
| Počet disků | Počet tahů | |-------------|------------| | 1 | 1 | | 2 | 3 | | 3 | 7 | | 4 | 15 | | 5 | 31 | | ... | ... | | 10 | 1023 | | n | 2^n - 1 |---
Časté dotazy k učení s AI
Odpovědi připravil náš tým pedagogických odborníků
Jak naprogramovat Hanojské věže v jazyce Pascal s využitím rekurze?
Hanojské věže lze v Pascalu efektivně vyřešit pomocí rekurzivní procedury, která rozděluje problém na přesun n-1 disků a následné přemístění největšího disku.
Co je principem řešení Hanojských věží v Pascalu s rekurzí?
Principem je rozdělení úlohy na tři menší kroky, pomocí rekurze postupně přesouvat disky mezi třemi tyčemi podle zadaných pravidel.
Jaký je minimální počet tahů při řešení Hanojských věží v Pascalu?
Minimální počet tahů je dán vzorcem 2^n - 1, kde n je počet disků, a platí i pro program v Pascalu.
V čem je Pascal vhodný pro programování Hanojských věží s rekurzí?
Pascal je vhodný pro svou srozumitelnost, podporu rekurze a přehlednou strukturu programů, což usnadňuje řešení algoritmických úloh.
Jaký je rozdíl mezi rekurzivním a iteračním řešením Hanojských věží v Pascalu?
Rekurzivní řešení využívá volání sebe sama k rozkladu úkolu, zatímco iterační využívá zásobník a je složitější na pochopení.
Ohodnoťte:
Přihlaste se, abyste mohli práci ohodnotit.
Přihlásit se