PŘÍKLAD: Klasický problém hanojských věží je použitím rekurze řešitelný velmi elegantně a názorně:
Jsou dány tři jehly, označené čísly 1, 2 a 3. Na jehle 1 je navléknuto n plochých disků, opatřených uprostřed otvorem. Průměry disků se směrem k vrcholu jehly postupně zmenšují. Úkolem je přenést všechny disky (věž) z jehly 1 na jehlu 3, přičemž
- současně smí být přenášen vždy pouze jediný disk
- disk lze odložit pouze na některou z jehel
- disk však nesmí být odložen na disk menšího průměru
- je-li n = 1:
- přenes tento jediný disk ze zdrojové na cílovou jehlu
- jinak (n
>
1): - použitím tohoto algoritmu postupně přenes n – 1 horních disků ze zdrojové na pomocnou jehlu, cílová jehla přitom slouží jako pomocná pak přenes jediný zbylý disk ze zdrojové na cílovou jehlu a nakonec použitím tohoto algoritmu postupně přenes n – 1 odložených disků z pomocné na cílovou jehlu, jako pomocná přitom slouží jehla zdrojová
{======================================================================} program HanojskeVeze; {======================================================================} var N: Byte; { počet disků - výška věže } procedure Vez (Zdroj, Cil, Pocet: Byte);{ číslo zdrojové a cílové } {--------------------------------------}{ jehly, počet přenášených } { disků } var Pomocna: Byte; { číslo pomocné jehly } begin { Vez } if Pocet = 1 then { přenos jediného disku } Writeln(Zdroj, '-', Cil) else { přenos více disků } begin Pomocna := 6 - Zdroj - Cil; { výpočet čísla pomocné jehly } Dec(Pocet); { počet disků odkládaných na } { pomocnou jehlu } Vez(Zdroj, Pomocna, Pocet); { odložení na pomocnou jehlu } Writeln(Zdroj, '-', Cil); { přenos zbývajícího disku } Vez(Pomocna, Cil, Pocet) { přenos odložených disků } end end; { Vez } begin { program } Writeln; { výpis titulku } Writeln('HANOJSKÉ VĚŽE'); Writeln; repeat { načtení výšky věže } Write('Počet disků (> 0): '); Readln(N) until N > 0; Writeln; Vez(1, 3, N); { přenos celé věže z jehly 1 } { na jehlu 3 } Writeln end. {program}
zdroj: http://home.pf.jcu.cz/~edpo/program/kap05.html
souhrn:
název procedury:
procedure Nazev (promenna1, promenna2, promenna3...: typ);
volání procedury:
nazev(promenna1, promenna2, promenna3...);
Žádné komentáře:
Okomentovat