Rekurze
Pavel Töpfer, KSVI MFF UK Praha
OBSAH
1. Co je to rekurze ................................................................................................ 2
2. Rekurze v programech .................................................................................... 5
3. Rekurzivní algoritmy.....................................................................................10
3.1. Matematické rekurzivní vzorce................................................................................... 10
3.2. Generování všech prvků dané vlastnosti..................................................................... 16
3.3. Prohledávání s návratem ............................................................................................. 30
3.4. Rozděl a panuj ............................................................................................................ 33
4. Rekurzivní datové struktury ........................................................................36
5. Efektivita rekurzivních postupů...................................................................39
5.1. Zrychlení rekurze ........................................................................................................ 39
5.2. Nahrazení rekurzivních volání zásobníkem ................................................................ 40
5.3. Odstranění rekurzivního postupu ................................................................................ 41
LITERATURA
Tento text vychází ze stejnojmenné publikace vydané v roce 1998 nakladatelstvím Fortuna.
Různé další rekurzivní algoritmy naleznete vedle tohoto textu také v učebnicích
Pavel Töpfer: Algoritmy a programovací techniky, Prometheus Praha 1995, 2. vyd. 2007
Niklaus Wirth: Algoritmy a štruktúry údajov, Alfa Bratislava 1988
1. Co je to rekurze
Tento text podává základní přehled o tom, co je to rekurze a jak se v programování využívá.
Obsahuje obecný výklad celé problematiky a řadu řešených úloh. Zabývá se vhodností a
nevhodností použití rekurze v různých situacích a také otázkami efektivity rekurzivních algoritmů
a programů. V programových ukázkách je zde všude používán programovací jazyk Pascal, resp.
jeho implementace Turbo Pascal. Uvedené rekurzivní algoritmy jsou ale samozřejmě nezávislé na
konkrétním programovacím jazyce.
Algoritmus, datovou strukturu nebo třeba kresbu či jakýkoli jiný předpis označujeme jako
rekurzivní, jestliže je definován pomocí sebe sama. Známý “rekurzivní obrázek” používaný
v mnoha učebnicích o rekurzi znázorňuje televizor, na jehož obrazovce vidíme televizor, na jehož
obrazovce vidíme televizor, atd. Tento jev jste ostatně mohli vidět na vlastní oči i ve skutečné
televizi, pokud se v nějakém přenosu z televizního studia dostane náhodou do záběru televizní
kamery obrazovka monitoru, v němž moderátoři sledují průběh vysílání. Popsaný rekurzivní jev je
teoreticky nekonečný, ve skutečnosti však vidíme pouze jistý konečný počet obrazovek v sobě.
Tato skutečnost je způsobena omezenou rozlišovací schopností jak televizní obrazovky, tak i
tiskárny v případě tištěného obrázku.
S některými rekurzivními jevy a postupy se setkáváme i jinde v životě. Snad každé malé dítě zná
pohádku o kohoutkovi a slepičce. Lakomý kohoutek se nerozdělil se slepičkou o nalezený oříšek,
spolknul ho sám a oříšek mu uváznul v krku. Slepička musí pro záchranu kohoutka podniknout
složitou cestu. Potřebuje přinést kohoutkovi vodu ze studánky, ale studánka chce za vodu šátek od
švadleny. Švadlena jí ale nedá šátek, dokud nedostane střevíce od ševce. A tak putování slepičky
pokračuje stále dál. Kdykoli někoho o něco požádá, splnění její prosby je podmíněno dalším
požadavkem. Ještě že po mnoha krocích svého putování narazí slepička na hodné nebe, které za
rosu pro louku nic nechce. Počet rekurzivních kroků je tím pevně omezen a pohádka může šťastně
skončit záchranou kohoutka. A kde že je v pohádce použita rekurze? Slepička opakovaně provádí
akci typu “přines od X předmět Y”, která má rekurzivní charakter. K jejímu provedení je totiž
nutné nejprve vykonat akci téhož typu, jen s jinými hodnotami X, Y.
S podobným postupem se setkáváme i v dospělosti při jednání s různými úřady. Úřad A potřebuje
k vystavení námi požadovaného dokladu nejprve donést potvrzení od úřadu B, úřad B ale žádá
nejprve potvrzení od úřadu C, atd. Máme-li alespoň tolik štěstí jako pohádková slepička, narazíme
po konečném počtu kroků na úřad, který od nás nic dalšího nepožaduje, a celou svoji záležitost
můžeme nakonec úspěšně vyřídit. Uvedené příklady nám tedy zároveň ilustrují důležitost omezení
hloubky rekurze pro praktickou použitelnost rekurzivního postupu.
Různé rekurzivní předpisy se vyskytují zejména v matematice. Používají se například v definicích
některých číselných posloupností. V pořadí n-tý člen posloupnosti {an} může být zadán buď
explicitním vzorcem v závislosti na n, např. an=2n-1, nebo může být určen rekurzivně pomocí
jiného nebo jiných členů téže posloupnosti, např. an=an-1+2. Aby měla smysl takováto rekurzivní
definice, musí být ovšem zadány ještě počáteční hodnoty, od kterých se celá rekurze odvíjí.
V našem příkladu může tedy úplná definice posloupnosti {an} vypadat třeba takto:
a1 = 1
an = an-1 + 2
pro n > 1.
Není stanovena žádná horní mez indexu n, takže v tomto případě máme rekurzivní předpis
nekonečné číselné posloupnosti. Snadno zjistíte, že jde o posloupnost všech lichých celých čísel,
2
tedy o stejnou posloupnost, kterou jsme již dříve definovali také explicitním předpisem an = 2n-1,
n > 0.
V případě posloupnosti lichých čísel bychom se bez rekurzivního předpisu klidně obešli, při
výpočtech stejně raději použijeme jednoduchý explicitní vzorec. U některých posloupností však
takovouto jednoduchou možnost nemáme. Buď explicitní vzorec vůbec neznáme, nebo je pro naše
potřeby příliš komplikovaný. K nejznámějším posloupnostem, které bývá v matematice zvykem
definovat rekurzivně, patří třeba faktoriál nebo posloupnost Fibonacciho čísel. Faktoriál celého
kladného čísla n označujeme symbolem n!. Představuje součin všech kladných celých čísel od 1
do n. Faktoriál se používá ve velké míře například v kombinatorice. Formálně ho definujeme
rekurzivním předpisem
1! = 1
n! = n .(n-1)!
pro n > 1.
Fibonacciho čísla patří k nejzajímavějším číselným posloupnostem. Setkáme se s nimi nejen
v matematice, ale v různých nečekaných souvislostech i v biologii, ve výtvarném umění a také při
návrhu algoritmů a programů. Posloupnost začíná dvěma jedničkami a dále pokračuje tak, že
každé další Fibonacciho číslo je rovno součtu dvou bezprostředně předcházejících Fibonacciho
čísel. Formálně tento rekurzivní vztah zapíšeme následovně:
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2
pro n > 1.
Rekurzivní formule se objevují i v definicích některých geometrických útvarů a křivek.
Nejznámější rekurzivně definované geometrické křivky patří mezi tzv. fraktální obrazce.
Problematika fraktální geometrie je velmi bohatá a nemůžeme se jí zde podrobně věnovat.
Ukážeme si proto alespoň dva typické příklady geometrických útvarů, jejichž definice jsou
založeny na rekurzi.
Prvním z nich bude slavná sněhová vločka Kochové. Při její konstrukci vyjdeme od
rovnostranného trojúhelníka. Každou jeho stranu rozdělíme na třetiny a nad prostředním dílem
každé strany sestrojíme menší rovnostranný trojúhelník (směrem ven od středu útvaru). Tím
dostaneme křivku Kochové 2. řádu ve tvaru jednoduché pravidelné šesticípé hvězdy. Dále
postupujeme stejným způsobem, tj. každou stranu vždy rozdělíme na třetiny a nad prostřední
z nich sestrojíme rovnostranný trojúhelník směrem ven. Počet iterací není teoreticky nijak pevně
omezen.
Jako druhý příklad si můžeme uvést neméně známou Hilbertovu křivku. Hilbertova křivka 1.
řádu je definována jednoduše pomocí tří spojených stejně dlouhých úseček. Hilbertovy křivky
vyšších řádů jsou pak zadány rekurzivním předpisem. Křivku k-tého řádku pro k > 1 sestrojíme
složením čtyř křivek řádu (k-1), které vůči sobě vhodně natočíme a spojíme třemi úsečkami.
Názorně vidíme celou situaci na obrázku s prvními třemi Hilbertovými křivkami:
3
My se budeme v této knize zajímat o použití rekurze v programování. Rekurze se používá jak při
návrhu algoritmů, tak i při realizaci algoritmů formou rekurzivních volání procedur a funkcí.
Rekurzivní principy se uplatňují i při návrhu a používání některých datových struktur. Zaměříme
se pouze na využití rekurze při práci s běžnými programovacími jazyky. Jejich typickým
představitelem je Pascal, který budeme také používat ve všech programových ukázkách. Přesněji
řečeno, budeme používat Turbo Pascal jakožto dnes nejrozšířenější implementaci Pascalu na PC.
Nebudeme se věnovat ani neprocedurálním programovacím jazykům (jako jsou Lisp nebo Prolog),
pro které je použití rekurze typické, ani jazykům speciálním (např. školní výukový jazyk Karel),
které rovněž rekurzi bohatě využívají.
Později se ještě vrátíme k některým příkladům uvedeným v této úvodní kapitole a ukážeme si
možnosti jejich programové realizace.
4
2. Rekurze v programech
Rekurze představuje velmi silný prostředek v rukou programátora. S využitím rekurze můžeme
často napsat krátký a elegantní program, zatímco nerekurzivní řešení téhož problému by bylo
mnohem pracnější. Použití rekurze má však také svá úskalí. Každý vysoce účinný nástroj se nám
může stát nebezpečným, pokud s ním nepracujeme dostatečně opatrně a používáme ho neuváženě
při práci, pro kterou není určen. Jestliže v programu použijeme rekurzi na nevhodném místě,
můžeme dostat program, který bude sice funkčně správný, ale velmi nepřehledný a
nesrozumitelný. V takovém programu se pak jen těžko provádějí nějaké pozdější úpravy nebo
změny a je také pravděpodobnější, že se při zápisu programu dopustíme chyby. Hledání a
odstraňování běhových chyb v rekurzivních programech bývá navíc obtížnější než v programech
bez rekurze. Nešikovné použití rekurze nám však přináší ještě další nebezpečí. Často vede
k programům, které jsou sice věcně správné, ale jsou příliš pomalé. V krajním případě se může
snadno stát, že teoreticky dobře navržený program je prakticky nepoužitelný, neboť doba potřebná
k jeho provedení na počítači přesahuje naše časové možnosti. Rekurzi bychom proto měli
v programování používat vždy opatrně a pouze tam, kde je její použití účelné a přirozené, kde nám
zjednoduší zápis programu a nezpůsobí přílišné zpomalení výpočtu.
V programování se rekurze objevuje ve dvou odlišných rovinách. První z nich je rekurzivní
návrh algoritmu, druhou pak použití rekurzivního volání procedury nebo funkce jakožto
prostředku programovacího jazyka. Tyto dvě roviny spolu zpravidla úzce korespondují, rekurzivní
volání využíváme zejména pro realizaci rekurzivních algoritmů. Nemusí tomu ale tak být vždycky.
Algoritmus, který je svou povahou rekurzivní, můžeme naprogramovat i bez použití rekurzivních
volání podprogramů tak, že mechanismus rekurzivního volání nahradíme vlastním programovým
zásobníkem a cyklem v programu. Zápis programu se tím obvykle trochu zkomplikuje, výpočet ale
bývá dokonce o něco rychlejší. Ušetří se totiž čas, který je při výpočtu rekurzivní verze programu
potřebný pro vlastní režii rekurze, tj. pro každé zavolání rekurzivního podprogramu a pro jeho
ukončení. Někdy rekurzivní volání procedur a funkcí ani použít nemůžeme, neboť zvolený
programovací jazyk něco takového vůbec nepřipouští (např. původní verze jazyka Fortran).
Naopak rekurzivní proceduru můžeme použít v programu i v situaci, kdy algoritmus žádnou
rekurzi nevyžaduje. V krajním případě můžeme dokonce rekurzivní procedurou nahradit jakýkoli
cyklus. Místo zápisu cyklu ve tvaru
while P do S;
je možné zavolat rekurzivní proceduru Q, kterou si předem deklarujeme takto:
procedure Q;
begin
if P then
begin S; Q end
end;
Takovéto použití rekurze patří samozřejmě do kategorie těch naprosto nevhodných. Zápis
programu zbytečně znepřehledňuje a navíc zpomaluje výpočet programu.
Rekurze jakožto prvek programovacího jazyka spočívá v tom, že procedura nebo funkce může ve
svém těle volat sama sebe. Tomuto volání pak říkáme rekurzivní volání procedury, resp. funkce.
Je vykonáno stejným způsobem jako kterékoli jiné volání procedury. Mechanismus volání
procedur a funkcí je v programovacích jazycích podobných Pascalu realizován pomocí vyhrazené
oblasti operační paměti počítače zvané systémový zásobník. Při každém zavolání procedury (příp.
funkce) se na vrcholu tohoto zásobníku vymezí místo pro tzv. aktivační záznam volané procedury.
Ten obsahuje prostor pro uložení všech parametrů a lokálních proměnných procedury. Dále
5
obsahuje některé technické údaje, jako např. návratovou adresu (tj. adresu v kódu programu,
odkud byla procedura zavolána). Tyto další údaje jsou potřebné pro správné provádění odkazů na
globální proměnné během práce procedury a pro korektní ukončení procedury s předáním řízení
zpět do místa jejího volání. V každém okamžiku výpočtu programu je na vrcholu systémového
zásobníku umístěn aktivační záznam právě prováděné procedury. Při ukončení výpočtu této
procedury je její aktivační záznam zrušen a výpočet programu pokračuje bezprostředně za
příkazem volání právě skončené procedury.
Každé zavolání rekurzivní procedury vede k vytvoření jejího nového aktivačního záznamu a tedy
také ke vzniku nové, zcela samostatné sady jejích lokálních proměnných. Proměnné každého
rozpočítaného exempláře rekurzivní procedury mají stejné identifikátory a stejnou strukturu, jsou
však umístěny v paměti počítače na jiném místě a mohou proto mít odlišné hodnoty. Při
rekurzivním volání se zaznamená místo, z něhož byl nový exemplář procedury zavolán, a příkazy
procedury se pak začnou provádět znovu od začátku. Po ukončení výpočtu procedury se zruší její
aktivační záznam umístěný na vrcholu zásobníku a provede se návrat do místa, odkud byla
procedura zavolána. Tam se bude pokračovat v provádění příkazů “staršího exempláře”
procedury, a to od zaznamenaného místa, kde předtím došlo k přerušení výpočtu. Přitom se bude
používat původní sada proměnných s hodnotami, které v nich byly zanechány v okamžiku
rekurzivního volání.
Popsaný mechanismus rekurzivních volání si můžeme ukázat na rekurzivním tvaru funkce pro
výpočet faktoriálu. Funkce nemá žádné lokální proměnné, ale má jeden parametr předávaný
hodnotou. Parametr představuje kladné celé číslo, jehož faktoriál chceme spočítat. Zápis funkce
přesně kopíruje rekurzivní definici faktoriálu uvedenou v úvodní kapitole:
function Faktorial(N: integer): integer;
begin
if N = 1 then
Faktorial := 1
else
Faktorial := N * Faktorial(N-1)
end;
Jestliže v hlavním programu zavoláme funkci Faktorial s parametrem rovným 3, vytvoří se
v systémovém zásobníku záznam s uloženým parametrem N=3 a funkce se začne provádět. Jelikož
N je různé od 1, bude zavolána funkce Faktorial s parametrem hodnoty 2. Přitom se vytvoří druhý
aktivační záznam s údajem N=2 a funkce Faktorial bude prováděna opět od začátku. Znovu je N
různé od 1, a proto bude funkce Faktorial zavolána potřetí, tentokrát s parametrem 1. To vede
k vytvoření třetího aktivačního záznamu na zásobníku s uloženou hodnotou N=1. Při zahájení
výpočtu funkce Faktorial bude tentokrát splněna rovnost N = 1 a výpočet funkce proto ihned
skončí s funkční hodnotou 1. Ze zásobníku se přitom odstraní vrchní záznam a výpočet pokračuje
ve druhém exempláři funkce Faktorial, v němž N=2. Pokračuje se bezprostředně za místem právě
ukončeného rekurzivního volání. Spočítá se funkční hodnota rovná 2 a výpočet funkce skončí.
Přitom se ze zásobníku odstraní druhý aktivační záznam a řízení se vrátí do prvního, tedy
nejstaršího exempláře funkce Faktorial, v jehož záznamu je uložen údaj N=3. Tam se spočítá
funkční hodnota 3 * 2 = 6 a tato výsledná hodnota je předána hlavnímu programu. Zároveň
s ukončením výpočtu funkce Faktorial je zrušen i její nejstarší aktivační záznam.
Při psaní rekurzivních procedur a funkcí nesmíme nikdy zapomenout na ukončení rekurze.
Každé rekurzivní volání musí být vázáno na splnění nějaké podmínky. Pokud by se v proceduře
objevilo bezpodmínečné rekurzivní volání sama sebe, zavolání této procedury by vedlo nutně
k nekonečnému výpočtu. Procedura by stále znovu a znovu volala sama sebe a žádné její volání by
nebylo nikdy ukončeno. Vzhledem k tomu, že každé zavolání procedury nebo funkce je provázeno
přidělením jistého paměťového prostoru v systémovém zásobníku a že pro celý zásobník je
6
vyhrazena předem pevně vymezená oblast v paměti počítače, výpočet takovéto procedury by po
jisté době skončil běhovou chybou přeplnění systémového zásobníku. Procedura by totiž stále
volala sama sebe a každé takovéto zavolání by si vyžadovalo vytvoření dalšího aktivačního
záznamu v zásobníku, až by jednou došlo k úplnému zaplnění té části paměťového prostoru
počítače, která je pro systémový zásobník vyhrazena. Tělo rekurzivní procedury proto zpravidla
zahajujeme testem vhodně zvolené podmínky, která bývá vázána na hodnoty vstupních parametrů
a která zajišťuje, že pro některé hodnoty již k dalšímu rekurzivnímu zavolání nedojde. Příklad
takového testu vidíme ve funkci Faktorial a uvidíme ho ještě v mnoha dalších rekurzivních
procedurách a funkcích.
Vedle právě popsané tzv. přímé rekurze, kdy procedura nebo funkce volá ve svém těle sama
sebe, existuje ještě rekurze nepřímá. Ta spočívá v tom, že je sice také v jednom okamžiku
rozpočítáno více exemplářů téže procedury, nikoli však přímým zavoláním sama sebe. Procedura
A může například volat proceduru B a procedura B zase proceduru A. Tento řetězec vzájemných
volání procedur nebo funkcí může být i delší (např. A volá B, B volá C, C volá D, D volá A). Ze
zběžného pohledu na zápis programu tudíž nemusí být ihned zřejmé, zda a ve kterém místě
programu se vyskytuje rekurze.
Chceme-li použít nepřímou rekurzi v programu zapsaném programovacím jazykem Pascal,
musíme vhodně zvolit pořadí deklarací procedur, mezi nimiž se vztah nepřímé rekurze uplatňuje.
V Pascalu totiž platí zásada, že každý identifikátor (tedy i identifikátor procedury) může být
použit (tj. procedura může být zavolána) až za místem své deklarace. Vzájemnou závislost
několika procedur můžeme řešit více způsoby. Zcela obecným a přehledným prostředkem pro
deklaraci procedur či funkcí ve vztahu nepřímé rekurze je direktiva forward. V programu nejprve
deklarujeme samotné hlavičky podprogramů včetně jejich parametrů, místo těl podprogramů však
zapíšeme pouze klíčové slovo forward. Poté mohou již bez problémů následovat deklarace celých
procedur a funkcí, a to dokonce v libovolném pořadí. Díky předsunuté deklaraci forward jsou při
jejich překladu známa všechna jména podprogramů, které jsou z nich nepřímou rekurzí volány.
Příklad: Mějme v programu tři procedury nazvané A, B, C ve vztahu nepřímé rekurze - procedura
A volá proceduru B, ta volá proceduru C a procedura C volá proceduru A i proceduru B. Zápis
deklarací těchto procedur může vypadat následovně:
procedure A;
forward;
procedure B;
forward;
procedure C;
forward;
procedure A;
begin
...
B;
...
end;
procedure B;
begin
...
C;
...
end;
7
procedure C;
begin
...
A;
...
B;
...
end;
Ne vždy je nutné zapisovat v programu předsunuté deklarace všech procedur, mezi nimiž se
uplatňuje nepřímá rekurze. Je-li ve vztahu mezi procedurami pouze cyklická závislost, což je dosti
častý případ, vystačíme s jedinou předsunutou deklarací a vhodně zvoleným pořadím zápisu
procedur. Opět si to ukážeme na příkladu.
Příklad: Mějme v programu tři procedury nazvané A, B, C ve vztahu nepřímé rekurze - procedura
A volá proceduru B, ta volá proceduru C a procedura C volá proceduru A. Pořadí deklarací
procedur může být následující:
procedure A;
forward;
procedure C;
begin
...
A;
...
end;
procedure B;
begin
...
C;
...
end;
procedure A;
begin
...
B;
...
end;
Někdy se stává, že mezi rekurzivními procedurami je pouze cyklická závislost a navíc z vnějšku
(např. z hlavního programu) je volána pouze jediná z těchto procedur. V takovém případě
direktivu forward vůbec nepotřebujeme, stačí deklarovat všechny procedury ve vhodném pořadí
jako lokální uvnitř té z nich, která je používána z vnějšku.
Příklad: Mějme v programu tři procedury nazvané A, B, C ve vztahu nepřímé rekurze - procedura
A volá proceduru B, ta volá proceduru C a procedura C volá proceduru A. Z hlavního programu je
volána pouze procedura A. Soustavu těchto tří procedur můžeme deklarovat následovně:
8
procedure A;
procedure C;
begin
...
A; {smí volat, A je pro ni globální symbol}
...
end;
procedure B;
begin
...
C; {smí volat, C bylo deklarováno dříve}
...
end;
begin {A}
...
B; {smí volat, B je její lokální procedura}
...
end; {A}
S praktickým využitím nepřímé rekurze se v programech setkáváme o dost méně, než s rekurzí
přímou. V této knize si předvedeme alespoň dva ukázkové programy založené na technice nepřímé
rekurze. Půjde jednak o program na vykreslování Hilbertových křivek, o nichž jsme se již zmínili
v úvodu, jednak o algoritmus vyhodnocování aritmetických výrazů. Oba tyto příklady užití
nepřímé rekurze najdete hned v následující kapitole.
9
3. Rekurzivní algoritmy
Pokusíme se nyní ukázat alespoň některé základní oblasti, kde se při návrhu algoritmů využívá
rekurze a kde je její použití přirozené a výhodné. Jednotlivé rekurzivní postupy řešení úloh
budeme demonstrovat na konkrétních příkladech. Nejprve si předvedeme algoritmy odvozené
z různých matematických rekurzivních předpisů, dále rekurzivní řešení úloh typu “nalézt všechny
prvky jisté vlastnosti” a s tím související algoritmy na prohledávání s návratem. Závěrečný oddíl
této kapitoly je věnován rekurzivnímu postupu nazývanému “rozděl a panuj”. V následující čtvrté
kapitole se seznámíme se základními rekurzivně definovanými datovými strukturami a také
s algoritmy pro jejich zpracování.
3.1. Matematické rekurzivní vzorce
Některé matematické objekty bývají definovány nebo popsány rekurzivními předpisy. Jako
typický příklad nám poslouží třeba definice číselných posloupností, v nichž je n-tý člen
posloupnosti an popsán pomocí jednoho nebo více předcházejících členů. S několika konkrétními
příklady takových posloupností jsme se již setkali v první kapitole, kde jsme uvedli rekurzivní
definici posloupnosti lichých čísel, faktoriálu a Fibonacciho čísel.
Při návrhu algoritmu pro výpočet n-tého členu rekurzivně definované posloupnosti máme dvě
možnosti. Nejpohodlnější cestou bývá přímé přepsání rekurzivního předpisu do podoby rekurzivní
funkce programovacího jazyka. To jsme si již ukázali v kap. 2 pro případ výpočtu faktoriálu.
Z hlediska průběhu výpočtu bývá ale výhodnější postupovat jinak. Pokud se nám podaří odvodit
z rekurzivní definice posloupnosti explicitní vzorec vyjadřující hodnotu členu an pouze
v závislosti na n, dostaneme rychlejší a mnohdy i paměťově méně náročný algoritmus. Buď se
výpočet řádově zrychlí, nebo se alespoň odstraní zbytečná rekurzivní volání funkce, která sama o
sobě vedou k dodatečným časovým i paměťovým nárokům vytvořeného programu. Jednoduchým
příkladem demonstrujícím zrychlení výpočtu je již zmíněná posloupnost lichých čísel. Výpočet
n-tého členu posloupnosti na základě rekurzivní definice
a1 = 1
an = an-1 + 2
pro n > 1
má lineární časovou složitost, zatímco při použití explicitního vzorce
an = 2n - 1
pro n > 0
dosáhneme složitosti konstantní. Jako ukázka úspory zbytečných rekurzivních volání nám
poslouží faktoriál. Explicitní vzorec
n! = 1.2.3. ....n
pro n > 0
vede stejně jako rekurzivní definice faktoriálu k výpočtu s lineární časovou složitostí. Je však
rychlejší o ušetřená rekurzivní volání funkce.
function Faktorial(N: integer): integer;
var I, F: integer;
begin
F := 1;
for I:=2 to N do F := F * I;
Faktorial := F
end;
10
Rekurzivní jsou i některé geometrické předpisy. V kap. 1 jsme uvedli definici tzv. Hilbertovy
křivky k-tého řádu, která je popsána složením čtyř křivek řádu o 1 nižšího. Ukážeme si nyní
program pro grafické vykreslení Hilbertovy křivky daného řádu na obrazovce počítače. Program je
založen na bezprostřední realizaci daného rekurzivního předpisu. Je zároveň hezkou ukázkou
použití nepřímé rekurze. Různě natočené segmenty vytvářené křivky jsou vykreslovány
samostatnými procedurami, které se podle potřeby navzájem volají.
program Hilbert;
{Vykreslení Hilbertovy
uses Graph;
var N: integer;
Gd, Gm: integer;
Max: integer;
H: integer;
Z: integer;
I: integer;
křivky zvoleného řádu}
{řád křivky}
{nastavení režimu grafické karty}
{rozlišení grafické karty}
{velikost úsečky}
{počet úseček na straně oblasti}
procedure UseckaDolu(H: integer);
{kreslí úsečku směrem dolů délky H bodů}
begin
LineRel(0,H)
end;
procedure UseckaNahoru(H: integer);
{kreslí úsečku směrem nahoru délky H bodů}
begin
LineRel(0,-H)
end;
procedure UseckaVlevo(H: integer);
{kreslí úsečku směrem vlevo délky H bodů}
begin
LineRel(-H,0)
end;
procedure UseckaVpravo(H: integer);
{kreslí úsečku směrem vpravo délky H bodů}
begin
LineRel(H,0)
end;
procedure
procedure
procedure
procedure
ObloukDolu (Rad,
ObloukNahoru(Rad,
ObloukVlevo (Rad,
ObloukVpravo(Rad,
H:
H:
H:
H:
integer);
integer);
integer);
integer);
forward;
forward;
forward;
forward;
procedure ObloukDolu(Rad, H: integer);
{kreslí úsek H. křivky - oblouk dolů pravotočivý}
{Rad - řád Hilbertovy křivky, H - velikost hrany}
var R: integer; {o jeden řád méně}
begin
if Rad > 0 then
begin
11
R := Rad - 1;
ObloukVlevo(R,H);
UseckaDolu(H);
ObloukDolu(R,H);
UseckaVlevo(H);
ObloukDolu(R,H);
UseckaNahoru(H);
ObloukVpravo(R,H);
end
end; {procedure ObloukDolu}
procedure ObloukNahoru(Rad, H: integer);
{kreslí úsek H. křivky - oblouk nahoru pravotočivý}
{Rad - řád Hilbertovy křivky, H - velikost hrany}
var R: integer; {o jeden řád méně}
begin
if Rad > 0 then
begin
R := Rad - 1;
ObloukVpravo(R,H);
UseckaNahoru(H);
ObloukNahoru(R,H);
UseckaVpravo(H);
ObloukNahoru(R,H);
UseckaDolu(H);
ObloukVlevo(R,H);
end
end; {procedure ObloukNahoru}
procedure ObloukVlevo(Rad, H: integer);
{kreslí úsek H. křivky - oblouk vlevo levotočivý}
{Rad - řád Hilbertovy křivky, H - velikost hrany}
var R: integer; {o jeden řád méně}
begin
if Rad > 0 then
begin
R := Rad - 1;
ObloukDolu(R,H);
UseckaVlevo(H);
ObloukVlevo(R,H);
UseckaDolu(H);
ObloukVlevo(R,H);
UseckaVpravo(H);
ObloukNahoru(R,H);
end
end; {procedure ObloukVlevo}
procedure ObloukVpravo(Rad, H: integer);
{kreslí úsek H. křivky - oblouk vpravo levotočivý}
{Rad - řád Hilbertovy křivky, H - velikost hrany}
var R: integer; {o jeden řád méně}
begin
if Rad > 0 then
begin
R := Rad - 1;
12
ObloukNahoru(R,H);
UseckaVpravo(H);
ObloukVpravo(R,H);
UseckaNahoru(H);
ObloukVpravo(R,H);
UseckaVlevo(H);
ObloukDolu(R,H);
end
end; {procedure ObloukVpravo}
begin
write('Řád Hilbertovy křivky: ');
readln(N);
Gd := Detect;
Gm := Detect;
InitGraph(Gd, Gm, '');
Max := GetMaxY; {počet bodů na obrazovce na výšku}
{počet úseček na straně oblasti pro N-tý řád: 2^N-1}
Z := 1;
for I:=1 to N do Z := Z * 2;
Z := Z - 1; {Z = počet úseček tvořících stranu}
H := Max div Z; {délka jedné úsečky}
MoveTo(Max,0);
ObloukVlevo(N,H);
readln;
CloseGraph;
end.
Jiným typickým postupem využívajícím vztahu nepřímé rekurze je jeden z algoritmů na
vyhodnocení aritmetického výrazu. Budeme mít zadán aritmetický výraz, který bude pro
jednoduchost tvořen pouze celočíselnými konstantami, binárními operátory +, -, *, / (znak / bude
představovat celočíselné dělení) a kulatými závorkami s možností libovolného vnoření do sebe.
Naším úkolem bude spočítat hodnotu tohoto výrazu.
Pro řešení této úlohy existuje řada různých postupů (viz např. [5]). Jeden z nejlepších algoritmů
s optimální lineární časovou složitostí je založen na rekurzivní definici aritmetického výrazu.
Místo přesné formální definice si řekneme raději její hlavní myšlenky. Výraz je buď člen, nebo je
to součet (příp. rozdíl) několika členů. Každý člen je buď faktor, nebo je to součin (příp. podíl)
několika faktorů. Každý faktor je buď tvořen přímo celočíselnou konstantou, nebo je to výraz
uzavřený v kulatých závorkách. V této definici je zachycen jak správný tvar zápisu výrazu, tak
také postup správného vyhodnocování s ohledem na strukturu závorek a prioritu operátorů
(násobení a dělení má vyšší prioritu než sčítání a odčítání).
Algoritmus si ukážeme naprogramovaný v Turbo Pascalu ve tvaru funkce Vyhodnoceni. Funkce
dostane ve svém parametru znakový řetězec obsahující vyhodnocovaný výraz a jako svou funkční
hodnotu vrátí hodnotu tohoto výrazu. Funkce Vyraz, Clen a Faktor, které se navzájem volají
metodou nepřímé rekurze, jsou lokálními funkcemi deklarovanými uvnitř funkce Vyhodnoceni.
Jako jediný parametr typu řetězec si předávají tu část vyhodnocovaného výrazu, která ještě zbývá
ke zpracování. Řetězec je zleva stále zkracován, až z něj zbude pouze jediný speciální znak $,
který k původně zadanému výrazu připojuje z technických důvodů sama funkce Vyhodnoceni.
program AritmetVyraz;
{Vyhodnocení aritmetického výrazu soustavou procedur
ve vztahu nepřímé rekurze podle formální gramatiky
13
popisující stavbu výrazu}
var S: string; {uložení vyhodnocovaného výrazu}
function Vyhodnoceni(S:string): integer;
{funkce vyhodnocující aritmetický výraz}
{metoda - nepřímá rekurze funkcí Vyraz, Clen, Faktor}
{vyhodnocovaný výraz je zadán ve vstupním parametru S}
{funkce předpokládá, že výraz je syntakticky správný}
function Vyraz(var S: string): integer; forward;
function Faktor(var S: string); integer;
{pomocná funkce na vyhodnocení jednoho faktoru}
{faktorem je číselná hodnota nebo výraz v závorkách}
var H: integer;
{číslo ve výrazu}
Z: boolean;
{znaménko minus u čísla}
begin
while S[1] = ' ' do Delete(S,1,1);
if S[1] = '(' then
begin
Delete(S,1,1); {zrušit levou závorku}
Faktor := Vyraz(S);
while S[1] = ' ' do Delete(S,1,1);
Delete(S,1,1); {zrušit pravou závorku}
end
else {číselná konstanta}
begin
Z := false;
if S[1] = '+' then
Delete(S,1,1)
else if S[1] = '-' then
begin
Delete(S,1,1);
Z := true
end;
H := 0;
while S[1] in ['0'..'9'] do
begin
H := H * 10 + ord(S[1]) - ord('0');
Delete(S,1,1)
end;
if Z then H := -H;
Faktor := H
end;
end; {function Faktor}
function Clen(var S: string): integer;
{pomocná funkce na vyhodnocení jednoho členu}
{členem je jeden faktor nebo součin/podíl více faktorů}
var C: integer;
{hodnota členu}
begin
C := Faktor(S);
while S[1] = ' ' do Delete(S,1,1);
while S[1] in ['*','/'] do
if S[1] = '*' then {součin faktorů}
14
begin
Delete(S,1,1);
C := C * Faktor(S);
while S[1] = ' ' do Delete(S,1,1);
end
else if S[1] = '/' then {podíl faktorů}
begin
Delete(S,1,1);
C := C div Faktor(S);
while S[1] = ' ' do Delete(S,1,1);
end;
Clen := C
end; {function Clen}
function Vyraz(var S: string): integer;
{funkce na vyhodnocení výrazu}
{výraz je člen nebo součet/rozdíl členů}
var V: integer;
{hodnota výrazu}
begin {function Vyraz}
while S[1] = ' ' do Delete(S,1,1);
V := Clen(S);
while S[1] = ' ' do Delete(S,1,1);
while S[1] in ['+','-'] do
if S[1] = '+' then {součet členů}
begin
Delete(S,1,1);
V := V + Clen(S);
while S[1] = ' ' do Delete(S,1,1);
end
else if S[1] = '-' then {rozdíl členů}
begin
Delete(S,1,1);
V := V - Clen(S);
while S[1] = ' ' do Delete(S,1,1);
end;
Vyraz := V
end; {function Vyraz}
begin {function Vyhodnoceni}
S := S + '$'; {technický trik pro ukončení}
Vyhodnoceni := Vyraz(S)
end; {function Vyhodnoceni}
begin
write('Vyhodnocovaný výraz: ');
readln(S);
writeln('Hodnota výrazu: ', Vyhodnoceni(S));
readln
end.
15
3.2. Generování všech prvků dané vlastnosti
Při řešení některých úloh je zapotřebí vygenerovat všechny prvky, k-tice, množiny či rozklady
zadané vlastnosti. Úlohy tohoto typu musíme často řešit prostým zkoušením všech možností.
Například při hledání všech k-tic celých čísel splňujících nějakou danou podmínku by však bylo
nevýhodné a zbytečně pomalé vytvořit nejprve mechanicky všechny existující k-tice čísel a
každou z nich pak dodatečně testovat, zda vyhovuje podmínce ze zadání úlohy. Lepší je vytvářet
přímo pouze vyhovující k-tice. K tomu obvykle použijeme rekurzivní proceduru, která při svém
prvním zavolání postupně umístí na první místo ve vytvářené k-tici všechna čísla, která se tam
mohou objevit, a pro každý takovýto “začátek” zajistí dokončení celé k-tice pomocí rekurzivního
volání sebe sama. Parametrem rekurzivního volání bude údaj, od kolikátého prvku je třeba
pokračovat ve vytváření k-tice. Součástí algoritmu procedury musí být samozřejmě i podmínka
pro ukončení rekurze. Jakmile bude ve vytvářené k-tici zvolena hodnota posledního, tj. k-tého
prvku, procedura místo dalšího rekurzivního volání nalezenou k-tici předá jako výsledek (někam ji
uloží nebo třeba přímo vytiskne).
Celý postup si předvedeme na několika konkrétních úlohách. Začneme příklady z kombinatoriky.
Následující programy slouží k vypsání všech k-prvkových kombinací bez opakování z N-prvkové
množiny celých čísel {1, 2, ..., N}, dále kombinací s opakováním, variací bez opakování a variací
s opakováním. Připomeňme si ještě ve stručnosti význam těchto základních kombinatorických
pojmů. K-prvkové kombinace z N prvků jsou všechny k-prvkové podmnožiny dané základní
množiny {1, 2, ..., N}, zatímco k-prvkové variace z N prvků jsou všechny uspořádané k-tice
tvořené prvky této základní množiny. U variací tedy na rozdíl od kombinací záleží na pořadí
prvků. Slova “bez opakování” a “s opakováním” udávají, zda se v kombinaci či variaci mohou
některé prvky opakovat.
Příklad: Všechny dvouprvkové kombinace, resp. variace, ze čtyř prvků vypadají následovně.
kombinace bez opakování: {1,2} {1,3} {1,4} {2,3} {2,4} {3 4}
kombinace s opakováním: {1,1} {1,2} {1,3} {1,4} {2,2} {2,3} {2,4} {3,3} {3 4} {4,4}
variace bez opakování: (1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3)
variace s opakováním: (1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)
(4,1) (4,2) (4,3) (4,4)
program KombinaceBezOpakovani;
{vypíše všechny K-prvkové kombinace bez opakování
z N prvků (1,2,...,N) pro zadané hodnoty K, N}
const MaxK = 20;
{maximální přípustné K}
var C: array[0..MaxK] of byte;
{uložení kombinace}
N, K: byte;
procedure Comb(p:byte);
{p - pořadí vytvářeného prvku kombinace}
{procedura používá globální proměnné C, K, N}
{kombinace jsou vytvářeny s prvky vzestupně uspořádanými}
var i:byte;
begin
if p > K then {hotovo}
begin
for i:= 1 to K do write(C[i]:3);
writeln
end
else {doplnit C[p]}
16
for i:=C[p-1]+1 to N-(K-p) do
begin
C[p] := i;
Comb(p+1)
end
end;
begin
write('Výpočet K-prvkových kombinací bez opakování ');
writeln('z N prvků');
write('Zadejte hodnoty K a N: ');
readln(K,N);
C[0]:=0; {technický trik}
Comb(1);
readln;
end.
program KombinaceSOpakovanim;
{vypíše všechny K-prvkové kombinace s opakováním
z N prvků (1,2,...,N) pro zadané hodnoty K, N}
const MaxK = 20;
{maximální přípustné K}
var C: array[0..MaxK] of byte;
{uložení kombinace}
N, K: byte;
procedure Comb(p:byte);
{p - pořadí vytvářeného prvku kombinace}
{procedura používá globální proměnné C, K, N}
{kombinace jsou vytvářeny s prvky vzestupně uspořádanými}
var i:byte;
begin
if p > K then {hotovo}
begin
for i:= 1 to K do write(C[i]:3);
writeln
end
else {doplnit C[p]}
for i:=C[p-1] to N do
begin
C[p] := i;
Comb(p+1)
end
end;
begin
write('Výpočet K-prvkových kombinací s opakováním ');
writeln('z N prvků');
write('Zadejte hodnoty K a N: ');
readln(K,N);
C[0]:=1; {technický trik}
Comb(1);
readln;
end.
17
program VariaceBezOpakovani;
{vypíše všechny K-prvkové variace bez opakování
z N prvků (1,2,...,N) pro zadané hodnoty K, N}
const MaxK = 20;
{maximální přípustné K}
var C: array[1..MaxK] of byte;
{uložení variace}
N, K: byte;
procedure Vari(p:byte);
{p - pořadí vytvářeného prvku variace}
{procedura používá globální proměnné C, K, N}
var i, j: byte;
nalez: boolean;
begin
if p > K then {hotovo}
begin
for i:= 1 to K do write(C[i]:3);
writeln
end
else {doplnit C[p]}
for i:=1 to N do
begin
nalez := false;
j:=1;
while not nalez and (j < p) do
begin
if C[j] = i then nalez := true
else j := j + 1
end;
if not nalez then
begin
C[p] := i;
Vari(p+1)
end
end
end;
begin
write('Výpočet K-prvkových variací bez opakování ');
writeln('z N prvků');
write('Zadejte hodnoty K a N: ');
readln(K,N);
Vari(1);
readln;
end.
program VariaceSOpakovanim;
{vypíše všechny K-prvkové variace s opakováním
z N prvků (1,2,...,N) pro zadané hodnoty K, N}
const MaxK = 20;
{maximální přípustné K}
var C: array[1..MaxK] of byte;
{uložení variace}
N, K: byte;
procedure Vari(p:byte);
{p - pořadí vytvářeného prvku variace}
18
{procedura používá globální proměnné C, K, N}
var i, j: byte;
begin
if p > K then {hotovo}
begin
for i:= 1 to K do write(C[i]:3);
writeln
end
else {doplnit C[p]}
for i:=1 to N do
begin
C[p] := i;
Vari(p+1)
end
end;
begin
write('Výpočet K-prvkových variací s opakováním ');
writeln('z N prvků');
write('Zadejte hodnoty K a N: ');
readln(K,N);
Vari(1);
readln;
end.
Dalším základním kombinatorickým pojmem jsou permutace. Permutací N-prvkové množiny
čísel {1, 2, ..., N} rozumíme každé seřazení jejích prvků do uspořádané N-tice. Existuje přesně N!
různých permutací dané N-prvkové množiny. Chceme-li je všechny vypsat, máme dvě základní
možnosti, jak lze postupovat. První řešení je rekurzivní a vychází ze skutečnosti, že permutace N
prvků jsou vlastně N-prvkové variace z daných N prvků bez opakování. Můžeme proto postupovat
stejně jako při hledání variací.
program Permutace_1;
{vypíše všechny permutace N prvků (1,2,...,N) }
{rekurzivní verze - postupné generování}
(* uses Dos; *)
const MaxN = 20;
{maximální přípustné N}
type Cisla = set of 1..MaxN;
var A: array[1..MaxN] of 1..MaxN; {uložení permutace}
N: integer; {počet prvků}
Pocet: integer;
{počet permutací}
(*
procedure WriteTime;
{Pomocná procedura pro výpis času}
var H,M,S,S100: word;
begin
GetTime(H,M,S,S100);
writeln('Čas: ',H:4,M:4,S:4,S100:4)
end; {procedure WriteTime}
*)
19
procedure Perm(p: integer; S: Cisla);
{p - pořadí vytvářeného prvku permutace}
{S - čísla dosud nepoužitá v permutaci}
{procedura používá globální proměnné A, N, Pocet}
var i: integer;
begin
if p > N then {hotovo}
begin
for i:= 1 to N do write(A[i]:3);
writeln;
Pocet := Pocet + 1
end
else {doplnit A[p]}
for i:=1 to N do
if not (i in S) then
begin
A[p] := i;
Perm(p+1, S+[i])
end
end; {procedure Perm}
begin
writeln('Výpočet permutací N prvků');
write('Zadejte hodnotu N: ');
readln(N);
Pocet := 0;
(* WriteTime; *)
Perm(1,[]);
writeln('Počet permutací: ', Pocet);
(* WriteTime; *)
readln;
end.
Druhý, nerekurzivní postup řešení je o něco šikovnější a několikanásobně rychlejší. Místo
postupného mechanického zkoušení všech možných rozložení prvků permutace pomocí rekurze
budeme vytvářet přímo celé jednotlivé permutace, a to v tzv. lexikografickém uspořádání.
Lexikografické uspořádání permutací je takové pořadí, které známe z řazení hesel ve slovníku. Ze
dvou permutací stojí dříve ta, která má menší číslo na první pozici, v případě shody na první
pozici rozhoduje menší číslo na druhém místě v permutaci zleva, atd. Například pro N=3 vypadá
lexikografické uspořádání všech permutací takto:
123
132
213
231
312
321
První v pořadí je permutace s prvky uspořádanými vzestupně, poslední permutace má prvky
seřazené v sestupném pořadí. Algoritmus na vypsání všech permutací N prvků využívá proceduru,
která ze zadané permutace N prvků vytvoří permutaci bezprostředně po ní následující
v lexikografickém uspořádání. Začneme tedy od první permutace a touto procedurou ji budeme
přetvářet tak dlouho, dokud nezískáme permutaci poslední.
Zbývá vysvětlit, jak pracuje zmíněná procedura na nalezení bezprostředně následující permutace.
Snaží se zvýšit zadanou permutaci, ale jen o co nejméně, jak je to možné. Změna se proto musí
20
odehrát v permutaci co nejvíce “vpravo”. Budeme tedy postupovat od pravého konce permutace
a1a2...aN směrem doleva a porovnávat dvojice sousedních prvků, tzn. postupně dvojice čísel
(aN-1aN), (aN-2aN-1), atd. Dokud je levý prvek takové dvojice větší než pravý, nemůžeme zatím
pro zvýšení permutace nic udělat a postupujeme dál vlevo. Jakmile najdeme poprvé dvojici
(aiai+1), v níž ai<ai+1, průchod permutací zastavíme. Prvek ai je totiž konečně tím, který
můžeme zvýšit. Hledáme nejbližší vyšší permutaci, a proto musíme ai nahradit nejbližším vyšším
z prvků ai+1, ai+2,..., aN. Nechť je to ak. Zaměníme tedy v permutaci prvky ai, ak. Zbývá již jen
uspořádat vzestupně prvky stojící vpravo od i-té pozice, aby vytvořená permutace s novou
hodnotou ai byla co nejmenší. Nemusíme ale čísla pracně třídit, neboť víme, že platí
ai+1>ai+2>...>aN-1>aN. Na tomto uspořádání nic nepokazila ani výměna prvků ai, ak, neboť za
ak bylo vybráno nejbližší vyšší číslo než bývalé ai. Stačí tedy jednoduše obrátit pořadí prvků
ai+1, ai+2,..., aN a jsme hotovi.
program Permutace_2;
{vypíše všechny permutace N prvků (1,2,...,N) }
{nerekurzivní verze - pomocí následníka v lexik. uspořádání}
(* uses Dos; *)
const MaxN = 20;
{maximální přípustné N}
type Pole = array[1..MaxN] of 1..MaxN;
var A: Pole;
{uložení permutace}
N: integer;
{počet prvků}
Pocet: integer;
{počet permutací}
i: integer;
(*
procedure WriteTime;
{Pomocná procedura pro výpis času}
var H,M,S,S100: word;
begin
GetTime(H,M,S,S100);
writeln('Čas: ',H:4,M:4,S:4,S100:4)
end; {procedure WriteTime}
*)
function Dalsi (var P: Pole): boolean;
{z permutace v poli P vytvoří nejbližší další
v lexikografickém uspořádání}
{vrací true, když se to podařilo
vrací false, pokud P obsahovalo nejvyšší permutaci}
{používá globální proměnné N, Pocet}
var i, j, k, x: integer;
begin
i := N-1;
while (i > 1) and (A[i] > A[i+1]) do i := i-1;
if A[i] > A[i+1] then
Dalsi := false
else
begin
{číslo A[i] zvětšíme - nahradíme nejbližším vyšším
číslem z úseku od A[i+1] do A[N]:}
j := N;
while A[j] < A[i] do j := j-1;
21
{vyměníme A[i] a A[j]:}
x := A[i]; A[i] := A[j]; A[j] := x;
{otočíme klesající úsek A[i+1]..A[N] na rostoucí:}
j := i+1; k := N;
while j < k do
begin
x := A[j]; A[j] := A[k]; A[k] := x;
j := j+1; k := k-1;
end;
Dalsi := true
end
end; {function Dalsi}
begin
writeln('Výpočet permutací N prvků');
write('Zadejte hodnotu N: ');
readln(N);
Pocet := 0;
for i:=1 to N do A[i] := i;
(* WriteTime; *)
repeat
for i:=1 to N do write(A[i]:3);
writeln;
Pocet := Pocet + 1
until not Dalsi(A);
writeln('Počet permutací: ', Pocet);
(* WriteTime; *)
readln;
end.
Také v následujících příkladech půjde o vytváření všech skupin zadané vlastnosti. Mějme dáno N
celých čísel bez znaménka, kde N není větší než 100. Dále je dáno celé číslo C. Naším úkolem je
doplnit k zadaným číslům znaménka “+” nebo “-” tak, aby byl jejich součet roven číslu C.
Chceme nalézt všechna přípustná řešení.
Postup řešení je podobný jako u výše uvedených kombinatorických úloh. V jednom poli budeme
mít pevně uložena sčítaná čísla, do druhého pole si budeme postupně ukládat jejich znaménka.
Vytvoříme všechny možné N-tice za znamének “+” a “-” a pro každou z nich otestujeme
odpovídající součet čísel. Sekvence znamének vytváříme rekurzivně. Jedno zavolání rekurzivní
procedury “má na starosti” volbu znaménka u jednoho z čísel. Vyzkouší obě možnosti znaménka a
pro každou z nich nechá prozkoumat všechna rozložení zbývajících znamének pomocí
rekurzivního volání. Parametrem procedury je tudíž pořadové číslo umisťovaného znaménka.
Ukončení rekurze je zajištěno kontrolou hodnoty tohoto parametru, zda nepřekročila N. Po
vytvoření celé N-tice znamének je již možné projít pole čísel a znamének a zkontrolovat výsledný
součet. Jinou stejně dobrou možností je předávat průběžný mezisoučet čísel s již stanovenými
znaménky ve druhém parametru rekurzivní procedury.
program Soucet_Cisel_V_Poli;
{Je dáno N celých čísel a požadovaný součet C.
Program doplní před každé z čísel znaménko + nebo - tak,
aby byl součet takto upravených čísel roven danému C.
Hledáme všechna možná řešení.}
const MaxN = 100;
{maximální počet čísel}
22
var H:
N:
C:
Z:
I:
array[1..MaxN] of integer;
integer;
integer;
array[1..MaxN] of char;
integer;
{sčítaná čísla}
{počet čísel}
{hledaný součet}
{uložení znamének}
procedure X (K:integer; Soucet:integer);
{K - kolikáté znaménko hledáme,
Soucet - průběžný součet čísel až do K-tého}
{Procedura používá globální proměnné N, C, H, Z}
var I:integer;
begin
if K = N+1 then {pole znamének zcela obsazeno}
begin
if Soucet = C then {našli jsme řešení}
begin
for I:=1 to N do write(Z[I],H[I]);
writeln
end
end
else {zkusíme hodnoty K-tého znaménka}
begin
Z[K] := '+';
X(K+1, Soucet+H[K]);
Z[K] := '-';
X(K+1, Soucet-H[K]);
end
end; {procedure X}
begin
write('Počet sčítaných čísel: ');
readln(N);
writeln('Sčítaná čísla: ');
for I:=1 to N do read(H[I]);
write('Požadovaný součet: ');
readln(C);
X(1, 0); {začínáme od prvního znaménka, dosud součet 0}
readln;
end.
V další úloze budeme studovat, jak mohou vypadat uzávorkování správně zapsaných
aritmetických výrazů. Uvažujeme výraz obsahující N párů závorek. Z celého výrazu nás bude
zajímat právě jen to, jaký tvar může mít struktura jeho závorek. Například pro N=3 existuje těchto
pět možností:
((()))
(()())
(())()
()(())
()()()
23
Naším úkolem bude nalézt a vypsat všechna takováto správná uzávorkování výrazu pro zadaný
počet párů závorek N.
Úlohu budeme řešit opět pomocí rekurze. Posloupnosti závorek budeme vytvářet postupně zleva
doprava. Procedura řešící úlohu převezme již vytvořenou úvodní část posloupnosti, prodlouží ji
o jednu závorku a pak zajistí dokončení celé posloupnosti rekurzivním zavoláním sebe sama.
Hloubka rekurze je omezena délkou vytvářené posloupnosti. Při každém rekurzivním zavolání je
posloupnost prodloužena o jednu závorku, takže po provedení 2N volání v sobě může procedura
místo dalšího rekurzivního volání přímo vypsat výsledek.
Musíme se ale ještě vrátit ke slovům “prodlouží ji o jednu závorku” a zamyslet se, jakou závorku
je možné k nějakému úvodnímu úseku posloupnosti přidat. V některých situacích je totiž možné
přidat jedině levou závorku, v některých pouze pravou a v některých musíme vyzkoušet obě
možnosti, chceme-li nalézt všechna přípustná řešení úlohy. Levou závorku můžeme připojit vždy,
pokud úvodní úsek ještě neobsahuje N levých závorek. Pravou závorku lze použít tehdy, jestliže je
co uzavírat, tzn. jestliže úvodní úsek obsahuje více levých závorek než pravých.
Všechno ostatní je již jenom technickou záležitostí. Vytvářenou posloupnost závorek musíme
podobně jako při řešení předchozí úlohy ukládat do pole. Toto pole musí být všemi exempláři
procedury sdíleno, a proto ho budeme deklarovat jako globální (mohlo by stát také na místě
parametru předávaného odkazem). Prostřednictvím vstupního parametru se musí procedura
dozvědět, jak dlouhý úsek posloupnosti je již vytvořen a uložen v poli. Přímo v poli by pak bylo
možné spočítat, kolik je v tomto úseku levých a kolik pravých závorek. Šikovnější je však zavést
parametry jinak a přímo v parametrech předávat proceduře informaci, kolik levých a kolik
pravých závorek úvodní úsek obsahuje. Ušetříme tím práci spojenou s opakovaným procházením
pole při každém zavolání procedury.
program Uzavorkovani;
{Vygeneruje všechna správná uzávorkování výrazu
pomocí N párů kulatých závorek}
const MaxN = 100;
{maximální přípustné N}
var Z: array[1..MaxN*2] of char; {uložení závorek}
N: integer;
{počet párů závorek}
I: integer;
procedure Zavorky(L, P: integer);
{L, P - kolik jsme už umístili levých a pravých závorek}
{používá globální proměnnou N}
begin
if L < N then {můžeme dát levou}
begin
Z[L+P+1] := '(';
Zavorky(L+1,P)
end;
if P < L then {můžeme dát pravou}
begin
Z[L+P+1] := ')';
Zavorky(L,P+1)
end;
if P = N then {uzávorkování vytvořeno}
begin
for I:=1 to 2*N do write(Z[I]);
writeln
end
end; {procedure Zavorky}
24
begin
write('Počet párů závorek: ');
readln(N);
Zavorky(0,0);
readln;
end.
Další ukázková úloha pojednává o placení. Úkolem je nalézt všechny způsoby, jimiž je možné
zaplatit danou částku pomocí dané sady platidel. Předpokládáme, že od každé hodnoty platidla
máme v zásobě dostatečný počet kusů. Úlohu si nejlépe přiblížíme na konkrétním příkladu.
Budeme uvažovat platidla o hodnotách 1 Kč, 2 Kč, 5 Kč, 10 Kč, 20 Kč a 50 Kč. Částku 12 Kč
můžeme zaplatit těmito patnácti způsoby:
1 x 10 Kč + 1 x 2 Kč
1 x 10 Kč + 2 x 1 Kč
2 x 5 Kč + 1 x 2 Kč
2 x 5 Kč + 2 x 1 Kč
1 x 5 Kč + 3 x 2 Kč + 1 x 1 Kč
1 x 5 Kč + 2 x 2 Kč + 3 x 1 Kč
1 x 5 Kč + 1 x 2 Kč + 5 x 1 Kč
1 x 5 Kč + 7 x 1 Kč
6 x 2 Kč
5 x 2 Kč + 2 x 1 Kč
4 x 2 Kč + 4 x 1 Kč
3 x 2 Kč + 6 x 1 Kč
2 x 2 Kč + 8 x 1 Kč
1 x 2 Kč + 10 x 1 Kč
12 x 1 Kč
Úlohu je možné řešit různými způsoby. Budeme-li uvažovat pouze pevnou sadu platidel nebo
alespoň sadu platidel o předem známém počtu různých hodnot, můžeme napsat řešení založené na
příslušném počtu cyklů vnořených do sebe. Pokud pracujeme s N platidly, vystačíme s N-1 cykly.
Víme-li navíc, že je mezi platidly vždy jednokoruna, takže libovolnou celou částku bude možné
zaplatit, budeme v těchto cyklech zkoumat všechny přípustné počty vyšších platidel, uvnitř cyklů
pak doplatíme zbytek částky jednokorunami a vytiskneme výsledek. Pokud by nebylo zaručeno, že
jednokoruna bude v sadě platidel obsažena, museli bychom do vnitřního cyklu doplnit navíc jeden
test pro kontrolu, zda má úloha řešení.
program Platidla_1;
{Zaplatit danou částku všemi způsoby danou sadou platidel.
Nerekurzivní verze s pevným počtem platidel.
První hodnotou platidla je vždy 1, dalších pět hodnot
platidel je zadáno na vstupu.}
var H1, H2, H3, H4, H5, H6: integer; {hodnoty platidel}
P1, P2, P3, P4, P5, P6: integer; {počty platidel}
25
Z1, Z2, Z3, Z4, Z5, Z6: integer; {zbývá zaplatit}
Zapl: integer; {počet různých zaplacení}
begin
writeln('Nejmenší platidlo hodnoty 1 se nezadává');
H1 := 1;
write('Hodnoty dalších 5 platidel: ');
readln(H2, H3, H4, H5, H6);
write('Částka k zaplacení: ');
readln(Z6);
Zapl := 0;
for P6:=0 to Z6 div H6 do
begin
Z5 := Z6 - P6 * H6;
for P5:=0 to Z5 div H5 do
begin
Z4 := Z5 - P5 * H5;
for P4:=0 to Z4 div H4 do
begin
Z3 := Z4 - P4 * H4;
for P3:=0 to Z3 div H3 do
begin
Z2 := Z3 - P3 * H3;
for P2:=0 to Z2 div H2 do
begin
Z1 := Z2 - P2 * H2;
P1 := Z1; {neboť H1 = 1}
write(P1,' x ',H1,' + ',P2,' x ',H2,' + ');
write(P3,' x ',H3,' + ',P4,' x ',H4,' + ');
writeln(P5,' x ',H5,' + ',P6,' x ',H6);
Zapl := Zapl + 1;
end
end
end
end
end;
writeln('Počet možných zaplacení: ', Zapl);
readln;
end.
Právě popsané řešení s velkým množstvím cyklů vnořených do sebe není zrovna nejelegantnější.
Nemůžeme ho navíc použít v případě, je-li úloha zadána zcela obecně a předem neznáme počet
druhů platidel, s nimiž je třeba pracovat. V této situaci nám opět pomůže rekurze. Každé zavolání
procedury bude odpovídat jednomu z platidel, hloubka rekurze bude tedy omezena počtem
platidel. Procedura vyzkouší v cyklu všechny vhodné počty toho platidla, které “má na starosti”, a
pro každý z těchto počtů zajistí doplacení zbývající částky dalšími platidly pomocí rekurzivního
volání.
Údaje o počtech platidel jednotlivých druhů v právě vytvářeném rozkladu se budou opět ukládat
do globálního pole. Parametry procedury budou pořadové číslo právě zkoumaného platidla a
částka, která ještě zbývá k zaplacení. Ukážeme si dvě varianty řešení. První z nich je jednodušší a
předpokládá, že každá použitá sada platidel obsahuje jednokorunu. Druhé řešení je zcela obecné.
program Platidla_2;
26
{Zaplatit danou částku všemi způsoby danou sadou platidel.
Rekurzivní verze s obecným počtem platidel.
První hodnotou platidla je vždy 1, další platidla jsou
dána na vstupu.}
const Max = 100;
{maximální počet platidel}
var H: array[1..Max] of integer; {hodnoty platidel}
P: array[1..Max] of integer; {počty platidel}
N: integer;
{počet platidel}
Castka: integer;
{částka k zaplacení}
Zapl: integer;
{počet různých zaplacení}
i: integer;
procedure Plat(J, Z: integer);
{J - index právě používaného platidla
Z- zbývá ještě zaplatit}
{používá globální proměnné H, P, N}
var i: integer;
begin
if J = 1 then
begin
P[1] := Z; {neboť H[1]=1}
for i:=1 to N-1 do write(P[i],' x ',H[i],' + ');
writeln(P[N],' x ',H[N]);
Zapl := Zapl + 1;
end
else
for i:=0 to Z div H[J] do
begin {i = počet použitých platidel indexu J}
P[J] := i;
Plat(J-1, Z-i*H[J])
end
end; {procedure Plat}
begin
write('Počet platidel: ');
readln(N);
writeln('Nejmenší platidlo hodnoty 1 se nezadává');
H[1] := 1;
write('Hodnoty dalších ', N-1, ' platidel: ');
for i:=2 to N do read(H[i]);
write('Částka k zaplacení: ');
readln(Castka);
Zapl := 0;
Plat(N, Castka);
writeln('Počet možných zaplacení: ', Zapl);
readln;
end.
program Platidla_3;
{Zaplatit danou částku všemi způsoby danou sadou platidel.
Rekurzivní verze s obecným počtem platidel.
Sada platidel nemusí obsahovat platidlo s hodnotou 1.}
const Max = 100;
{maximální počet platidel}
var H: array[1..Max] of integer; {hodnoty platidel}
27
P: array[1..Max] of integer;
N: integer;
Castka: integer;
Zapl: integer;
i: integer;
{počty platidel}
{počet platidel}
{částka k zaplacení}
{počet různých zaplacení}
procedure Plat(J, Z: integer);
{J - index právě používaného platidla
Z- zbývá ještě zaplatit}
{používá globální proměnné H, P, N}
var i: integer;
begin
if J = 1 then
begin
if Z mod H[1] = 0 then
begin {zaplacení je možné}
P[1] := Z div H[1];
for i:=1 to N-1 do write(P[i],' x ',H[i],' + ');
writeln(P[N],' x ',H[N]);
Zapl := Zapl + 1;
end
end
else
for i:=0 to Z div H[J] do
begin {i = počet použitých platidel indexu J}
P[J] := i;
Plat(J-1, Z-i*H[J])
end
end; {procedure Plat}
begin
write('Počet platidel: ');
readln(N);
write('Hodnoty všech ', N, ' platidel: ');
for i:=1 to N do read(H[i]);
write('Částka k zaplacení: ');
readln(Castka);
Zapl := 0;
Plat(N, Castka);
if Zapl = 0 then
writeln('Částku ', Castka,
' nelze touto sadou platidel zaplatit')
else
writeln('Počet možných zaplacení: ', Zapl);
readln;
end.
V poslední úloze této kapitoly budeme chtít nalézt všechny rozklady daného kladného celého čísla
na součty kladných celých čísel. Rozklady přitom nepovažujeme za různé, jestliže se liší pouze
pořadím svých sčítanců. Např. pro zadané číslo N=5 může výsledek vypadat takto (nezáleží na
pořadí rozkladů ani na pořadí sčítanců v rámci každého rozkladu):
5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1
28
Bylo by dost nešikovné generovat všechny možné rozklady zadaného čísla N lišící se třeba jen
pořadím sčítanců a až dodatečně vybírat ty z nich, které jsou opravdu různé. Abychom získali
rovnou pouze navzájem různé rozklady, použijeme při jejich vytváření stejný trik jako v úloze o
generování všech kombinací: připustíme pouze takové rozklady, které mají sčítance uspořádané
(např. sestupně - viz příklad výše). K vytváření rozkladů nám poslouží rekurzivní procedura. Její
parametry budou udávat, jakou hodnotu je ještě třeba rozložit a kolik sčítanců již má právě
vytvářený rozklad. Procedura prodlouží aktuální rozklad všemi možnými způsoby o jeden sčítanec
a dále zajistí rozložení zbytku rekurzivním voláním sebe sama. Přidávaný sčítanec může být
nejvýše roven dosud poslednímu sčítanci v rozkladu a zároveň nejvýše roven hodnotě, kterou ještě
máme na rozložení. Hloubka rekurze bude určena počtem členů rozkladu a pro různé rozklady
bude různá. Nejvýše je však rovna N v případě rozkladu zadaného čísla N na samé jedničky.
program RozkladCisla;
{Zadané kladné celé číslo N rozloží všemi způsoby na součet
kladných celých čísel. Na pořadí sčítanců nezáleží.
Např.: 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1}
const Max = 100;
{maximální přípustné N}
var N: integer;
{rozkládané číslo}
A: array[0..Max] of integer; {uložení rozkladu}
function Min(A, B: integer): integer;
{pomocná procedura na výpočet minima z dvou celých čísel A, B}
begin
if A > B then Min := B else Min := A
end;
procedure Rozloz(Zbytek, P:integer);
{Zbytek = kolik zbývá rozložit,
P = kolikátý sčítanec vytváříme }
var I: integer;
begin
if Zbytek = 0 then {rozklad je hotov}
begin
for I:=1 to P-1 do write(A[I]:3);
writeln
end
else {přidat další člen rozkladu - v pořadí P-tý}
begin
for I:=Min(Zbytek, A[P-1]) downto 1 do
begin
A[P] := I;
Rozloz(Zbytek-I, P+1)
end;
end;
end; {procedure Rozloz}
begin {Hlavní program}
write('Rozkládané číslo (1-',Max,'): ');
readln(N);
A[0] := Max+1; {technický trik}
Rozloz(N, 1); {rozložit celé N, začínáme 1. sčítancem}
end.
29
3.3. Prohledávání s návratem
Programovací techniku zvanou prohledávání s návratem, prohledávání do hloubky nebo krátce a
jednoduše backtracking bychom mohli charakterizovat jako hledání řešení postupným zkoušením
všech možností. Těmi “možnostmi” přitom může být ledacos - různé varianty dalšího pokračování
výpočtu, různé cesty v grafu, po nichž se můžeme vydat, různé tahy ve hře, které můžeme ve
zkoumané situaci provést. Postupujeme do hloubky v tom smyslu, že z více možných pokračování
jedno ihned provedeme a ostatní si zapamatujeme na pozdější dobu. V nové situaci se opět
rozhodneme pro jedno možné pokračování výpočtu a všechna zbývající si uložíme. Takto
postupujeme tak dlouho, až buď najdeme řešení, nebo zjistíme, že zvolená cesta je špatná a
k řešení nevede. V tom případě se vrátíme do předchozí pozice a je-li v ní zaznamenáno ještě
nějaké neprozkoumané pokračování výpočtu, vyzkoušíme ho. Pokud jsme již všechna možná
pokračování výpočtu vyzkoušeli, opět se vracíme do předcházející situace. Výpočet končí buď ve
chvíli, kdy najdeme nějaké řešení (pokud je úkolem nalézt jedno libovolné řešení) nebo po
prohledání všech možných cest (pokud máme nalézt všechna řešení úlohy nebo pokud žádné
řešení úlohy neexistuje).
Programová realizace prohledávání do hloubky bývá typicky založena na rekurzivní proceduře.
Proceduře je v parametrech předána informace o aktuální situaci. Procedura nejprve zjistí, zda tato
situace není cílová. Jestliže ne, vyhledá všechna možná pokračování, zaznamená je ve zvoleném
pořadí a v cyklu postupně zkouší provést jedno po druhém. Provedením každého z těchto kroků
vždy vznikne nová situace, na jejíž zpracování je rekurzivně zavolána tatáž procedura. Po
vyčerpání všech možných pokračování výpočet procedury končí.
Prohledávání do hloubky je podrobněji vysvětleno ve výše uvedených učebnicích, kde také
najdete řešení různých ilustrujících úloh. My si ho nyní předvedeme na jiném příkladu. Naším
úkolem bude umístit na čtvercovou šachovnici o rozměrech N x N daný počet šachových koňů tak,
aby jimi byla pokryta všechna pole šachovnice. Řekneme, že pole šachovnice je pokryto, pokud na
něm stojí kůň nebo pokud ho alespoň jeden kůň ohrožuje. Pro zvolenou velikost šachovnice a
počet koňů chceme nalézt všechna rozmístění koňů na šachovnici splňující podmínky úlohy.
Řešením úlohy bude rekurzivní procedura Kun, která dostane ve vstupním parametru informaci,
kolik koňů je ještě třeba umístit na šachovnici a do které části šachovnice se mají pokládat.
Procedura vyzkouší všechna možná umístění jednoho koně a pro každou jeho přípustnou pozici
volá rekurzivně sama sebe k prozkoumání možných umístění zbývajících koňů. Hloubka rekurze
je určena celkovým počtem koňů. Koně zkoušíme umisťovat na šachovnici postupně po řádcích
vždy zleva doprava. Po každém rozmístění všech koňů zkontrolujeme, zda jsou pokryta všechna
pole šachovnice.
program Kone;
{Úkolem je umístit na šachovnici NxN daný počet šachových
koňů tak, aby pokrývali všechna pole, tj. na každém poli
kůň buď stojí, nebo je pole ohrožováno}
{Metoda řešení: úplný backtracking}
uses Dos;
const N = 5; {velikost šachovnice}
Pocet = 5; {počet koňů}
var S: array[-1..N+2, -1..N+2] of byte;
{reprezentace šachovnice: 0 = volné pole
1 = kůň stojí na poli
2 = pole ohroženo koněm }
{z technických důvodů připojen okraj šířky 2 pole }
Tah: array[1..8] of
record d1, d2: integer end; {možné tahy koně}
30
i, j: integer;
procedure Test(i, j: integer);
{Obnoví hodnotu S[i,j], momentálně je to 1 nebo 2}
var l: integer; {směry pohybu koně}
volno: boolean;
begin
if (i>=1) and (i<=N) and (j>=1) and (j<=N) then
if S[i,j] = 2 then
begin
volno := true;
for l:=1 to 8 do
if S[i+Tah[l].d1, j+Tah[l].d2] = 1 then
volno := false;
if volno then S[i,j] := 0
end
end; {procedure Test}
procedure Tisk;
{Přehledný tisk nalezeného řešení podle obsahu pole S}
var i, j: integer;
begin
write('+-');
for j:=1 to N do write('--');
writeln('+');
for i:=1 to N do
begin
write('| ');
for j:=1 to N do
if S[i,j] = 1 then write('* ')
else write(' ');
writeln('|')
end;
write('+-');
for j:=1 to N do write('--');
writeln('+');
writeln
end; {procedure Tisk}
procedure Kun(P, K: integer);
{Umístí v pořadí P-tého koně za pole číslo K}
{Šachovnice je číslována od 1 po řádcích}
var i, j, l: integer; {i=řádek, j=sloupec, l=směr}
Sij: byte;
{stará hodnota S[i,j]}
Reseni: boolean;
{příznak nalezení řešení úlohy}
begin
if P > Pocet then
{už tam jsou všechny koně}
begin
Reseni := true;
for i:=1 to N do
for j:=1 to N do
if S[i,j] = 0 then Reseni := false;
if Reseni then {nalezeno řešení úlohy}
Tisk
end
31
else {umisťujeme dalšího koně}
repeat
K := K+1; {další zkoumané pole}
i := (K-1) div N + 1; {řádek pole K}
j := (K-1) mod N + 1; {sloupec pole K}
Sij := S[i,j]; {uschovat hodnotu - 0 nebo 2}
S[i,j] := 1; {zkusíme tam dát koně}
for l:=1 to 8 do
if S[i+Tah[l].d1, j+Tah[l].d2] = 0 then
S[i+Tah[l].d1, j+Tah[l].d2] := 2; {ovládané pole}
Kun(P+1,K);
S[i,j] := Sij;
for l:=1 to 8 do
Test(i+Tah[l].d1, j+Tah[l].d2); {obnovení hodnot}
until K = N*N - Pocet + P;
end; {procedure Kun}
procedure WriteTime;
{Pomocná procedura pro výpis času}
var H,M,S,S100: word;
begin
GetTime(H,M,S,S100);
writeln('Čas: ',H:4,M:4,S:4,S100:4)
end; {procedure WriteTime}
begin {program}
{inicializace pole tahů koněm:}
Tah[1].d1 := 1; Tah[1].d2 := 2;
Tah[2].d1 := 2; Tah[2].d2 := 1;
Tah[3].d1 := 2; Tah[3].d2 := -1;
Tah[4].d1 := 1; Tah[4].d2 := -2;
Tah[5].d1 := -1; Tah[5].d2 := -2;
Tah[6].d1 := -2; Tah[6].d2 := -1;
Tah[7].d1 := -2; Tah[7].d2 := 1;
Tah[8].d1 := -1; Tah[8].d2 := 2;
{inicializace šachovnice:}
for i:=1 to N do
for j:=1 to N do S[i,j] := 0;
{vlastní výpočet všech možných rozmístění:}
WriteTime;
writeln('Čekejte, probíhá výpočet');
Kun(1,0);
WriteTime;
end.
Jestliže tento program spustíte na počítači, lehce si sami prakticky ověříte, jak je metoda
backtrackingu pomalá. Počet operací provedených při výpočtu roste v exponenciální závislosti na
velikosti vstupních dat. Při řešení rozsáhlých úloh je proto prohledávání do hloubky prakticky
nepoužitelné. Konkrétně zde uvedený program při výpočtu na běžném počítači typu PC proběhne
velmi rychle ještě pro čtyři koně na šachovnici o rozměrech 4x4, ale pro čtyři koně na šachovnici
velké 5x5 polí potřebuje k výpočtu řádově desítky sekund aby zjistil, že úloha nemá řešení.
Nalezení všech řešení v případě pěti koní na šachovnici 5x5 již trvá několik minut, pro vyšší
hodnoty doba výpočtu prudce narůstá.
32
Všimněte si, že také všechna řešení úloh uvedená v kap. 3.2 měla charakter prohledávání do
hloubky. Úkolem vždy bylo určit všechna řešení zadané úlohy. Výpočet proto nebyl ukončen po
nalezení některého řešení, ale pokračoval dál návratem k předchozímu stavu a zkoušením dalších
možností.
3.4. Rozděl a panuj
Metoda zvaná “rozděl a panuj” je další typickou rekurzivní technikou používanou při návrhu
algoritmů. Lze ji ovšem použít pouze pro jistou omezenou třídu úloh. Spočívá v tom, že řešenou
úlohu rozdělíme na dvě nebo více dílčích podúloh, které jsou menší a proto snadnější. Podúlohy
jsou stejného charakteru jako původní úloha a vyřešíme je proto rekurzivním voláním téhož
algoritmu. Důležitá je skutečnost, že podúlohy jsou na sobě zcela nezávislé, znalost řešení některé
z nich nám nepomůže při řešení žádné jiné. Proto také vůbec nezáleží na pořadí, v jakém dílčí
podúlohy zpracováváme. Je-li některá z podúloh již zcela elementární, místo rekurzivního volání
ji vyřešíme přímým výpočtem. Po vyřešení všech podúloh vzniklých z původní úlohy získáme
výsledné řešení vhodným spojením výsledků podúloh. Mechanismus opakovaného rekurzivního
volání tedy vede k tomu, že se původní zadaná úloha postupně rozdrobí až na samé elementární
dílčí úlohy a z jejich výsledků se pak zpětně sestavují výsledky úloh větších, dokud nedostaneme
výsledek celé původně řešené úlohy.
Metoda rozděl a panuj je podrobně vysvětlena v [5]. Její použití je tam demonstrováno na třech
poměrně známých úlohách, a to na třídicích algoritmech quicksort a mergesort (třídění sléváním)
a na řešení problému Hanojských věží. Ukážeme si proto, jak se dá metodou rozděl a panuj vyřešit
jiná úloha. Již v závěru kap. 3.1 jsme se seznámili s úkolem vyhodnotit aritmetický výraz. Tehdy
jsme k jeho vyřešení použili nepřímou rekurzi. Tutéž úlohu nyní snadno vyřešíme technikou
rozděl a panuj. Toto řešení bude mít kratší a jednodušší zápis, vede však k trochu pomalejšímu
výpočtu.
Pravidla pro vyhodnocování aritmetického výrazu stanoví, že pořadí vyhodnocování určují v první
řadě závorky. Na stejné závorkové úrovni jsou operátory vyhodnocovány podle priorit (násobení a
dělení mají vyšší prioritu než sčítání a odčítání) a operátory téže priority jsou zpracovávány zleva
doprava. Se znalostí těchto zásad není těžké nalézt ve zkoumaném aritmetickém výrazu operátor,
který bude vyhodnocen až jako poslední. Je to operátor stojící zcela mimo závorky, co nejnižší
priority a mezi více takovými ten, který je umístěn nejvíce vpravo. K nalezení operátoru těchto
vlastností vystačíme s jedním postupným průchodem výrazem. Může se ale stát, že se ve výrazu
žádný operátor nenachází zcela mimo závorky. K tomu může dojít ve dvou případech: buď je již
celý výraz tvořen jenom jediným operandem určujícím přímo hodnotu výrazu, nebo je výraz jako
celek uzavřen do závorek, které jsou z hlediska svého významu zcela zbytečné. Tyto vnější
závorky v takovém případě odstraníme a hledání operátoru zopakujeme v upraveném výrazu. Po
určení naposledy vyhodnocovaného operátoru konečně přichází ke slovu metoda rozděl a panuj.
Výraz v místě nalezeného operátoru rozdělíme na levou a pravou část, každý z takto vzniklých
podvýrazů vyhodnotíme rekurzivním uplatněním téhož vyhodnocovacího algoritmu a s jejich
výsledky pak již jenom provedeme závěrečnou aritmetickou operaci určenou nalezeným
operátorem.
Řešení si ukážeme naprogramované v Turbo Pascalu. Zkoumaný výraz bude pro jednoduchost
uložen v proměnné S typu znakový řetězec. Rekurzivní funkce Hodnota zajišťuje realizaci metody
rozděl a panuj. Pomocná funkce Znamenko slouží k nalezení polohy toho operátoru ve výrazu,
který bude vyhodnocován až jako poslední. Funkce Znamenko zároveň ze zkoumaného výrazu
odstraňuje nadbytečné vnější závorky, a to případně i opakovaně. Rovněž funkce Znamenko je
rekurzivní.
33
program AritmetickyVyraz;
{Vyhodnocení aritmetického výrazu rekurzivně metodou
rozděl a panuj. Výraz je zadán na vstupu, obsahuje
celočíselné konstanty, binární operátory +,-,*,/ a
kulaté závorky. Znak / představuje celočíselné dělení.
Obvyklý postup vyhodnocení: podle závorek, podle priorit,
operátory stejné priority zleva doprava.
Předp.: zápis výrazu nemá celkem více než 255 znaků,
může být tedy uložen ve stringu.}
var S: string; {zpracovávaný výraz}
function Znamenko(var S: string): integer;
{Ve výrazu S určí index výskytu znaménka naposledy
prováděného operátoru, přitom z S odstraní vnější
nadbytečné závorky. Není-li v S už žádné znaménko,
vrací nulu}
var Plus, Krat: integer;
{poloha posledního operátoru}
Zavorky: integer;
{bilance závorek}
i: integer;
begin
Plus := 0;
Krat := 0;
Zavorky := 0;
for i:=1 to length(S) do
case S[i] of
'(': Zavorky := Zavorky + 1;
')': Zavorky := Zavorky - 1;
'+', '-': if Zavorky = 0 then Plus := i;
'*', '/': if Zavorky = 0 then Krat := i;
end;
if Plus > 0 then
Znamenko := Plus
else if Krat > 0 then
Znamenko := Krat
else if S[1] <> '(' then
Znamenko := 0
else
begin
S := Copy(S, 2, length(S)-2); {odstranit vnější závorky}
Znamenko := Znamenko(S)
end
end; {function Znamenko}
function Hodnota(var S: string): integer;
{Určí hodnotu výrazu uloženého v S}
var Z: integer;
{poloha znaménka}
S1, S2: string;
{levý a pravý úsek od znaménka}
H: integer;
{výsledná hodnota}
C: integer;
{pomocné pro proceduru Val}
begin
Z := Znamenko(S);
if Z = 0 then
Val(S, H, C)
else
34
begin
S1 := Copy(S, 1, Z-1);
S2 := Copy(S, Z+1, length(S)-Z);
case S[Z] of
'+': H := Hodnota(S1) + Hodnota(S2);
'-': H := Hodnota(S1) - Hodnota(S2);
'*': H := Hodnota(S1) * Hodnota(S2);
'/': H := Hodnota(S1) div Hodnota(S2);
end
end;
Hodnota := H
end; {function Hodnota}
begin
write('Vyhodnocovaný výraz: ');
readln(S);
writeln('Hodnota výrazu: ', Hodnota(S));
readln;
end.
35
4. Rekurzivní datové struktury
Dosud jsme se zabývali použitím rekurze v programování na úrovni algoritmů a příkazů.
Rekurzivní charakter ale mají také některé datové struktury. Tyto struktury jsou vytvářeny
z dynamicky alokovaných záznamů spojených navzájem pomocí ukazatelů. Podrobnější výklad
dynamických datových struktur, jejich významu, použití a způsobu manipulace s nimi je uveden
v knihách [5] a [8]. Zde se proto omezíme jen na stručný pohled na ně z hlediska rekurze.
Nejjednodušší dynamickou datovou strukturou je lineární spojový seznam. Je tvořen záznamy,
které kromě vlastních uložených informací obsahují jeden ukazatel na záznamy téhož typu:
type PUzel = ^TUzel;
Tuzel = record
Info: T; {uložená informace}
Dalsi: PUzel
end;
Lineární spojový seznam je sestaven z posloupnosti takovýchto záznamů s pevně stanoveným
pořadím. První záznam ukazuje na druhý, druhý na třetí, atd. Poslední záznam v seznamu má
v položce Dalsi dosazenu speciální konstantu nil (neboť na žádný další záznam neukazuje).
Lineární spojový seznam je možné chápat také rekurzivně. Seznam je buď prázdný (je tvořen
pouze konstantou nil), nebo je tvořen prvním prvkem obsahujícím odkaz na zbytek seznamu.
Zbytek seznamu je opět seznam, tzn. je už prázdný, nebo je tvořen prvkem s odkazem na zbytek
tohoto seznamu, atd.
Chceme-li projít celým lineárním spojovým seznamem a v každém jeho uzlu provést jistou akci,
můžeme použít rekurzivní proceduru odpovídající přesně rekurzivní definici seznamu. Celá akce
průchodu seznamem spočívá ve zpracování prvního uzlu v seznamu a v následném provedení téže
akce (tj. rekurzivním voláním téže procedury) pro zbytek seznamu. V Pascalu můžeme zapsat
příslušnou proceduru takto:
procedure Pruchod1(P: PUzel);
{P = ukazatel na začátek zpracovávaného lin. spoj. seznamu}
begin
if P <> nil then
begin
Akce(P); {provedení nějaké akce v uzlu P^}
Pruchod1(P^.Dalsi)
end
end;
Použití rekurze je však v tomto případě zbytečné, stejného výsledku dosáhneme snáze zavoláním
následující nerekurzivní procedury. Rekurze je v ní nahrazena cyklem.
procedure Pruchod2(P: PUzel);
{P = ukazatel na začátek zpracovávaného lin. spoj. seznamu}
begin
while P <> nil do
begin
Akce(P); {provedení nějaké akce v uzlu P^}
P := P^.Dalsi
end
36
end;
Složitější datovou strukturou rekurzivní povahy je binární strom. Každý vrchol stromu obsahuje
vedle vlastní uložené informace dva ukazatele na vrcholy téhož typu:
type PVrchol = ^TVrchol;
TVrchol = record
Info: T; {uložená informace}
L, R: PVrchol
end;
Binární strom je tvořen z více vrcholů tohoto typu. Obsahuje jeden význačný vrchol zvaný kořen,
z něho vede odkaz na levého a pravého následníka, z nich zase odkazy na jejich následníky atd.
Jestliže některý z vrcholů některého následníka nemá, příslušný ukazatel nabývá hodnoty nil.
Binární strom lze rekurzivně popsat tak, že je buď prázdný (je tvořen konstantou nil), nebo je
tvořen jedním vrcholem obsahujícím odkazy na jeho levý a pravý podstrom. Každý z podstromů je
opět stromem, tzn. je buď už prázdný, nebo je tvořen vrcholem s odkazy na levý a pravý
podstrom.
Pro zápis průchodu všemi uzly binárního stromu můžeme opět použít rekurzi. Ta bude přesně
kopírovat rekurzivní definici stromu. Provést jistou akci v každém vrcholu binárního stromu
znamená provést tuto akci v kořenu stromu a poté zajistit provedení téže akce ve všech vrcholech
nejprve levého a pak pravého podstromu pomocí dvojího rekurzivního volání. Tento rekurzivní
postup procházení binárním stromem je hezkým jednoduchým příkladem programové techniky
prohledávání s návratem, s níž jsme se seznámili v kap. 3.3. Proceduru si nyní zapíšeme v jazyce
Pascal:
procedure Pruchod3(P: PUzel);
{P = ukazatel na kořen zpracovávaného binárního stromu}
begin
if P <> nil then
begin
Akce(P); {provedení nějaké akce v uzlu P^}
Pruchod3(P^.L);
Pruchod3(P^.R)
end
end;
Operace se stromy mají přirozeně rekurzivní charakter. Případné odstranění rekurze je v tomto
případě o dost komplikovanější, než tomu bylo u lineárních spojových seznamů. Musíme si
v programu vytvořit pomocný zásobník, který nahradí mechanismus rekurzivních volání. Zásobník
bude sloužit k odkládání informací o tom, které podstromy původního stromu je ještě třeba
procházet. Na začátku výpočtu vložíme do zásobníku jediný záznam - ukazatel na celý strom.
Výpočet bude probíhat tak dlouho, dokud se zásobník zcela nevyprázdní. Nerekurzivní verzi
procedury Pruchod3 označenou jako Pruchod4 si zapíšeme pouze schematicky, bez detailního
naprogramování operací se zásobníkem.
procedure Pruchod4(P: PUzel);
{P = ukazatel na kořen zpracovávaného binárního stromu}
var Zasob: TZasobnik;
37
begin
Vyprazdni(Zasob); {prázdný zásobník}
if P <> nil then Vloz(Zasob,P); {vložení P do zásobníku}
while Neprazdny(Zasob) do
begin
P := Vezmi(Zasob);
Akce(P); {provedení nějaké akce v uzlu P^}
if P^.R <> nil then Vloz(Zasob, P^.R);
if P^.L <> nil then Vloz(Zasob, P^.L)
end
end;
Seznámili jsme se alespoň ve stručnosti se dvěma nejdůležitějšími rekurzivními datovými
strukturami, tj. s lineárními spojovými seznamy a binárními stromy. Podobným způsobem
pracujeme i s obecnými stromy a s dalšími složitějšími dynamickými datovými strukturami, které
mají rovněž rekurzivní charakter.
38
5. Efektivita rekurzivních postupů
Již v kap. 2 a v kap. 3.1 jsme se zmínili o tom, že neuvážené použití rekurzivního postupu
v programu vede často k velmi pomalému výpočtu. To však neznamená, že by každý rekurzivní
program musel být také neefektivní a že bychom se měli rekurzi zcela vyhýbat. Měli bychom však
každé použití rekurze pečlivě zvažovat právě z hlediska rychlosti výpočtu výsledného programu.
Zaměříme se nyní na tři základní oblasti, co je možné dělat s velkou časovou náročností některých
rekurzivních řešení úloh. První z nich je zrychlení výpočtu rekurzivního algoritmu pomocí pole,
do kterého ukládáme již jednou spočítané hodnoty, druhou oblastí je nahrazení rekurzivních
volání procedur nebo funkcí cyklem a pomocným zásobníkem a konečně třetí možností je
nahrazení rekurzivního postupu řešení zcela jiným nerekurzivním postupem, který pracuje
rychleji.
Problematice efektivity rekurzivních algoritmů je věnována také samostatná kapitola v knize [5].
V úvodních partiích učebnic [4] a [5] naleznou zájemci rovněž vysvětlení, co to vůbec efektivita
algoritmů je, jak se vyjadřuje, k čemu slouží její studium při praktické tvorbě programů a jaký je
vztah mezi časovými a paměťovými nároky programů.
5.1. Zrychlení rekurze
Příliš pomalý výpočet některých rekurzivních programů je způsoben tím, že se v něm zbytečně
mnohokrát opakuje výpočet již jednou spočítaných hodnot. Jako klasický příklad nám zde
poslouží výpočet n-tého Fibonacciho čísla. V kap. 1 jsme si přesně definovali posloupnost
Fibonacciho čísel rekurzivním předpisem
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2
pro n>1.
Chceme-li počítat v pořadí n-té Fibonacciho číslo pro různá zadaná n, můžeme snadno napsat
rekurzivní funkci prostým přepsáním uvedené definice do Pascalu:
function Fib1(n: integer): integer;
begin
if (n=0) or (n=1) then Fib1 := n
else Fib1 := Fib1(n-1) + Fib1(n-2)
end;
Zavolání takové funkce v programu však vede k výpočtu s exponenciální časovou složitostí, takže
pro větší n je funkce prakticky nepoužitelná. Můžete si sami snadno vyzkoušet na počítači, jak se
s rostoucí hodnotou n prodlužuje doba výpočtu. Pro prvních deset až patnáct nejmenších hodnot je
ještě výpočet funkce Fib1 dostatečně rychlý. Vyšší hodnoty již vedou ke znatelnému zpomalení
výpočtu a pro hodnoty n kolem 30 až 50 (podle rychlosti počítače) se již výsledku v rozumném
čase nedočkáme. Například volání Fib1(20) způsobí zavolání Fib1(19) a Fib1(18), přitom
Fib1(19) potřebuje nejprve spočítat Fib1(18) a Fib1(17) atd. Již zde vidíme, že velmi pracný
výpočet hodnoty Fib1(18) se bude zcela zbytečně odehrávat dvakrát, hodnota Fib1(17) se bude
počítat třikrát, Fib1(16) dokonce pětkrát atd.
39
Zásadního zrychlení výpočtu dosáhneme zavedením pomocného pole, v němž si budeme
uchovávat všechny již jednou získané hodnoty. Algoritmus výpočtu zůstane zachován v podstatě
beze změn, jenom před každým rekurzivním voláním do tohoto pole nahlédneme a pokud je tam
hledaná hodnota již uložena, nepočítáme ji znovu. Funkce bude tedy zavolána pro každou hodnotu
svého parametru nejvýše jednou. Tím jsme rázem získali řešení úlohy s lineární časovou
složitostí.
Funkce Fib2 si zachovává stejnou strukturu jako měla Fib1, je jen doplněna pomocným globálním
polem F:
const Max = ...
var F: array[0..Max] of integer;
F[0] := 0;
F[1] := 1;
for i:=2 to Max do F[i]:=-1; {nedefinovaná hodnota}
function Fib2(n: integer);
begin
if F[n] = -1 then {zatím neznáme}
F[n] := Fib2(n-1) + Fib2(n-2);
Fib2 := F[n]
end;
Uvedený postup je zcela obecný a lze ho samozřejmě použít i pro výpočet hodnot jiných
rekurzivně definovaných funkcí. Jedinou nevýhodou tohoto řešení je nutnost deklarovat předem
velikost pomocného pole a tím tedy vlastně omezit použitelnost výsledného programu pouze na
určitý předem pevně stanovený rozsah vstupních hodnot.
5.2. Nahrazení rekurzivních volání zásobníkem
Zatímco zrychlování výpočtu vysvětlené v kap. 5.1 mělo zásadní charakter a mohlo změnit
rychlost výpočtu programu třeba z exponenciální na lineární, nyní nám půjde jen o technickou
maličkost, která rychlost řádově neovlivňuje. Jestliže pro zápis rekurzivního algoritmu nechceme
použít rekurzivní volání procedur nebo funkcí, můžeme tento mechanismus v programu nahradit
vlastním zásobníkem a cyklem. Místo aktivačních záznamů ukládaných do systémového
zásobníku při každém zavolání procedury či funkce budeme přímo v programu ukládat příslušné
údaje do našeho programového zásobníku. Pro programátora to znamená více práce, výsledný
program bude mít delší a obvykle i méně přehledný zápis. Rekurzivní charakter algoritmu však
zůstává zachován.
Z hlediska rychlosti výpočtu, která je nyní ve středu naší pozornosti, znamená nahrazení
rekurzivních volání operacemi s programovým zásobníkem mírné zrychlení. Vlastní výpočty se
nijak nezměnily, ušetřil se ale čas potřebný pro realizaci každého zavolání nebo ukončení
procedury.
S konkrétním příkladem tohoto postupu jste se již setkali v závěru kap. 4, kde jsme uvedli
rekurzivní a nerekurzivní verzi procedury na průchod binárním stromem.
40
5.3. Odstranění rekurzivního postupu
V poslední části kap. 5 se budeme věnovat možnosti zcela se vyhnout rekurzivnímu algoritmu
řešení úlohy. To je ovšem možné pouze tehdy, známe-li nějaký odlišný, nerekurzivní postup
řešení, který navíc není příliš komplikovaný ve srovnání s rekurzivním algoritmem. V takové
situaci by bylo použití rekurze buď zbytečné, nebo dokonce nevhodné. Na rozdíl od úprav
uvedených v kap. 5.1 a 5.2, které měly charakter obecných programátorských technik
použitelných analogicky v mnoha různých úlohách, nalezení odlišného způsobu řešení je pokaždé
novým tvůrčím úkolem pro programátora.
Porovnáme nyní různé varianty řešení několika konkrétních úloh. Začneme u počítání našich
známých Fibonacciho čísel, jimiž jsme se zabývali již v kap. 5.1. Tam jsme uvedli jednak
jednoduchou rekurzivní funkci Fib1 s exponenciální časovou složitostí, jednak vylepšené řešení
Fib2, které díky pomocnému poli dosahuje složitosti lineární. Fibonacciho čísla ale můžeme
počítat také zcela jinak. Místo rekurzivního výpočtu podle vzorce budeme raději v cyklu postupně
počítat jednotlivá Fibonacciho čísla počínaje od nejmenšího. Každé Fibonacciho číslo je rovno
součtu dvou předchozích, takže v programu vystačíme se třemi proměnnými: ve dvou si
uchováváme poslední dvě hodnoty, do třetí proměnné ukládáme hodnotu novou rovnou součtu
obou předchozích. Získáme tak celkem snadno nerekurzivní řešení s lineární časovou složitostí a
navíc s konstantními paměťovými nároky.
function Fib3(n: integer): integer;
var x, y, z: integer; {poslední tři Fibonacciho čísla}
i: integer;
{počítadlo Fibonacciho čísel}
begin
y := 0;
z := 1;
i := 1;
while i < n do
begin
x := y; y := z; z := x + y;
i := i + 1
end;
Fib3 := z
end;
S jinými příklady, v nichž jsme zlepšili řešení úlohy odstraněním rekurzivního postupu, jste se již
setkali v předchozích kapitolách. V kap. 2 jsme zapsali rekurzivní funkci pro výpočet faktoriálu,
v kap. 3.1 jsme výpočet faktoriálu zrychlili jednoduchým nahrazením rekurze cyklem. V kap. 4
jsme zase uvedli zbytečně rekurzivní proceduru Pruchod1 sloužící k procházení lineárním
spojovým seznamem. Vzápětí jsme ji nahradili procedurou Pruchod2, která řeší stejný úkol
rychleji pomocí cyklu. V kap. 3.2 jsme uvedli dva rozdílné postupy, jak určit všechny permutace
N prvků. Nerekurzivní varianta řešení počítala několikanásobně rychleji.
Také v následujících poněkud rozsáhlejších příkladech půjde o odstranění mechanického použití
rekurzivního postupu řešení úlohy. Namísto backtrackingu (prohledávání do hloubky)
s exponenciální časovou složitostí dojdeme vždy k mnohem rychlejšímu řešení s časovou
složitostí polynomiální. Zrychlení výpočtu dosáhneme obvykle za cenu nějakých dodatečných
paměťových nároků. Uvidíme, že ve všech případech budou naše vylepšené programy používat
pomocná pole k průběžnému ukládání dílčích mezivýsledků.
41
Je dána konečná posloupnost celých čísel. Počet čísel v posloupnosti N není větší než sto.
Podposloupností vybranou ze zadané posloupnosti čísel rozumíme jakoukoliv skupinu daných N
čísel, v níž zůstane zachováno stejné vzájemné pořadí jako v původní posloupnosti. Například
z posloupnosti 4, 8, 2, 3, 6, 10, 1, 5, 7, 9 je možné vybrat podposloupnost 8, 2, 5, 9. Naproti tomu
2, 8, 5, 9 není vybranou podposloupností z dané posloupnosti, neboť nedodržuje původní pořadí
prvků. Úkolem je určit délku nejdelší rostoucí podposloupnosti vybrané ze zadané posloupnosti
čísel. V našem příkladě by správným výsledkem bylo číslo 5, neboť nejdelší vybraná rostoucí
podposloupnost 2, 3, 5, 7, 9 má pět prvků.
Se zadáním úlohy o nejdelší vybrané rostoucí podposloupnosti jste se mohli setkat již v knihách
[4] a [6], přičemž v [4] je publikováno i jedno její vzorové řešení. Budeme se teď proto touto
úlohou zabývat z trochu jiného pohledu a ukážeme si řešení odlišná.
Nejjednodušší algoritmus řešení úlohy patří do kategorie “generování všech prvků”, o které jsme
hovořili v kap. 3.2. Postupně budeme vytvářet všechny možné vybrané rostoucí podposloupnosti a
budeme porovnávat jejich délky. Po prozkoumání všech takových podposloupností budeme jistě
znát délku nejdelší z nich. Řešení úlohy naprogramujeme pomocí rekurze. Vybraná rostoucí
podposloupnost může začínat kterýmkoli prvkem dané posloupnosti. Každý již vybraný rostoucí
úsek se musíme pokusit prodloužit všemi možnými způsoby vždy až do nalezení podposloupnosti,
jejíž prodloužení není možné. Rekurzivní procedura Vyber tedy převezme již nalezenou vybranou
rostoucí podposloupnost (na začátku výpočtu prázdnou) a postupně ji zkusí prodloužit všemi
možnými způsoby. Sama vždy přidá k podposloupnosti jedno větší číslo a další prodloužení zajistí
rekurzivním voláním sama sebe.
program VybranaRostouci1;
{Úkol: v posloupnosti N čísel určit délku nejdelší
rostoucí vybrané podposloupnosti.
Metoda řešení: backtracking - zkoušení všech možných
výběrů rostoucí podposloupnosti.}
const Max = 100;
{maximální počet čísel}
var A: array[0..Max] of integer; {uložení čísel}
N: integer;
{počet všech čísel}
M: integer;
{výsledek}
I: integer;
procedure Vyber(J, D: integer);
{hledá všechny rostoucí vybrané podposloupnosti
z N prvků pole A
J - index posledního vybraného prvku v úseku
D - momentální délka již vybraného úseku
používá globální proměnné A, N, M
metoda: rekurzivně postupně volí vždy J-tý prvek výběru}
var I: integer; {index nového prvku ve výběru}
begin
if D > M then M := D; {nová maximální délka úseku}
for I:=J+1 to N do
if A[I] > A[J] then {lze prodloužit}
Vyber(I, D+1)
end; {procedure Vyber}
begin
write('Počet čísel: ');
readln(N);
write('Zpracovávaná posloupnost ', N, ' čísel: ');
42
for I:=1 to N do read(A[I]);
A[0] := -maxint; {pomocná technická záležitost}
M := 0;
Vyber(0, 0);
write('Délka maximální rostoucí vybrané ');
writeln('podposloupnosti: ', M);
end.
Úlohu je možné ještě zobecnit. Můžeme požadovat, aby program určil nejen délku nejdelší
rostoucí vybrané podposloupnosti, ale aby také vypsal tuto nalezenou podposloupnost. V zadané
posloupnosti se může nacházet více různých rostoucích vybraných podposloupností stejné
maximální délky. My zde žádáme o nalezení pouze jednoho řešení.
Toto zobecnění si vyžádá doplnit do programu dvě globální celočíselná pole velikosti N. Do pole
X si budeme průběžně ukládat vždy právě zkoumanou rostoucí vybranou podposloupnost, ve
druhém poli Y budeme mít stále uloženu dosud nejdelší rostoucí vybranou podposloupnost. Ta má
v každém okamžiku délku M. Kdykoliv v programu zvýšíme hodnotu proměnné M, našli jsme
delší podposloupnost a uložíme ji z pole X do pole Y.
program VybranaRostouci2;
{Úkol: v posloupnosti N čísel určit nejdelší rostoucí
vybranou podposloupnost (nalézt jedno řešení).
Metoda řešení: backtracking - zkoušení všech možných
výběrů rostoucí podposloupnosti.}
const Max = 100;
{maximální počet čísel}
var A: array[0..Max] of integer; {uložení čísel}
N: integer;
{počet všech čísel}
M: integer;
{výsledek}
X, Y: array[1..Max] of integer;
{aktuální a maximální vybraná podposloupnost}
I: integer;
procedure Vyber(J, D: integer);
{hledá všechny rostoucí vybrané podposloupnosti
z N prvků pole A
J - index posledního vybraného prvku v úseku
D - momentální délka již vybraného úseku
používá globální proměnné A, N, M, X, Y
metoda: rekurzivně postupně volí vždy J-tý prvek výběru}
var I: integer;
begin
if D > M then
begin
M := D; {nová maximální délka}
Y := X; {uložení maximální podposloupnosti}
end;
for I:=J+1 to N do
if A[I] > A[J] then {lze prodloužit}
begin
X[D+1] := A[I]; {prodloužení podposloupnosti}
Vyber(I, D+1)
end
end; {procedure Vyber}
43
begin
write('Počet čísel: ');
readln(N);
write('Zpracovávaná posloupnost ', N, ' čísel: ');
for I:=1 to N do read(A[I]);
A[0] := -maxint; {pomocná technická záležitost}
M := 0;
Vyber(0, 0);
write('Délka maximální rostoucí vybrané ');
writeln('podposloupnosti: ', M);
writeln('Jedna rostoucí podposloupnost maximální délky:');
for I:=1 to M do write(Y[I], ' ');
writeln
end.
Rychlejší řešení úlohy získáme při použití pomocného celočíselného pole velikosti N. Pro
jednoduchost si nejprve ukážeme řešení původní úlohy, kdy nás zajímala pouze délka nejdelší
rostoucí vybrané podposloupnosti, ale nikoli podposloupnost samotná. Pomocné pole označíme
symbolem D. Hodnota D[J] bude pro každé J od 1 do N udávat délku nejdelší rostoucí vybrané
podposloupnosti začínající J-tým prvkem zkoumané posloupnosti čísel. Po zaplnění celého pole D
snadno určíme hledaný výsledek jako maximum z čísel uložených v D. Zbývá už jenom ukázat,
jak můžeme spočítat hodnoty D[J]. Je to snadné, pokud je budeme určovat od konce, tzn. od D[N]
do D[1]. Začneme tím, že položíme D[N]=1, neboť nejdelší rostoucí podposloupnost vybraná
z jednoprvkové posloupnosti A[N] má jistě délku 1. Předpokládejme nyní, že již známe hodnoty
D[J+1], ..., D[N] a chceme spočítat D[J]. Musíme nalézt co nejdelší rostoucí podposloupnost,
kterou je možné připojit za prvek A[J]. Hledáme tedy takové K z rozmezí od J+1 do N, aby A[K] >
A[J] a přitom D[K] bylo co největší. Hodnotu D[J] potom určíme jako D[K]+1. Jestliže mezi
prvky A[J+1], ..., A[N] není žádný větší než A[J], nejdelší vybraná rostoucí podposloupnost
začínající číslem A[J] je jednoprvková a položíme tudíž D[J]=1.
Popsané řešení má kvadratickou časovou složitost. Postupně počítáme N prvků pole D, výpočet
každého z nich vyžaduje provést řádově až N operací. Existuje dokonce ještě o něco rychlejší
řešení, ale nám toto plně postačí. Časově optimalizované řešení úlohy můžete nalézt v knize [4].
program VybranaRostouci3;
{Úkol: v posloupnosti N čísel určit délku nejdelší
rostoucí vybrané podposloupnosti.
Metoda řešení: pomocné pole délek vybraných
rostoucích podposloupností s různými začátky.}
const Max = 100;
{maximální počet čísel}
var A: array[1..Max] of integer; {uložení čísel}
N: integer;
{počet všech čísel}
D: array[1..Max] of integer; {délky podposloupností}
M: integer;
{výsledek}
Nejvetsi: integer;
{největší hodnota D}
I, J, K: integer;
{pomocné}
begin
write('Počet čísel: ');
readln(N);
write('Zpracovávaná posloupnost ', N, ' čísel: ');
for I:=1 to N do read(A[I]);
D[N] := 1; {nejdelší počínaje A[N] má délku 1}
M := 1; {zatím nejdelší má délku 1}
44
for J:=N-1 downto 1 do {počítáme D[J]}
begin
Nejvetsi := 0;
for K:=J+1 to N do
if A[K] > A[J] then
if D[K] > Nejvetsi then
Nejvetsi := D[K]; {A[K] je následníkem A[J]}
D[J] := Nejvetsi + 1;
if D[J] > M then M := D[J] {nalezena delší podposl.}
end;
write('Délka maximální rostoucí vybrané ');
writeln('podposloupnosti: ', M);
end.
Také toto nerekurzivní řešení můžeme upravit, aby program vypisoval i nalezenou nejdelší
vybranou rostoucí podposloupnost. Úprava je v tomto případě dokonce ještě snadnější. Zavedeme
si vedle pole D ještě jedno pomocné pole P stejné velikosti. Hodnota P[J] bude určovat, kolikátý
prvek posloupnosti následuje za A[J] v nejdelší rostoucí vybrané podposloupnosti začínající
prvkem A[J]. Čísla P[J] budeme snadno určovat souběžně s počítáním hodnot D[J]. Je totiž
P[J]=K právě pro to K, pomocí něhož jsme určili novou hodnotu D[J].
program VybranaRostouci4;
{Úkol: v posloupnosti N čísel určit nejdelší rostoucí
vybranou podposloupnost (nalézt jedno řešení).
Metoda řešení: pomocné pole délek vybraných
rostoucích podposloupností s různými začátky.}
const Max = 100;
{maximální počet čísel}
var A: array[1..Max] of integer; {uložení čísel}
N: integer;
{počet všech čísel}
D: array[1..Max] of integer; {délky podposloupností}
P: array[1..Max] of integer; {čísla následníků}
M: integer;
{výsledek}
Zacatek: integer;
{první prvek výsledku}
Nejvetsi: integer;
{největší hodnota D}
I, J, K: integer;
{pomocné}
begin
write('Počet čísel: ');
readln(N);
write('Zpracovávaná posloupnost ', N, ' čísel: ');
for I:=1 to N do read(A[I]);
D[N] := 1; {nejdelší počínaje A[N] má délku 1}
M := 1; {zatím nejdelší má délku 1}
Zacatek := N; {...a začíná prvkem A[N]}
for J:=N-1 downto 1 do {počítáme D[J]}
begin
Nejvetsi := 0;
for K:=J+1 to N do
if A[K] > A[J] then
if D[K] > Nejvetsi then
begin
Nejvetsi := D[K]; {A[K] je následníkem A[J]}
P[J] := K
end;
45
D[J] := Nejvetsi + 1;
if D[J] > M then
begin
M := D[J]; {nalezena delší rostoucí podposloupnost}
Zacatek := J {začíná prvkem A[J]}
end
end;
write('Délka maximální rostoucí vybrané ');
writeln('podposloupnosti: ', M);
writeln('Jedna rostoucí podposloupnost maximální délky:');
J := Zacatek;
for I:=1 to M do
begin
write(A[J], ' ');
J := P[J] {index následníka v podposloupnosti}
end;
writeln
end.
Také naše závěrečná úloha bude pojednávat o posloupnosti celých čísel. Je dána konečná
posloupnost celých čísel a jedno celé číslo C. Počet čísel v posloupnosti N není větší než sto. Ze
zadaných čísel vyberte takovou skupinu, jejíž součet je přesně roven danému C. Při řešení rozlište
dva případy podle toho, zda posloupnost může obsahovat libovolná celá čísla nebo zda obsahuje
pouze čísla kladná. Ve druhém případě můžeme tutéž úlohu zformulovat také názorněji jako
plnění batohu. Úkolem je z daných N předmětů o známých celočíselných objemech vybrat
takovou skupinu, která přesně zaplní batoh o známém objemu C.
Nejprve budeme řešit obecnější úlohu a budeme předpokládat, že se v zadané posloupnosti mohou
vyskytovat i záporná čísla. K řešení použijeme metodu backtrackingu, pomocí níž postupně
vyzkoušíme všechny podmnožiny dané množiny čísel. Program napíšeme takovým způsobem, aby
vyhledával všechna řešení úlohy. Ukážeme si dva různé přístupy, jak je možné rekurzivní
prohledávání všech možností postavit. Obě metody jsou rovnocenné a vedou samozřejmě ke
stejným výsledkům. Procedura Soucet1 zkouší postupně všemi možnými způsoby volit ze
zadaných čísel J-tý prvek výběru pro J = 1, 2, ... atd. Po každém zvětšení skupiny vybraných čísel
testuje, zda součet skupiny není roven C. Procedura Soucet2 přistupuje k řešení z opačného konce.
Postupně prochází všechna zadaná čísla a každé z nich zkusí do výběru buď zařadit nebo
nezařadit. Rovnost součtu vybrané skupiny čísel hodnotě C testuje pokaždé, když rozhodne o
zařazení nebo nezařazení posledního z čísel.
program Batoh1;
{Úkol: z posloupnosti N čísel vybrat skupinu se součtem
rovným dané hodnotě C.
Metoda řešení: backtracking - zkoušení všech možných
výběrů podmnožiny z daných čísel.
Program určí všechna přípustná řešení úlohy.}
const Max = 100; {maximální počet čísel}
var A: array[1..Max] of integer; {uložení čísel}
V: array[1..Max] of 1..Max;
{indexy vybraných čísel}
N: integer;
{počet všech čísel}
P: integer;
{počet vybraných čísel}
C: integer;
{požadovaný součet}
R: integer;
{počet řešení}
I: integer;
46
procedure Tisk(P: integer);
{tiskne řešení připravené v prvních P prvcích pole V}
{používá obsah globálních polí A, V, zvyšuje hodnotu R}
var I: integer;
begin
write(A[V[1]]);
for I:=2 to P do
begin
if A[V[I]] >= 0 then write('+');
write(A[V[I]])
end;
writeln;
R := R+1
end; {procedure Tisk}
procedure Soucet1(J, S: integer);
{hledá všechny možné výběry čísel z N prvků pole A
J - index do V, který prvek právě vybíráme
S - průběžný mezisoučet již vybraných prvků
používá globální proměnné A, N, V, C
metoda: rekurzivně postupně volí vždy J-tý prvek výběru}
var I: integer; {prvek A[I] zvolen na místo V[J]}
begin
if J = 1 then
for I:=1 to N do
begin
V[1] := I;
if A[I] = C then Tisk(1);
if I < N then Soucet1(2, A[I])
end
else
for I:=V[J-1]+1 to N do
begin
V[J] := I;
if S + A[I] = C then Tisk(J);
if I < N then Soucet1(J+1, S + A[I])
end
end; {procedure Soucet1}
procedure Soucet2(J, S: integer);
{hledá všechny možné výběry čísel z N prvků pole A
J - index zkoumaného čísla v poli A
S - průběžný mezisoučet již vybraných prvků
používá globální proměnné A, N, V, C, P
metoda: rekurzivně postupně zkoumá vždy J-tý prvek pole A
a zkusí ho do výběru zařadit nebo nezařadit}
begin
P := P+1;
V[P] := J;
if J < N then
Soucet2(J+1, S+A[J]) {číslo A[J] zařazeno do výběru}
else {J = N ...výběr čísel je ukončen}
if S+A[J] = C then Tisk(P);
P := P-1;
47
if J < N then
Soucet2(J+1, S) {číslo A[J] nezařazeno do výběru}
else {J = N ...výběr čísel je ukončen}
if S = C then Tisk(P);
end; {procedure Soucet2}
begin
write('Počet čísel: ');
readln(N);
write('Zpracovávaná posloupnost ', N, ' čísel: ');
for I:=1 to N do read(A[I]);
write('Požadovaný součet: ');
readln(C);
R := 0;
Soucet1(1,0);
{ R := 0;
P := 0;
Soucet2(1,0); }
{podle zvolené metody řešení lze
použít jednu nebo druhou proceduru}
if R = 0 then
writeln('Úloha nemá řešení')
else
writeln('Počet řešení: ', R);
end.
Jestliže předem víme, že všechna zkoumaná čísla budou kladná, můžeme výpočet urychlit pomocí
ořezávání neperspektivních cest. Ve vytváření výběru čísel budeme pokračovat vždy jen tak
dlouho, dokud průběžně počítaný součet vybraných čísel nepřekročí hodnotu C. Pokud je součet
několika zatím vybraných čísel již větší než C a víme přitom, že všechna čísla jsou kladná, další
přidávání čísel do této skupiny rozhodně nemůže vést k řešení. Tuto větev proto ihned opustíme a
budeme pokračovat ve výpočtu zkoumáním jiných variant výběru čísel. Ořezávání sice může vést
k významnému zrychlení výpočtu, ale algoritmus má i v tomto případě exponenciální časovou
složitost a z hlediska svých časových nároků není proto prakticky použitelný pro řešení
rozsáhlejších úloh.
Variantu řešení s ořezáváním si ukážeme již jen v jedné verzi. Následující procedura Soucet3 je
drobnou modifikací procedury Soucet2. Obdobným způsobem bylo samozřejmě možné upravit
také proceduru Soucet1.
procedure Soucet3(J, S: integer);
{modifikace procedury Soucet2 pro případ, že jsou všechna
zkoumaná čísla kladná - zrychlení výpočtu ořezáváním
neperspektivních cest}
begin
if S = C then
Tisk(P) {nalezeno řešení úlohy}
else if (S < C) and (J <= N) then
begin
P := P+1;
V[P] := J;
Soucet3(J+1, S+A[J]); {číslo A[J] zařazeno do výběru}
P := P-1;
Soucet3(J+1, S) {číslo A[J] nezařazeno do výběru}
48
end
end; {procedure Soucet3}
V případě, že jsou všechna zkoumaná čísla kladná a že nám stačí nalézt jedno řešení, můžeme
postupovat úplně jinak než dosud. Použijeme metodu dynamického programování, která vede
k řešení mnohem rychlejšímu, k řešení s polynomiální časovou složitostí.
Princip metody si názorně vysvětlíme s využitím formulace úlohy o zaplňování batohu daného
objemu C. Budeme souběžně sledovat, jak by bylo možné co nejvíce zaplnit batohy o objemech 1,
2, 3, ..., C. Budeme brát jeden předmět po druhém v libovolném pořadí a pomocí každého dalšího
předmětu se vždy pokusíme zvětšit zaplnění všech uvažovaných batohů. Nejlepší zaplnění batohu
velikosti J pomocí prvních I předmětů získáme následující úvahou: Předpokládejme, že známe
nejlepší možná zaplnění všech batohů pomocí prvních I-1 předmětů. Nyní dostáváme navíc
k dispozici ještě I-tý předmět. Pokud je tento předmět větší než J, do J-tého batohu se nevejde a
nejlepší možné zaplnění batohu velikosti J prvními I předměty je proto stejné jako zaplnění
prvními I-1 předměty. V opačném případě buď k zaplnění batohu velikosti J nový I-tý předmět
nepoužijeme, nebo ho použijeme. Z obou možností si vybereme tu příznivější, která vede
k většímu zaplnění batohu. Nyní nám už jenom zbývá popsat tyto dvě možnosti. Jestliže se
rozhodneme I-tý předmět nepoužít, bude zaplnění J-tého batohu stejné jako dosud, tj. jako při
optimálním zaplnění prvními I-1 předměty. Jestliže naopak I-tý předmět do J-tého batohu vložíme,
můžeme snadno spočítat zbývající volný prostor v tomto batohu jako rozdíl J minus velikost
I-tého předmětu. Tento volný prostor potřebujeme co nejlépe zaplnit prvními I-1 předměty. To
však již umíme, neboť optimální zaplnění všech různých menších batohů prvními I-1 předměty
známe.
Celý výpočet skončí ve chvíli, kdy zpracujeme všechny předměty a získáme tak informace o
nejlepším zaplnění všech uvažovaných batohů libovolnými ze zadaných předmětů. Údaj
zaznamenaný u největšího batohu o objemu C udává, jak nejlépe je možné zaplnit tento batoh.
Je-li roven hodnotě C, přesné zaplnění batohu je možné, v opačném případě možné není.
V tuto chvíli již víme, zda je možné batoh o dané velikosti C zcela zaplnit. Jestliže ano, nemáme
však ještě nalezeno toto zaplnění. K jeho získání si budeme během celého výpočtu evidovat pro
každý z batohů, který předmět jsme do něj vložili jako poslední. Tato zaznamenaná hodnota se
změní pokaždé, když zlepšíme zaplnění tohoto batohu. Skupinu předmětů, které přesně zaplňují
batoh o objemu C, pak již snadno získáme ve druhé fázi výpočtu. Přímo u batohu C je
zaznamenáno číslo posledního předmětu. Odečtením jeho velikosti od C dostaneme zbývající
objem D. U batohu velikosti D je zaznamenáno, který předmět byl do něj vložen jako poslední při
jeho nejlepším možném zaplnění. Odečteme tedy objem tohoto předmětu od D a dále postupujeme
stejným způsobem až do získání všech předmětů, tj. do nulového zbytkového objemu.
Programová realizace uvedeného algoritmu je poměrně snadná. Program je v podstatě tvořen
dvěma vnořenými cykly. Vnější cyklus postupně prochází zadaných N předmětů, pro každý z nich
se ve vnitřním cyklu přepočítává údaj o maximálním možném zaplnění batohů o objemech od 1 do
C. Program nemá ani příliš velké paměťové nároky. Vystačíme se dvěma pracovními poli o C
složkách. V jednom poli si budeme evidovat pro každý z batohů hodnotu jeho zatím nejlepšího
zaplnění, ve druhém poli bude uloženo pořadové číslo předmětu, který jsme do batohu vložili jako
poslední.
program Batoh2;
{Úkol: z posloupnosti N čísel vybrat skupinu se součtem
rovným dané hodnotě C (přesně naplnit batoh velikosti C).
Metoda řešení: dynamické programování.
Předpoklad: všechna zadaná čísla jsou kladná
49
(představují velikosti předmětů ukládaných do batohů).
Program určí jedno řešení úlohy.}
const MaxN = 100;
{maximální počet předmětů}
MaxC = 1000;
{maximální velikost batohu}
var A: array[1..MaxN] of integer; {velikosti předmětů}
Z: array[0..MaxC] of integer; {zaplnění pomocných batohů}
U: array[1..MaxC] of integer;
{pro každý batoh číslo naposledy vloženého předmětu}
N: integer;
{počet předmětů}
C: integer;
{velikost batohu}
ZZ: integer;
{možnost nového zaplnění}
I, J: integer;
begin
write('Počet předmětů: ');
readln(N);
write('Velikosti ', N, ' předmětů: ');
for I:=1 to N do read(A[I]);
write('Velikost batohu: ');
readln(C);
for J:= 0 to C do Z[J] := 0; {batohy jsou prázdné}
for I:=1 to N do {bereme postupně předměty}
for J:=C downto 1 do {batohy od největšího!}
if A[I] <= J then {I-tý předmět se vejde}
begin
ZZ := A[I] + Z[J-A[I]];
{ZZ teď udává nejlepší možné nové zaplnění J-tého
batohu, pokud I-tý předmět opravdu použijeme}
if ZZ > Z[J] then {vyplatí se ho použít}
begin
Z[J] := ZZ;
U[J] := I
end
end;
if Z[C] < C then
writeln('Úloha nemá řešení')
else
begin {výpis vybraných předmětů}
J := C;
while J > 0 do
begin
write(A[U[J]],' ');
J := J - A[U[J]]
end;
writeln
end;
end.
Metoda dynamického programování není rekurzivní, takže do učebnice o rekurzi patří jen
okrajově jako ukázka toho, kde a jak je účelné rekurzi z programu odstranit. Podrobněji se s ní
můžete seznámit například v učebnici [5], kde také naleznete další ilustrující příklady. Dynamické
programování má stejnou základní myšlenku jako rekurzivní metoda “rozděl a panuj” popsaná
v kap. 3.4., a sice to, že se řešení úlohy skládá z řešení dílčích podúloh stejného typu. Na rozdíl od
techniky “rozděl a panuj” zde však podúlohy nejsou navzájem nezávislé, ale využívají další
50
společné dílčí podúlohy. Vyplatí se proto neřešit úlohu rekurzivním rozkladem shora, ale naopak
postupovat iteračně zdola od řešení elementárních podúloh k větším, až se z nich nakonec složí
řešení celé úlohy. Každá z dílčích podúloh bude takto řešena pouze jednou a její výsledek může
být zaznamenán a opakovaně využit v dalším výpočtu, zatímco při rekurzivním řešení bychom
některé opakující se dílčí podúlohy řešili zbytečně vícekrát. To by mohlo vést k velmi prudkému
růstu časové náročnosti výpočtu. S tímto jevem jsme se ostatně již setkali na samém začátku této
kapitoly, když jsme srovnávali různé postupy výpočtu Fibonacciho čísel.
51
Download

Rekurze (P. Töpfer)