Radek Pelánek
Programátorská cvičebnice
Computer Press Brno 2012
Programátorská cvičebnice Radek Pelánek Obálka: Martin Sodomka Odpovědný redaktor: Martin Herodek Technický redaktor: Jiří Matoušek Objednávky knih: http://knihy.cpress.cz www.albatrosmedia.cz
[email protected] bezplatná linka 800 555 513 ISBN 978-80-251-3751-2 Vydalo nakladatelství Computer Press v Brně roku 2012 ve společnosti Albatros Media a. s. se sídlem Na Pankráci 30, Praha 4. Číslo publikace 16 440. © Albatros Media a. s. Všechna práva vyhrazena. Žádná část této publikace nesmí být kopírována a rozmnožována za účelem rozšiřování v jakékoli formě či jakýmkoli způsobem bez písemného souhlasu vydavatele. 1. vydání
Obsah
Prˇedmluva
7
1
O knize ´ lohy a jejich popisky . . . . . . . . . . . . . . . . . . . . . . . . 1.1 U 1.2 Jak knihu pouzˇ´ıvat . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Sce´na´rˇe pouzˇitı´ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9 10 12 13
2
Prˇehled pojmu˚ 2.1 Slozˇitost . . . . . . . . . . . . . . . . . 2.2 Rekurze a metoda rozdeˇl a panuj . . . 2.3 Dynamicke´ programova´nı´ . . . . . . . 2.4 Hladove´ algoritmy . . . . . . . . . . . 2.5 Hruba´ sı´la a heuristiky . . . . . . . . . 2.6 Grafy a stavove´ prostory . . . . . . . . 2.7 Objektoveˇ orientovane´ programova´nı´ 2.8 Grafika . . . . . . . . . . . . . . . . . .
. . . . . . . .
17 17 18 19 19 20 21 21 22
. . . . . . . . . .
25 25 26 27 30 31 34 35 36 38 40
3
Pocˇ´ıta´nı´ s cˇı´sly 3.1 Hra´tky s cˇ´ısly . . . . . . . . . . 3.2 Posloupnosti . . . . . . . . . . . 3.3 Collatzu˚v proble´m . . . . . . . 3.4 Na´hodna´ procha´zka . . . . . . 3.5 Deˇlitelnost a prvocˇ´ısla . . . . . 3.6 Reprezentace cˇ´ısel . . . . . . . . 3.7 Fibonacciho posloupnost . . . . 3.8 Pascalu˚v troju´helnı´k . . . . . . 3.9 Vy´pocˇet π . . . . . . . . . . . . 3.10 Permutace, kombinace, variace
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
4 4
5
6
7
Obsah Obra´zky a geometrie 4.1 Textova´ grafika . . . . . 4.2 Zˇelvı´ grafika: za´klady . . 4.3 Zˇelvı´ grafika: frakta´ly . . ´ ´ ho frakta´l . . . 4.4 Sierpinske 4.5 Bitmapova´ grafika . . . . 4.6 Mandelbrotova mnozˇina 4.7 Konvexnı´ obal . . . . . . 4.8 Triangulace . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
43 44 45 48 50 52 54 57 59
Sˇifrova´nı´ a pra´ce s textem 5.1 Analy´za a imitace textu . 5.2 Transpozicˇnı´ sˇifry . . . . 5.3 Substituce a ko´dova´nı´ . 5.4 Rozlomenı´ sˇifer . . . . . 5.5 Prˇesmycˇky . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
63 63 66 69 70 73
Logicke´ u´lohy 6.1 Cˇ´ıselne´ bludisˇteˇ . . . . . . . . . . . 6.2 Prˇele´va´nı´ vody . . . . . . . . . . . 6.3 Hanojske´ veˇzˇe . . . . . . . . . . . . 6.4 Pokry´va´nı´ mrˇ´ızˇky . . . . . . . . . . 6.5 Hleda´nı´ cest v bludisˇti . . . . . . . 6.6 Generova´nı´ bludisˇt’ . . . . . . . . . 6.7 Rozmist’ova´nı´ figur na sˇachovnici . 6.8 Jak navsˇtı´vit vsˇechna pole mrˇ´ızˇky? 6.9 Polyomina . . . . . . . . . . . . . . 6.10 Sudoku . . . . . . . . . . . . . . . . 6.11 Sokoban . . . . . . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
75 76 77 79 82 83 84 86 89 91 94 97
Hry 7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
99 100 102 103 105 107 108 110 111 112
Ka´men, nu˚zˇky, papı´r . . . Ha´da´nı´ cˇ´ısla . . . . . . . . Obeˇsˇenec . . . . . . . . . . Logik . . . . . . . . . . . . Hra Nim . . . . . . . . . . Tetris . . . . . . . . . . . . Jednorozmeˇrne´ pisˇkvorky Pisˇkvorky . . . . . . . . . Souboje virtua´lnı´ch robotu˚
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
Obsah 8
9
5
Klasicke´ informaticke´ proble´my 8.1 Rozmeˇnˇova´nı´ mincı´ . . . . . . . . . . 8.2 Simula´tor hry Zˇivot . . . . . . . . . . 8.3 Proble´my s rˇeteˇzci a posloupnostmi 8.4 Experimenty s rˇadicı´mi algoritmy . . 8.5 Vyhodnocova´nı´ vy´razu˚ . . . . . . . . 8.6 Grafove´ algoritmy . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
117 117 119 122 123 125 127
Dalsˇı´ na´meˇty 9.1 Generova´nı´ a transformace obra´zku˚ . . . . . . . 9.2 Blı´zke´ body . . . . . . . . . . . . . . . . . . . . . 9.3 Akcˇnı´ hry . . . . . . . . . . . . . . . . . . . . . . . 9.4 Implementace datovy´ch struktur . . . . . . . . . 9.5 Implementace matematicky´ch operacı´ . . . . . . 9.6 Zpracova´nı´ a analy´za rea´lny´ch dat . . . . . . . . 9.7 Interpret jednoduche´ho programovacı´ho jazyka
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
131 131 132 133 134 134 135 135
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
137 138 143 149 152 161 167
10 Vybrana´ rˇesˇenı´ 10.1 Pocˇ´ıta´nı´ s cˇ´ısly . . . . . . . . . . 10.2 Obra´zky a geometrie . . . . . . 10.3 Sˇifrova´nı´ a pra´ce s textem . . . 10.4 Logicke´ u´lohy . . . . . . . . . . 10.5 Hry . . . . . . . . . . . . . . . . 10.6 Klasicke´ informaticke´ proble´my Rejstrˇı´k
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
173
Prˇedmluva Tato kniha vycha´zı´ z my´ch zkusˇenostı´ s programova´nı´m v neˇkolika rolı´ch. V roli studenta jsem za svu˚j „programa´torsky´ zˇivot“ prosˇel mnoha programovacı´mi jazyky. Jako nejlepsˇ´ı zpu˚sob ucˇenı´ programovacı´ho jazyka mi vzˇdy prˇisˇla metoda „skocˇit do vody a plavat“, tedy vzı´t si zajı´mavy´, prˇimeˇrˇeneˇ na´rocˇny´ proble´m, ten zkusit vyrˇesˇit a potrˇebne´ veˇci se ucˇit za beˇhu. Cˇasto mi prˇisˇlo na´rocˇneˇjsˇ´ı vymyslet si zajı´mave´ zada´nı´, nezˇ najı´t rˇesˇenı´ konkre´tnı´ch technicky´ch proble´mu˚, na ktere´ jsem pak prˇi rˇesˇenı´ narazil. Jako ucˇitel ma´m podobnou zkusˇenost. S dı´lcˇ´ımi technicky´mi proble´my si veˇtsˇinou studenti zvla´dnou poradit, du˚lezˇite´ je prˇedevsˇ´ım prˇedlozˇit jim vhodny´ proble´m – proble´m, ktery´ pro neˇ bude adekva´tneˇ obtı´zˇny´ a soucˇasneˇ bude neˇjaky´m zpu˚sobem zajı´mavy´, takzˇe je bude bavit. Podobneˇ je to i v programa´torsky´ch souteˇzˇ´ıch, ktery´ch jsem se mnohokra´t u´cˇastnil v roli souteˇzˇ´ıcı´ho i organiza´tora. Zajı´mavou souteˇzˇ deˇlajı´ dobrˇe vybrane´ proble´my. Ve vsˇech teˇchto rolı´ch jsem se setkal s celou rˇadou zajı´mavy´ch prˇ´ıkladu˚, ale vzˇdy, kdyzˇ neˇjaky´ potrˇebuji, musı´m slozˇiteˇ vzpomı´nat nebo hledat. Dobry´ch ucˇebnic programova´nı´ existuje spousta, ale veˇtsˇinou kladou du˚raz na konkre´tnı´ jazyk nebo detailnı´ rozbor dı´lcˇ´ıch algoritmu˚, prˇ´ıkladu˚ v nich by´va´ jen pa´r. Rozsa´hla´ sbı´rka zajı´mavy´ch prˇ´ıkladu˚ mi vzˇdy chybeˇla. Proto jsem se pokusil ji vytvorˇit a pevneˇ veˇrˇ´ım, zˇe bude uzˇitecˇna´ nejen pro meˇ. Kniha prˇ´ımo cˇi neprˇ´ımo cˇerpa´ z velke´ho mnozˇstvı´ zdroju˚ a zkusˇenostı´. Kromeˇ teˇch litera´rnı´ch, ktere´ jsou uvedeny v seznamu literatury, jde hlavneˇ o programa´torske´ souteˇzˇe a vy´uku. Velkou meˇrou cˇerpa´m ze zkusˇenostı´ s programa´torsky´mi souteˇzˇemi a z prˇ´ıkladu˚, ktere´ jsem na teˇchto souteˇzˇ´ıch poznal cˇi pro neˇ navrhl. Konkre´tneˇ jde o souteˇzˇ ACM ICPC a jejı´ cˇesko-slovenskou verzi CTU Open, programa´torskou olympia´du, korespondencˇnı´ semina´rˇe z programova´nı´ a fakultnı´ souteˇzˇ FIbot. Cenne´ zkusˇenosti jsem zı´skal prˇi vy´uce programa´torsky´ch prˇedmeˇtu˚ na Fakulteˇ informatiky MU, prˇedevsˇ´ım pak prˇi vedenı´ prˇedmeˇtu IV104 Semina´rˇ rˇesˇenı´ programa´torsky´ch u´loh. Na studentech tohoto prˇedmeˇtu jsem mnoho
8
Prˇedmluva
zde uvedeny´ch prˇ´ıkladu˚ testoval a jejich pozorova´nı´m jsem zı´skal zkusˇenosti o obtı´zˇnosti a pedagogicke´ vhodnosti jednotlivy´ch u´loh. Tato kniha take´ cˇa´stecˇneˇ vycha´zı´ k me´ prˇedchozı´ knihy „Jak to vyrˇesˇit?“, ktera´ se zaby´va´ logicky´mi u´lohami a jejich vyuzˇitı´m prˇi vy´uce informatiky. Cˇa´st prˇ´ıkladu˚ uvedeny´ch zde v kapitola´ch o logicky´ch u´loha´ch a hra´ch vycha´zı´ z te´to drˇ´ıveˇjsˇ´ı knihy. Chteˇl bych tedy podeˇkovat vsˇem, kdo organizovali uvedene´ souteˇzˇe, u´cˇastnili se me´ vy´uky cˇi poma´hali s prˇ´ıpravou prˇedchozı´ knihy, za jejich prˇ´ınos pro tuto knihu, byt’neveˇdomy´ a neprˇ´ımy´. Konkre´tneˇ bych chteˇl podeˇkovat Petrovi Jarusˇkovi a Janovi Ryglovi za komenta´rˇe k dı´lcˇ´ım cvicˇenı´m. Martin Herodek z nakladatelstvı´ Computer Press pomohl knihu vylepsˇit po obsahove´ i typograficke´ stra´nce. Podeˇkova´nı´ take´ patrˇ´ı mojı´ zˇeneˇ Barcˇe za jejı´ vytrvalou podporu nejen prˇi psanı´. Radek Pela´nek
1 O knize Mysl nenı´ na´doba, kterou je potrˇeba naplnit, ale ohenˇ, ktery´ je potrˇeba zapa´lit. Plutarchos Aby se cˇloveˇk naucˇil programovat, musı´ se naucˇit za´kladnı´ prˇ´ıkazy a postupy (trochu mysl naplnit), prˇedevsˇ´ım vsˇak potrˇebuje hodneˇ tre´novat, zkousˇet a procvicˇovat. Aby u toho tre´nova´nı´ cˇloveˇk vydrzˇel, meˇl by by´t zapa´leny´. Jenzˇe na cˇem tre´novat programova´nı´, aby to bylo zajı´mave´? Na programova´nı´ rozsa´hly´ch, prakticky uzˇitecˇny´ch programu˚ zacˇa´tecˇnı´k jesˇteˇ nema´ a ucˇebnicove´ prˇ´ıklady jsou cˇasto nudne´, takzˇe u nich cˇloveˇk nevydrzˇ´ı. K tomu pra´veˇ slouzˇ´ı tato kniha – poskytuje na´meˇty na zajı´mava´ programa´torska´ cvicˇenı´, slouzˇ´ıcı´ k procvicˇenı´ a tre´ninku. Prˇ´ıklady jsou voleny tak, aby byly atraktivnı´ a zajı´mave´, takzˇe cˇloveˇka, ktery´ ma´ alesponˇ trochu informaticke´ho ducha a nadsˇenı´, vta´hnou natolik, zˇe si vydrzˇ´ı s nimi hra´t, dı´ky cˇemuzˇ dobrˇe potre´nuje. Kniha nenı´ zameˇrˇena na zˇa´dny´ specificky´ programovacı´ jazyk. Vsˇechny prˇ´ıklady jsou zvla´dnutelne´ ve vsˇech beˇzˇneˇ pouzˇ´ıvany´ch programovacı´ch jazycı´ch, a to veˇtsˇinou s docela za´kladnı´mi prvky jazyka, tj. bez pouzˇitı´ pokrocˇily´ch vlastnostı´ jazyka a specia´lnı´ch knihoven. Prˇedpokla´da´ se, zˇe cˇtena´rˇ ma´ k dispozici ucˇebnici konkre´tnı´ho programovacı´ho jazyka, ktery´ pouzˇ´ıva´. Kniha slouzˇ´ı nejen k procvicˇenı´ za´kladnı´ch programa´torsky´ch konstrukcı´, ale i k procvicˇenı´ algoritmu˚. I po te´to stra´nce je kniha prˇedevsˇ´ım cvicˇebnicı´ a nikoliv samonosnou ucˇebnicı´. Klı´cˇove´ pojmy jsou v knize strucˇneˇ popsa´ny a vysveˇtleny, nicme´neˇ tento popis je mı´neˇn jako prˇipomenutı´ pojmu˚, ktere´ jizˇ cˇtena´rˇ slysˇel, resp. inspirace pro to, co by si meˇl dostudovat. Opeˇt se prˇedpokla´da´, zˇe cˇtena´rˇ ma´ k dispozici ucˇebnici algoritmizace (naprˇ. Skiena, 1998; Wroblewski, 2004; Cormen et al., 2001; Kucˇera, 2009) nebo prosˇel relevantnı´m odborny´m kurzem. Pokryta´ la´tka veˇtsˇinou spada´ do ucˇiva probı´rane´ho v 1. rocˇnı´ku na informaticky´ch vysoky´ch sˇkola´ch. Kniha obsahuje sˇirokou sˇka´lu prˇ´ıkladu˚ od velmi jednoduchy´ch azˇ po mysˇlenkoveˇ i programa´torsky na´rocˇne´ projekty. Take´ dı´lcˇ´ı u´lohy obsahujı´ podu´lohy
10
1. O knize
s ru˚znou slozˇitostı´. Cˇtena´rˇ tedy vzˇdy mu˚zˇe najı´t prˇ´ıklad, ktery´ odpovı´da´ jeho momenta´lnı´m schopnostem, na´ladeˇ, cˇasovy´m mozˇnostem a tomu, co si chce procvicˇit. Pru˚beˇzˇneˇ, jak se bude zlepsˇovat, zde navı´c najde sta´le nove´ vy´zvy. Kniha prˇijde vhod neˇkolika skupina´m cˇtena´rˇu˚m: • studentu˚m, kterˇ´ı se ucˇ´ı programovat a psa´t efektivnı´ algoritmy, pro samostudium a tre´nink, • ucˇitelu˚m, kterˇ´ı vyucˇujı´ programova´nı´ a hledajı´ na´meˇty na cvicˇenı´, zada´nı´ doma´cı´ch u´loh a projektu˚, • zkusˇeny´m programa´toru˚m, kterˇ´ı se ucˇ´ı novy´ jazyk a chteˇjı´ si jej procvicˇit na prˇ´ıkladech, prˇ´ıpadneˇ si chteˇjı´ procvicˇit sve´ „programa´torske´ svaly“ na zajı´mavy´ch prˇ´ıkladech.
1.1
´ lohy a jejich popisky U Proble´my, ktere´ stojı´ za u´tok, proka´zˇou svoji cenu tı´m, zˇe u´tok opeˇtujı´. P. Erd˝os
´ lohy jsou rozdeˇleny do neˇkolika tematicky´ch oblastı´, ktere´ sdı´lejı´ za´kladnı´ U rysy. Pro kazˇdou u´lohu je uveden odhad obtı´zˇnosti, strucˇny´ styl u´lohy, popis zada´nı´, doplnˇujı´cı´ komenta´rˇ a cˇa´stecˇneˇ pozna´mky k rˇesˇenı´m. Kniha obsahuje velmi rozmanite´ typy u´loh. Neˇktere´ jsou prˇ´ımocˇare´, v zada´nı´ je celkem jasneˇ popsa´no, co deˇlat, stacˇ´ı to „jen“ implementovat. Jine´ jsou na´padove´ – vy´sledny´ program je velmi kra´tky´ a nevyzˇaduje nic slozˇite´ho, ale je potrˇeba vhodny´ na´pad, na ktery´ nemusı´ by´t snadne´ prˇijı´t. U jiny´ch prˇ´ıkladu˚ se zase naopak hodı´ netrivia´lnı´ teorie cˇi pojmy, ale ty jsou strucˇneˇ vysveˇtleny, takzˇe jde hlavneˇ o to popis pochopit, dohledat si v prˇ´ıpadeˇ potrˇeby detailneˇjsˇ´ı vysveˇtlenı´ a zvla´dnout popis prˇeve´st do funkcˇnı´ho programu. Za´kladnı´ styl u´lohy je vzˇdy strucˇneˇ shrnut na zacˇa´tku popisu u´lohy. Kromeˇ slovnı´ho popisu stylu je pro snadneˇjsˇ´ı orientaci uvedeno i cˇ´ıselne´ hodnocenı´ obtı´zˇnosti u´loh. Toto hodnocenı´ obtı´zˇnosti je rozdeˇleno na dva aspekty: na´pad, tedy jak na´rocˇne´ je prˇijı´t na hlavnı´ mysˇlenku rˇesˇenı´, algoritmus a vhodnou reprezentaci dat, a ko´dova´nı´, tedy jak na´rocˇne´ je program napsat a odladit. Obeˇ kategorie jsou pouze prˇiblizˇne´ odhady a slouzˇ´ı prˇedevsˇ´ım k relativnı´mu porovna´nı´ u´loh. Absolutnı´ obtı´zˇnost pochopitelneˇ za´visı´ na zkusˇenostech rˇesˇitele. Obeˇ obtı´zˇnosti jsou hodnoceny na stupnici 1–5. Vy´znam jednotlivy´ch stupnˇu˚ pro zacˇa´tecˇnı´ka a experta je ilustrova´n v tabulce 1.1. U veˇtsˇiny u´loh je pro na´pad i ko´dova´nı´ uveden interval, protozˇe u´lohy typicky obsahujı´ neˇkolik podu´loh, jejichzˇ obtı´zˇnost se lisˇ´ı. Podu´lohy jsou veˇtsˇinou uvedeny v porˇadı´ rostoucı´ obtı´zˇnosti.
´ lohy a jejich popisky 1.1. U
11
Tabulka 1.1: Kategorie obtı´zˇnosti Na´pad 1 2 3 4 5
Zacˇa´tecˇnı´k vcelku jasne´ trocha rozmy´sˇlenı´ teˇzˇke´ hranice mozˇnostı´ nerˇesˇitelne´
Expert zrˇejme´ rutina trocha rozmy´sˇlenı´ teˇzˇke´ hranice mozˇnostı´
Ko´dova´nı´ 1 2 3 4 5
Zacˇa´tecˇnı´k 20 min. 1 hod. pu˚l dne neˇkolik dnı´ pu˚lrocˇnı´ projekt
Expert 5 min. 15 min. 1 hod. 2–6 hod. intenzivnı´ vı´kend
Da´le pak na´sleduje samotny´ popis u´lohy. Zada´nı´ je za´kladnı´ popis cı´lu˚ u´lohy. Po prˇecˇtenı´ tohoto textu je mozˇne´ zacˇ´ıt rˇesˇit, v prˇ´ıpadeˇ pouzˇitı´ ve vy´uce je tento text urcˇeny´ pro studenty. Na´sleduje komenta´rˇ k u´loze, ktery´ obsahuje souvislosti a za´kladnı´ rady, jak k proble´mu prˇistupovat. Komenta´rˇe obcˇas prozrazujı´ i za´kladnı´ mysˇlenky vhodny´ch algoritmu˚ cˇi skryte´ „finty“, jak k zada´nı´ prˇistoupit. Ambicio´znı´ cˇtena´rˇ by tedy meˇl u´lohu zkusit vyrˇesˇit bez cˇtenı´ komenta´rˇu˚. Na konci knihy jsou uvedena vybrana´ rˇesˇenı´, ktera´ detailneˇji osveˇtlujı´ zajı´mave´ body z postupu, ukazujı´ prˇ´ıklady mozˇny´ch programu˚, prˇ´ıpadneˇ odpoveˇdi na konkre´tnı´ ota´zky polozˇene´ v zada´nı´. Jde vsˇak opravdu pouze o vybrana´ rˇesˇenı´, rozhodneˇ nejsou rozebra´ny vsˇechny prˇ´ıklady a varianty. To nenı´ zˇa´doucı´, neˇktere´ proble´my jsou za´meˇrneˇ ponecha´ny otevrˇene´ pro vlastnı´ zkouma´nı´ a projekty. V rˇesˇenı´ch jsou uvedeny uka´zky ko´du v jazyce Python. Jazyk Python byl pro uka´zky zvolen proto, zˇe jde o cˇisty´ vysokou´rovnˇovy´ jazyk, ktery´ by´va´ obcˇas oznacˇova´n za „spustitelny´ pseudoko´d“. Uka´zky ko´du by tedy meˇly by´t pochopitelne´ i bez znalosti tohoto konkre´tnı´ho jazyka. Python je programovacı´ jazyk, ktery´ se rozhodneˇ vyplatı´ naucˇit, nicme´neˇ pro porozumeˇnı´ te´to knize nenı´ jeho znalost nijak za´sadnı´.
12
1.2
1. O knize
Jak knihu pouzˇ´ıvat Bud’ to udeˇlej, nebo ne. Neexistuje zˇa´dne´ „zkusı´m“. Yoda ve filmu Impe´rium vracı´ u´der
Knihu lze vyuzˇ´ıvat ru˚zny´mi zpu˚soby: k samostudiu, ve vy´uce ke kra´tky´m cvicˇenı´m, k zada´va´nı´ doma´cı´ch u´loh nebo i rozsa´hly´ch projektu˚. Na´sleduje neˇkolik komenta´rˇu˚ a doporucˇenı´ ke kazˇde´mu stylu. V prˇ´ıpadeˇ samostudia je du˚lezˇita´ pevna´ vu˚le – nespokojit se pouze s jednoduchy´mi prˇ´ıklady a nedı´vat se hned na rˇesˇenı´. Mu˚zˇe by´t vhodne´ najı´t si partnera, se ktery´m budete prˇ´ıklady rˇesˇit soubeˇzˇneˇ. Mu˚zˇete tak souteˇzˇit, kdo zvla´dne u´lohy vyrˇesˇit rychleji cˇi efektivneˇji, a take´ mu˚zˇete sva´ rˇesˇenı´ porovna´vat. U mnoha u´loh existuje neˇkolik ru˚zny´ch rˇesˇenı´ a porovna´nı´m vı´ce ru˚zny´ch rˇesˇenı´ se mu˚zˇete hodneˇ naucˇit. U pouzˇitı´ ve vy´uce, prˇedevsˇ´ım pokud programova´nı´ probı´ha´ v hodineˇ, ktera´ ma´ fixnı´ konec, je du˚lezˇite´ vybrat prˇ´ıklady spra´vne´ obtı´zˇnosti. Prˇedevsˇ´ım je du˚lezˇite´, aby obtı´zˇnost nebyla prˇ´ılisˇ vysoka´. Pokud studenti v pu˚lce hodiny zjistı´, zˇe je nad jejich sı´ly dokoncˇit prˇ´ıklad v dostupne´m cˇase, jsou demotivova´ni, uzˇ se prˇ´ılisˇ nesoustrˇedı´ a tı´m pa´dem i nic moc nenaucˇ´ı. Prˇ´ımo ve vyucˇovacı´ hodineˇ je lepsˇ´ı pouzˇ´ıvat za´kladnı´ varianty prˇ´ıkladu˚ a slozˇiteˇjsˇ´ı varianty a rozsˇ´ırˇenı´ nechat jako doma´cı´ u´kol, u ktere´ho nenı´ tak kra´tky´ cˇasovy´ limit. U doma´cı´ch u´loh je dnes samozrˇejmeˇ proble´m s vyhleda´va´nı´m na Internetu. Do knihy jsou zacˇleneˇny u´lohy zajı´mave´ a osveˇdcˇene´, cozˇ ovsˇem znaˇ esˇenı´ mnoha u´loh lze tedy mena´, zˇe jde cˇasto take´ o u´lohy zna´me´ a rozsˇ´ırˇene´. R cˇasto vcelku snadno najı´t na Internetu (prˇedevsˇ´ım pokud hleda´me anglicke´ verze pojmu˚). Pokud jsme si tohoto proble´mu veˇdomi, lze mu vcelku rozumneˇ prˇedcha´zet. Snadno vyhledatelna´ rˇesˇenı´ veˇtsˇinou nejsou prˇesneˇ v te´ podobeˇ, jak je zde zada´no, a pokud navı´c u´lohu trochu pozmeˇnı´me cˇi prˇejmenujeme, cˇasto se da´ snadne´mu vyhleda´nı´ zabra´nit. Navı´c schopnost „vyhledat si za´klad rˇesˇenı´ a to pak jen vhodneˇ upravit“ nenı´ sama o sobeˇ nijak sˇpatna´, naopak u prakticky´ch aplikacı´ programova´nı´ to je preferovany´ postup. I tuto schopnost mu˚zˇe by´t uzˇitecˇne´ tre´novat, takzˇe u neˇktery´ch prˇ´ıkladu˚ mu˚zˇe by´t rozumne´ pouzˇitı´ tohoto prˇ´ıstupu podporovat. Konkre´tneˇ naprˇ´ıklad u cvicˇenı´ „Experimenty s rˇadicı´mi algoritmy“ studenty podporuji v tom, aby si rˇadicı´ algoritmy vyhledali a pouze prˇevedli do jednotne´ho stylu a aby se soustrˇedili na experimenta´lnı´ porovna´nı´. Prˇi pouzˇitı´ prˇ´ıkladu˚ jako zada´nı´ projektu˚ vyuzˇ´ıvejte zde uvedene´ zada´nı´ ˇ esˇitel projektu by meˇl zkusit vymyslet vlastnı´ rozsˇ´ıpouze jako vy´chozı´ bod. R rˇenı´ a variace a zkusit si sa´m polozˇit zajı´mavou ota´zku o u´loze.
1.3. Sce´na´rˇe pouzˇitı´
1.3
13
Sce´na´rˇe pouzˇitı´ Cˇ´ım tvrdeˇji pracuji, tı´m vı´c se zda´, zˇe ma´m sˇteˇstı´. T. Jefferson
Forma´t knihy vynucuje linea´rnı´ rˇazenı´ prˇ´ıkladu˚, ovsˇem mozˇny´ch krite´riı´, podle ktery´ch lze prˇ´ıklady rˇadit, je cela´ rˇada: naprˇ´ıklad obtı´zˇnost, metoda rˇesˇenı´, te´ma, typ vstupu a vy´stupu. V te´to knize je zvoleno tematicke´ rˇazenı´ prˇ´ıkladu˚. Prˇ´ıklady, ktere´ jsou zarˇazeny za sebou, tedy sdı´lejı´ podobne´ te´ma, ale mohou se vy´razneˇ lisˇit v ostatnı´ch aspektech, prˇedevsˇ´ım v obtı´zˇnosti. To znamena´, zˇe nenı´ dobry´ na´pad rˇesˇit prˇ´ıklady v knize cˇisteˇ sekvencˇneˇ. Pro vy´beˇr vhodne´ho prˇ´ıkladu slouzˇ´ı informace uvedene´ na zacˇa´tku popisu kazˇde´ho prˇ´ıkladu a da´le pak tato a na´sledujı´cı´ kapitola, ktere´ uda´vajı´ prˇehled prˇ´ıkladu˚ roztrˇ´ıdeˇny´ch podle ru˚zny´ch krite´riı´. V te´to kapitole jsou prˇ´ıklady roztrˇ´ıdeˇny podle stylu pouzˇitı´, v na´sledujı´cı´ pak podle metod na´vrhu algoritmu˚, ktere´ se prˇi rˇesˇenı´ pouzˇ´ıvajı´. Zde uvedene´ seznamy berte jen jako za´kladnı´ orientaci. To, zˇe prˇ´ıklad nenı´ uveden v urcˇite´ kategorii, jesˇteˇ neznamena´, zˇe by nemohl by´t pro dane´ u´cˇely vhodny´.
´ plnı´ zacˇa´tecˇnı´ci U Zacˇneme prˇ´ıklady vhodny´mi pro u´vodnı´ kurz programova´nı´, tedy pro ty, kdo neumı´ vu˚bec programovat. Prˇ´ıklady jsou rˇazeny v porˇadı´, v jake´m je vhodne´ je procha´zet: • 4.2 Zˇelvı´ grafika: za´klady – pokud pouzˇ´ıva´te jazyk, ktery´ ma´ snadno pouzˇitelnou knihovnu pro interpretaci prˇ´ıkazu˚ zˇelvı´ grafiky (naprˇ. Python), je toto cvicˇenı´ nena´rocˇne´ a prˇitom efektnı´ (pomocı´ pa´r prˇ´ıkazu˚ jdou kreslit zajı´mave´ obra´zky), takzˇe jde o vhodne´ prvnı´ cvicˇenı´. • Prˇ´ıklady z kapitoly Pocˇ´ıta´nı´ s cˇ´ısly, konkre´tneˇ: 3.1 Hra´tky s cˇ´ısly, 3.2 Vy´pisy posloupnostı´, 3.3 Collatzu˚v proble´m, 3.4 Na´hodna´ procha´zka, 3.5 Deˇlitelnost a prvocˇ´ısla – u teˇchto prˇ´ıkladu˚ vystacˇ´ıme pouze s jednoduchy´mi syntakticky´mi prvky jazyka (celocˇ´ıselne´ promeˇnne´ a cykly), prˇ´ıklady jsou take´ vhodne´ pro prˇedstavenı´ konceptu funkce. • 3.7 Fibonacciho posloupnost – prˇedstavenı´ jednorozmeˇrne´ho pole, uka´zka ru˚zny´ch pohledu˚ na proble´m. • 4.1 Textova´ grafika – opeˇt proble´my vyuzˇ´ıvajı´cı´ jen za´kladnı´ syntakticke´ konstrukce, jen vı´ce obra´zkove´ a obcˇas vyzˇadujı´cı´ mı´rny´ na´pad. • 5.2 Transpozicˇnı´ sˇifry, 5.3 Substituce a ko´dova´nı´ – vhodne´ pro prˇedstavenı´ rˇeteˇzcu˚ a pra´ce s nimi.
14
1. O knize • 7.2 Ha´da´nı´ cˇ´ısla, 7.3 Obeˇsˇenec, 7.5 Hra Nim – vhodne´ pro prˇedstavenı´ nacˇ´ıta´nı´ vstupu od uzˇivatele (prˇ´ıpadneˇ ze souboru) a vyzkousˇenı´ interakce s uzˇivatelem. Prˇ´ıklady take´ ilustrujı´ zajı´mave´ a prˇitom vcelku snadno zvla´dnutelne´ algoritmy. ˇ elvı´ grafika: frakta´ly, 6.3 Hanojske´ veˇzˇe – prˇedstavenı´ konceptu • 4.3 Z rekurze. • 6.1 Cˇ´ıselne´ bludisˇteˇ, 6.5 Hleda´nı´ cest v bludisˇti – pra´ce s dvojrozmeˇrny´m polem, prˇedstavenı´ za´kladnı´ch grafovy´ch algoritmu˚ (prohleda´va´nı´ do sˇ´ırˇky). • 8.4 Experimenty s rˇadicı´mi algoritmy – pra´ce s polem, ilustrace klasicky´ch algoritmu˚.
Prˇ´ıklady z kapitoly 3 Pocˇ´ıta´nı´ s cˇ´ısly jsou realizovatelne´ trˇeba i v tabulkove´m editoru a mohou tak poslouzˇit jako za´kladnı´ u´vod do algoritmizace i v prˇ´ıpadeˇ, kdy nenı´ ve vy´uce cˇas na probra´nı´ obecne´ho programovacı´ho jazyka.
Tre´nink algoritmizace Na´sledujı´cı´ prˇ´ıklady prˇijdou vhod, pokud se chceme zameˇrˇit prima´rneˇ na tre´nink algoritmu˚ a metod na´vrhu algoritmu˚ a chceme prˇ´ıklady, ktere´ jsou zvla´dnutelne´ prˇi dobre´m na´padu relativneˇ rychle a pomocı´ kra´tke´ho ko´du: • • • • • • • • • •
3.10 Permutace, kombinace, variace 4.7 Konvexnı´ obal 4.8 Triangulace 5.5 Prˇesmycˇky 6.3 Hanojske´ veˇzˇe 6.6 Generova´nı´ bludisˇt’ 7.7 Jednorozmeˇrne´ pisˇkvorky 8.1 Rozmeˇnˇova´nı´ mincı´ 8.3 Proble´my s rˇeteˇzci a posloupnostmi 8.4 Experimenty s rˇadicı´mi algoritmy
Podrobneˇjsˇ´ı rozbor ru˚zny´ch metod na´vrhu algoritmu˚ je uveden v na´sledujı´cı´ kapitole.
Ucˇenı´ nove´ho jazyka Pro ty, kdo uzˇ umı´ programovat, pouze se ucˇ´ı novy´ programovacı´ jazyk a chteˇjı´ jej natre´novat na zajı´mavy´ch prˇ´ıkladech, se mohou hodit na´sledujı´cı´ prˇ´ıklady: • 3.9 Vy´pocˇet Pı´ – zajı´mave´ experimenty, ktere´ prˇitom vyzˇadujı´ jen manipulaci s cˇ´ıselny´mi promeˇnny´mi (vhodne´ pro prvnı´ sezna´menı´ s jazykem).
1.3. Sce´na´rˇe pouzˇitı´
15
• 6.1 Cˇ´ıselne´ bludisˇteˇ – jednoducha´ logicka´ u´loha pro procvicˇenı´ pra´ce s dvojrozmeˇrny´m polem. • 5.2 Transpozicˇnı´ sˇifry, 5.3 Substituce a ko´dova´nı´ – procvicˇenı´ za´kladnı´ pra´ce s rˇeteˇzci a poli. • 7.6 Tetris (interaktivnı´ verze) – komplexnı´ procvicˇenı´ mnoha aspektu˚ jazyka (interakce s uzˇivatelem, reprezentace dat, cˇas), prˇicˇemzˇ celkoveˇ je program docela kra´tky´ a vy´sledek relativneˇ efektnı´.
Vy´zvy pro zkusˇene´ programa´tory Pro zkusˇene´ programa´tory, kterˇ´ı se nechteˇjı´ ucˇit novy´ jazyk nebo algoritmus, ale chteˇjı´ vy´zvu svy´ch schopnostı´, zkusit si neˇco „pro radost z programova´nı´“ nebo potre´novat na programa´torskou souteˇzˇ, se mohou hodit na´sledujı´cı´ prˇ´ıklady. • Vy´sˇe uvedene´ prˇ´ıklady na tre´nink algoritmizace. • Prˇ´ıklady z kapitoly 8 Klasicke´ informaticke´ proble´my, a to nejle´pe bez cˇtenı´ doprovodne´ho komenta´rˇe. ˇ elvı´ grafika: frakta´ly, ´ lohy 3.10 Permutace, kombinace, variace, 4.3 Z • U ´ ´ ho frakta´l. Tyto u´lohy majı´ kra´tke´ elegantnı´ rˇesˇenı´, ale nenı´ 4.4 Sierpinske u´plneˇ snadne´ je vymyslet. • Hry a logicke´ u´lohy, konkre´tneˇ naprˇ. 6.11 Sokoban, 7.6 Tetris, 7.8 Pisˇkvorky. Za´kladnı´ verze her v textove´m rezˇimu lze napsat docela rychle, take´ heuristiky pro umeˇlou inteligenci mohou by´t s dobry´m na´padem kra´tke´, poskytujı´ prostor pro souteˇzˇenı´ o to, kdo napı´sˇe neju´speˇsˇneˇjsˇ´ı program, a take´ da´vajı´ sˇiroky´ prostor pro rozsˇ´ırˇenı´. • 5.4 Rozlomenı´ sˇifer – tato u´loha obsahuje otevrˇenou a zajı´mavou vy´zvu napsat program tak, aby byl co neju´speˇsˇneˇjsˇ´ı v la´ma´nı´ sˇifer. Zkusˇenı´ programa´torˇi si pak take´ mohou u´lohy rozsˇ´ırˇit tı´m, zˇe prˇekrocˇ´ı ra´mec psanı´ klasicky´ch sekvencˇnı´ch programu˚ vyuzˇitı´m paralelizace u vy´pocˇetneˇ na´rocˇny´ch proble´mu˚, naprˇ. 6.11 Sokoban, 6.8 Jak navsˇtı´vit vsˇechna pole mrˇ´ızˇky? nebo 4.6 Mandelbrotova mnozˇina s velkou prˇesnostı´. Mu˚zˇete zkusit co nejefektivneˇji vyuzˇ´ıt vı´ceja´drove´ procesory nebo prove´st vy´pocˇet v distribuovane´m prostrˇedı´. Jiny´m zpu˚sobem rozsˇ´ırˇenı´ zada´nı´ mu˚zˇe by´t realizace u´loh formou interaktivnı´ webove´ aplikace nebo aplikace pro mobilnı´ telefon – pro tento styl jsou vhodne´ prˇedevsˇ´ım hry a logicke´ u´lohy, ale zajı´mave´ mohou by´t i neˇktere´ geometricke´ proble´my a u´lohy s obra´zky.
16
1. O knize
Projekty Jako te´mata semestra´lnı´ch (rocˇnı´kovy´ch) projektu˚, prˇ´ıpadneˇ i jako inspirace pro te´mata bakala´rˇsky´ch cˇi diplomovy´ch pracı´, se mohou hodit na´sledujı´cı´ prˇ´ıklady: • Sˇifrovacı´ syste´m – kombinace te´mat z kapitoly 5 Sˇifrova´nı´ a pra´ce s textem. Program dostane text a bude ho umeˇt zasˇifrovat a desˇifrovat ru˚zny´mi zpu˚soby. ´ loha 6.6 Generova´nı´ bludisˇt’ a generova´nı´ zada´nı´ u dalsˇ´ıch logicky´ch • U u´loh. • Slozˇiteˇjsˇ´ı logicke´ u´lohy a hry: 6.9 Polyomina, 6.10 Sudoku, 6.11 Sokoban, 7.6 Tetris, 7.8 Pisˇkvorky. • 7.9 Souboje virtua´lnı´ch robotu˚. • 8.6 Grafove´ algoritmy. • Proble´my s experimenta´lnı´ slozˇkou, jako jsou 8.4 Experimenty s rˇadicı´mi algoritmy. • Na´meˇty z kapitoly 9 Dalsˇ´ı na´meˇty.
2 Prˇehled pojmu˚ Do pru˚sˇvihu na´s nikdy nedostane to, co nevı´me. Dostane na´s tam to, co vı´me prˇ´ılisˇ jisteˇ, a ono to tak prosteˇ nenı´. Y. Berry Tato kniha slouzˇ´ı jako cvicˇebnice, nikoliv jako kompletnı´ ucˇebnice. U jednotlivy´ch prˇ´ıkladu˚ jsou veˇtsˇinou hlavnı´ mysˇlenky vysveˇtleny, prˇedpokla´da´ se vsˇak, zˇe cˇtena´rˇ umı´ programovat v neˇjake´m programovacı´m jazyce a zna´ za´kladnı´ pojmy z informatiky. Pro za´kladnı´ prˇehled pozadı´, na ktere´m kniha stavı´, slouzˇ´ı tato kapitola, ktera´ poda´va´ strucˇny´ prˇehled pojmu˚ pouzˇity´ch v knize. Rozhodneˇ nenı´ nezbytne´ vsˇechny uvedene´ pojmy ovla´dat, neˇktere´ z nich se vyuzˇijı´ pouze v neˇkolika ma´lo teˇzˇsˇ´ıch prˇ´ıkladech. Pro kazˇdy´ pojem je da´n strucˇny´ popis, ktery´ slouzˇ´ı prima´rneˇ pro prˇipomenutı´, nikoliv pro vysveˇtlenı´. Pokud se cˇtena´rˇ s neˇktery´m z pojmu˚ nesetkal, je vhodne´ si prˇed rˇesˇenı´m prˇ´ıkladu˚ souvisejı´cı´ch s dany´m pojmem te´ma blı´zˇe dostudovat. Vy´klad zmı´neˇny´ch pojmu˚ lze najı´t v mnoha ucˇebnicı´ch, viz naprˇ. Skiena, 1998; Wroblewski, 2004; Cormen et al., 2001; Kucˇera, 2009. U mnoha za´kladnı´ch pojmu˚ nabı´zı´ dobre´ vysveˇtlenı´ i Wikipedie. Ke kazˇde´mu pojmu je uveden i seznam prˇ´ıkladu˚, ve ktery´ch se dany´ pojem vyskytuje. Tyto prˇ´ıklady poslouzˇ´ı jako na´zorna´ ilustrace uvedene´ho strucˇne´ho popisu. Soucˇasneˇ lze tuto kapitolu vyuzˇ´ıt i jako zdroj na´meˇtu˚ ve chvı´li, kdy se ucˇ´ıte neˇjaky´ pojem a chcete si jej dobrˇe procvicˇit.
2.1
Slozˇitost
Drˇ´ıve nezˇ se podı´va´me na techniky na´vrhu algoritmu˚, prˇipomenˇme si, jak pomeˇrˇujeme vy´kon algoritmu˚. Prˇ´ımocˇary´ prˇ´ıstup by byl spustit algoritmy na konkre´tnı´m vstupu, zmeˇrˇit jejich rychlost a podle toho urcˇit „vı´teˇze“. Takovy´ prˇ´ıstup ma´ vsˇak zrˇejme´ nevy´hody: vy´sledek za´visı´ na pocˇ´ıtacˇi, na ktere´m algoritmy spousˇtı´me, a na volbeˇ konkre´tnı´ho vstupu. Proto se k porovna´nı´ algoritmu˚ veˇtsˇinou pouzˇ´ıva´ jiny´ prˇ´ıstup: nemeˇrˇ´ıme cˇas beˇhu na konkre´tnı´m
18
2. Prˇehled pojmu˚
pocˇ´ıtacˇi, ale pocˇet operacı´, ktere´ algoritmus prova´dı´, a nezajı´ma´ na´s de´lka vy´pocˇtu na konkre´tnı´m vstupu, ale funkce urcˇujı´cı´, jak de´lka vy´pocˇtu za´visı´ na velikosti vstupu. Slozˇitost algoritmu pak vyjadrˇujeme pomocı´ O(f (n)) notace, ktera´ rˇ´ıka´, zˇe de´lka vy´pocˇtu algoritmu je funkce f za´visejı´cı´ na velikosti vstupu n („azˇ na konstantnı´ na´sobek“). Na´sledujı´cı´ vy´cˇet uda´va´ prˇ´ıklady, ve ktery´ch se slozˇitost algoritmu˚ rozebı´ra´, a zminˇuje slozˇitost algoritmu˚ vyskytujı´cı´ch se v rˇesˇenı´ prˇ´ıkladu: • 8.4 Experimenty s rˇadicı´mi algoritmy – prakticke´ vyzkousˇenı´ rozdı´lu mezi algoritmy s kvadratickou slozˇitostı´ O(n2 ) a slozˇitostı´ O(n log(n)). • 7.2 Ha´da´nı´ cˇ´ısla – typicka´ ilustrace algoritmu s logaritmickou slozˇitostı´ O(log(n)). • 4.7 Konvexnı´ obal – algoritmus se slozˇitostı´ O(n log(n)). • 8.3 Proble´my s rˇeteˇzci a posloupnostmi – zde ma´me proble´my, kde naivnı´ rˇesˇenı´ ma´ exponencia´lnı´ slozˇitost O(2n ), ale pomocı´ vhodne´ho algoritmu mu˚zˇeme dosa´hnout kvadraticke´ slozˇitosti O(n2 ). • 5.5 Prˇesmycˇky – prˇ´ıklad uzˇitecˇne´ho algoritmu s exponencia´lnı´ slozˇitostı´ O(2n ) (ve veˇtsˇineˇ prˇ´ıpadu˚ jsou exponencia´lnı´ algoritmy pro rea´lne´ proble´my nepouzˇitelne´).
2.2
Rekurze a metoda rozdeˇl a panuj
Metoda „rozdeˇl a panuj“ je zalozˇena na tom, zˇe proble´m rozdeˇlı´me na podcˇa´sti, ktere´ jsou vza´jemneˇ neza´visle´ a pokud mozˇno majı´ podobnou velikost, a tyto podcˇa´sti vyrˇesˇ´ıme samostatneˇ. Na za´kladeˇ rˇesˇenı´ podproble´mu˚ pak zkonstruujeme rˇesˇenı´ kompletnı´ho proble´mu. Typicky´m prˇ´ıkladem pouzˇitı´ te´to metody je rˇazenı´ posloupnosti pomocı´ metody „rˇazenı´ slucˇova´nı´m“ – posloupnost rozdeˇlı´me na dva stejneˇ dlouhe´ u´seky, kazˇdy´ z nich samostatneˇ serˇadı´me a vznikle´ dveˇ serˇazene´ posloupnosti spojı´me do vy´sledne´ serˇazene´ posloupnosti. Jak ukazuje tento prˇ´ıklad, algoritmy navrzˇene´ pomocı´ metody rozdeˇl a panuj typicky vedou na pouzˇitı´ rekurze, tj. vola´nı´ sebe sama – funkce prˇi sve´m vy´pocˇtu vola´ sebe samu, pouze s jiny´mi hodnotami parametru˚. Variacı´ na metodu „rozdeˇl a panuj“ je metoda „prˇeved’ na prˇedchozı´ prˇ´ıpad“, nazy´vana´ te´zˇ „zmensˇi a panuj“. V tomto prˇ´ıpadeˇ rˇesˇenı´ proble´mu o velikosti n vyja´drˇ´ıme pomocı´ rˇesˇenı´ proble´mu o velikosti n − 1. Typicky´m prˇ´ıkladem pouzˇitı´ te´to metody je proble´m Hanojsky´ch veˇzˇ´ı. Cvicˇenı´ vyuzˇ´ıvajı´cı´ uvedene´ metody: 7.2 Ha´da´nı´ cˇ´ısla, 4.3 Zˇelvı´ grafika: ´ ´ ho frakta´l, 6.3 Hanojske´ veˇzˇe, 6.4 Pokry´va´nı´ mrˇ´ızˇky, frakta´ly, 4.4 Sierpinske 3.7 Fibonacciho posloupnost (prˇ´ıklad nevhodne´ho pouzˇitı´ rekurze), 8.5 Vyhodnocova´nı´ vy´razu.
2.3. Dynamicke´ programova´nı´
19
Dalsˇ´ı standardnı´ proble´my, u ktery´ch lze vyuzˇ´ıt tento prˇ´ıstup (nerozebı´rane´ detailneˇ v te´to knize): rˇadicı´ algoritmy (quicksort, rˇazenı´ slucˇova´nı´m), bina´rnı´ vyhleda´vacı´ strom, hleda´nı´ dvojice nejblizˇsˇ´ıch bodu˚, Strassenu˚v algoritmus pro na´sobenı´ matic, efektivnı´ na´sobenı´ cely´ch cˇ´ısel, rychla´ Furierova transformace.
2.3
Dynamicke´ programova´nı´
Dynamicke´ programova´nı´ je technika pro rˇesˇenı´ proble´mu˚, ktere´ jdou rozlozˇit na vza´jemneˇ se prˇekry´vajı´ podproble´my. Hlavnı´ rozdı´l oproti vy´sˇe uvedene´ metodeˇ rozdeˇl a panuj spocˇ´ıva´ v prˇekry´va´nı´ podproble´mu˚. U metody rozdeˇl a panuj potrˇebujeme, aby podproble´my byly neza´visle´. U dynamicke´ho programova´nı´ naopak stavı´me na prˇekryvech podproble´mu˚, prˇicˇemzˇ potrˇebujeme, aby rˇesˇenı´ proble´mu sˇlo vzˇdy vyja´drˇit jako kombinace rˇesˇenı´ mensˇ´ıch ˇ esˇenı´ pak budujeme „odspodu“. Nejdrˇ´ıve vyrˇesˇ´ıme nejmensˇ´ı podproble´mu˚. R podproble´my a pomocı´ nich pak budujeme rˇesˇenı´ rozsa´hlejsˇ´ıch podproble´mu˚. Program typicky funguje tak, zˇe si definujeme „tabulku“, do ktere´ ukla´da´me dı´lcˇ´ı rˇesˇenı´ a kterou postupneˇ vyplnˇujeme od jednoho konce. Alternativneˇ lze dynamicke´ programova´nı´ implementovat „odvrchu“ za vyuzˇitı´ rekurze, prˇicˇemzˇ si musı´me pamatovat vy´sledky rekurzivnı´ch vola´nı´, aby zbytecˇneˇ nedocha´zelo k opakova´nı´ vy´pocˇtu. Cvicˇenı´, ve ktery´ch se dynamicke´ programova´nı´ vyuzˇ´ıva´ (obcˇas jen v dı´lcˇ´ı varianteˇ zada´nı´): 3.7 Fibonacciho posloupnost, 3.8 Pascalu˚v troju´helnı´k, 7.5 Hra Nim, 8.3 Proble´my s rˇeteˇzci a posloupnostmi, 8.1 Rozmeˇnˇova´nı´ mincı´, 4.8 Triangulace. Dalsˇ´ı standardnı´ proble´my, u ktery´ch lze vyuzˇ´ıt tento prˇ´ıstup (nerozebı´rane´ v te´to knize): Floydu˚v-Warshallu˚v algoritmus pro hleda´nı´ nejkratsˇ´ı cesty mezi vsˇemi pa´ry vrcholu˚ v grafu, optima´lnı´ uza´vorkova´nı´ prˇi na´sobenı´ matic.
2.4
Hladove´ algoritmy
Hladove´ algoritmy budujı´ rˇesˇenı´ v jednotlivy´ch krocı´ch a v kazˇde´m kroku deˇlajı´ „loka´lneˇ optima´lnı´ rozhodnutı´ “, tj. rozhodnutı´, ktere´ se jevı´ jako optima´lnı´ na za´kladeˇ aktua´lnı´ situace. Takove´ algoritmy by´vajı´ jednoduche´ na programova´nı´ a majı´ dobrou vy´pocˇetnı´ slozˇitost. Nicme´neˇ jen ma´lokdy vedou k optima´lnı´mu rˇesˇenı´. I pokud nevedou k optima´lnı´mu rˇesˇenı´, mohou prˇedstavovat dobrou za´kladnı´ heuristiku, takzˇe cˇasto se vyplatı´ zacˇ´ıt hladovy´m algoritmem, pomocı´ neˇj zı´skat intuici o proble´mu, a pak teprve zacˇ´ıt vymy´sˇlet vylepsˇenı´.
