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+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
