E-kniha: Programátorská cvičebnice - Radek Pelánek

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

eshop@albatrosmedia.cz

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 9

1.1 U

́

lohy a jejich popisky . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2 Jak knihu pouzˇı ́vat . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3 Sce ́na ́rˇe pouzˇitı ́ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Prˇehled pojmu ̊ 17

2.1 Slozˇitost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Rekurze a metoda rozdeˇl a panuj . . . . . . . . . . . . . . . . . . 18

2.3 Dynamicke ́ programova ́nı ́ . . . . . . . . . . . . . . . . . . . . . . 19

2.4 Hladove ́ algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5 Hruba ́ sı ́la a heuristiky . . . . . . . . . . . . . . . . . . . . . . . . 20

2.6 Grafy a stavove ́ prostory . . . . . . . . . . . . . . . . . . . . . . . 21

2.7 Objektoveˇ orientovane ́ programova ́nı ́ . . . . . . . . . . . . . . . 21

2.8 Grafika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Pocˇı ́ta ́nı ́ s cˇı ́sly 25

3.1 Hra ́tky s cˇı ́sly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.2 Posloupnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3 Collatzu ̊v proble ́m . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.4 Na ́hodna ́ procha ́zka . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.5 Deˇlitelnost a prvocˇı ́sla . . . . . . . . . . . . . . . . . . . . . . . . 31

3.6 Reprezentace cˇı ́sel . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.7 Fibonacciho posloupnost . . . . . . . . . . . . . . . . . . . . . . . 35

3.8 Pascalu ̊v troju ́helnı ́k . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.9 Vy ́pocˇet π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.10 Permutace, kombinace, variace . . . . . . . . . . . . . . . . . . . 40 Obsah 4 Obra ́zky a geometrie 43

4.1 Textova ́ grafika . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2 Z

ˇ

elvı ́ grafika: za ́klady . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.3 Z

ˇ

elvı ́ grafika: frakta ́ly . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.4 Sierpi ́nske ́ho frakta ́l . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.5 Bitmapova ́ grafika . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.6 Mandelbrotova mnozˇina . . . . . . . . . . . . . . . . . . . . . . . 54

4.7 Konvexnı ́ obal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.8 Triangulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5 S

ˇ

ifrova ́nı ́ a pra ́ce s textem 63

5.1 Analy ́za a imitace textu . . . . . . . . . . . . . . . . . . . . . . . . 63

5.2 Transpozicˇnı ́ sˇifry . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.3 Substituce a ko ́dova ́nı ́ . . . . . . . . . . . . . . . . . . . . . . . . 69

5.4 Rozlomenı ́ sˇifer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.5 Prˇesmycˇky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6 Logicke ́ u ́lohy 75

6.1 C

ˇ

ı ́selne ́ bludisˇteˇ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.2 Prˇele ́va ́nı ́ vody . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.3 Hanojske ́ veˇzˇe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.4 Pokry ́va ́nı ́ mrˇı ́zˇky . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.5 Hleda ́nı ́ cest v bludisˇti . . . . . . . . . . . . . . . . . . . . . . . . 83

6.6 Generova ́nı ́ bludisˇt’ . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.7 Rozmist’ova ́nı ́ figur na sˇachovnici . . . . . . . . . . . . . . . . . . 86

6.8 Jak navsˇtı ́vit vsˇechna pole mrˇı ́zˇky? . . . . . . . . . . . . . . . . . 89

6.9 Polyomina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6.10 Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.11 Sokoban . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7 Hry 99

7.1 Ka ́men, nu ̊zˇky, papı ́r . . . . . . . . . . . . . . . . . . . . . . . . . 100

7.2 Ha ́da ́nı ́ cˇı ́sla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7.3 Obeˇsˇenec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.4 Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

7.5 Hra Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

7.6 Tetris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7.7 Jednorozmeˇrne ́ pisˇkvorky . . . . . . . . . . . . . . . . . . . . . . 110

7.8 Pisˇkvorky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

7.9 Souboje virtua ́lnı ́ch robotu ̊ . . . . . . . . . . . . . . . . . . . . . . 112 Obsah 5 8 Klasicke ́ informaticke ́ proble ́my 117

8.1 Rozmeˇnˇova ́nı ́ mincı ́ . . . . . . . . . . . . . . . . . . . . . . . . . . 117

8.2 Simula ́tor hry Z

ˇ

ivot . . . . . . . . . . . . . . . . . . . . . . . . . . 119

8.3 Proble ́my s rˇeteˇzci a posloupnostmi . . . . . . . . . . . . . . . . 122

8.4 Experimenty s rˇadicı ́mi algoritmy . . . . . . . . . . . . . . . . . . 123

8.5 Vyhodnocova ́nı ́ vy ́razu ̊ . . . . . . . . . . . . . . . . . . . . . . . . 125

8.6 Grafove ́ algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 9 Dalsˇı ́ na ́meˇty 131

9.1 Generova ́nı ́ a transformace obra ́zku ̊ . . . . . . . . . . . . . . . . 131

9.2 Blı ́zke ́ body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

9.3 Akcˇnı ́ hry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

9.4 Implementace datovy ́ch struktur . . . . . . . . . . . . . . . . . . 134

9.5 Implementace matematicky ́ch operacı ́ . . . . . . . . . . . . . . . 134

9.6 Zpracova ́nı ́ a analy ́za rea ́lny ́ch dat . . . . . . . . . . . . . . . . . 135

9.7 Interpret jednoduche ́ho programovacı ́ho jazyka . . . . . . . . . 135 10 Vybrana ́ rˇesˇenı ́ 137

10.1 Pocˇı ́ta ́nı ́ s cˇı ́sly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

10.2 Obra ́zky a geometrie . . . . . . . . . . . . . . . . . . . . . . . . . 143

10.3 S

ˇ

ifrova ́nı ́ a pra ́ce s textem . . . . . . . . . . . . . . . . . . . . . . 149

10.4 Logicke ́ u ́lohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

10.5 Hry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

10.6 Klasicke ́ informaticke ́ proble ́my . . . . . . . . . . . . . . . . . . . 167 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 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 myslnaplnit), 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 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 sa

mostudium 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 U

́

lohy a jejich popisky

Proble ́my, ktere ́ stojı ́ za u ́tok, proka ́zˇou svoji cenu tı ́m, zˇe u ́tok opeˇtujı ́.

P. Erd ̋os

U

́

lohy jsou rozdeˇleny do neˇkolika tematicky ́ch oblastı ́, ktere ́ sdı ́lejı ́ za ́kladnı ́

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 za

da ́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 relativ

nı ́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. 1.1. U

́

lohy a jejich popisky 11

Tabulka 1.1: Kategorie obtı ́zˇnosti

Na ́pad Zacˇa ́tecˇnı ́k Expert

1 vcelku jasne ́ zrˇejme ́

2 trocha rozmy ́sˇlenı ́ rutina

3 teˇzˇke ́ trocha rozmy ́sˇlenı ́

4 hranice mozˇnostı ́ teˇzˇke ́

5 nerˇesˇitelne ́ hranice mozˇnostı ́

Ko ́dova ́nı ́ Zacˇa ́tecˇnı ́k Expert

1 20 min. 5 min.

2 1 hod. 15 min.

3 pu ̊l dne 1 hod.

4 neˇkolik dnı ́ 2–6 hod.

5 pu ̊lrocˇnı ́ projekt 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ı ́ za

jı ́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ı ́. 1. O knize 1.2 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 znamena ́, zˇe jde cˇasto take ́ o u ́lohy zna ́me ́ a rozsˇı ́rˇene ́. R

ˇ

esˇenı ́ mnoha u ́loh lze tedy

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ı ́ pouze jako vy ́chozı ́ bod. R

ˇ

esˇitel projektu by meˇl zkusit vymyslet vlastnı ́ rozsˇı ́

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ı ́ 13 1.3 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 ́. U

́

plnı ́ zacˇa ́tecˇnı ́ci

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ˇ. Py

thon), 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 jed

noduchy ́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. 1. O knize

• 7.2 Ha ́da ́nı ́ cˇı ́sla, 7.3 Obeˇsˇenec, 7.5 Hra Nim – vhodne ́ pro prˇedstavenı ́ na

cˇı ́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.

• 4.3 Z

ˇ

elvı ́ grafika: frakta ́ly, 6.3 Hanojske ́ veˇzˇe – prˇedstavenı ́ konceptu

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 ́sledu

jı ́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 mani

pulaci 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.

• U

́

lohy 3.10 Permutace, kombinace, variace, 4.3 Z

ˇ

elvı ́ grafika: frakta ́ly,

4.4 Sierpi ́nske ́ho frakta ́l. Tyto u ́lohy majı ́ kra ́tke ́ elegantnı ́ rˇesˇenı ́, ale nenı ́

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 do

cela 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 tex

tem. Program dostane text a bude ho umeˇt zasˇifrovat a desˇifrovat ru ̊z

ny ́mi zpu ̊soby.

• U

́

loha 6.6 Generova ́nı ́ bludisˇt’a generova ́nı ́ zada ́nı ́ u dalsˇı ́ch logicky ́ch

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 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(n

2

) a slozˇitostı ́ O(nlog(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(nlog(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(2

n

), ale pomocı ́ vhodne ́ho algoritmu

mu ̊zˇeme dosa ́hnout kvadraticke ́ slozˇitosti O(n

2

).

• 5.5 Prˇesmycˇky – prˇı ́klad uzˇitecˇne ́ho algoritmu s exponencia ́lnı ́ slozˇitostı ́

O(2

n

) (ve veˇtsˇineˇ prˇı ́padu ̊ jsou exponencia ́lnı ́ algoritmy pro rea ́lne ́ pro

ble ́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 pa

nuj 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:

frakta ́ly, 4.4 Sierpi ́nske ́ho frakta ́l, 6.3 Hanojske ́ veˇzˇe, 6.4 Pokry ́va ́nı ́ mrˇı ́zˇky, 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 podproble ́mu ̊. R

ˇ

esˇenı ́ pak budujeme „odspodu“. Nejdrˇı ́ve vyrˇesˇı ́me nejmensˇı ́

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ı ́. 2. Prˇehled pojmu ̊

Cvicˇenı ́ souvisejı ́cı ́ s uvedeny ́mi pojmy: 8.1 Rozmeˇnˇova ́nı ́ mincı ́ (klasicka ́ ilustrace pouzˇitı ́ hladove ́ho algoritmu a toho, kdy nefunguje), 4.8 Triangulace, 7.6 Tetris (za ́kladnı ́ heuristiku pro „umeˇlou inteligenci“ pro tuto hru lze realizovat hladovy ́m algoritmem), cˇa ́stecˇneˇ 7.3 Obeˇsˇenec.

Dalsˇı ́ standardnı ́ proble ́my, u ktery ́ch lze vyuzˇı ́t tento prˇı ́stup (nerozebı ́rane ́ detailneˇ v te ́to knize): Huffmanovo ko ́dova ́nı ́, Primu ̊v a Kruskalu ̊v algoritmus pro hleda ́nı ́ kostry grafu, Dijkstru ̊v algoritmus pro hleda ́nı ́ nejkratsˇı ́ cesty v grafu. 2.5 Hruba ́ sı ́la a heuristiky Hruba ́ sı ́la je prˇı ́mocˇary ́ prˇı ́stup k rˇesˇenı ́ proble ́mu ̊ – prosteˇ zkousˇı ́me vsˇechny mozˇne ́ kombinace a oveˇrˇujeme, zda rˇesˇı ́ proble ́m. Prˇı ́mocˇare ́ pouzˇitı ́ hrube ́ sı ́ly je tedy veˇtsˇinou neefektivnı ́ a pouzˇitelne ́ pouze pro male ́ proble ́my. Nicme ́neˇ pokud vı ́me, zˇe vstupnı ́ data budou mı ́t maly ́ rozsah, mu ̊zˇe by ́t po pragmaticke ́ stra ́nce pouzˇitı ́ hrube ́ sı ́ly tı ́m nejlepsˇı ́m rˇesˇenı ́m, protozˇe implementace hrube ́ sı ́ly je cˇasto vy ́razneˇ jednodusˇsˇı ́ nezˇ implementace slozˇiteˇjsˇı ́ch algoritmu ̊. Navı ́c cˇasto ani zˇa ́dny ́ efektivneˇjsˇı ́ algoritmus nezna ́me.

Prˇı ́mocˇarou hrubou sı ́lu mu ̊zˇeme navı ́c cˇasto drobny ́mi u ́pravami vylepsˇit. Za ́kladnı ́m vylepsˇenı ́m je orˇeza ́va ́nı ́. Na za ́kladeˇ cˇa ́stecˇne ́ho rˇesˇenı ́ mu ̊zˇe by ́t mozˇne ́ rozhodnout, zˇe dana ́ veˇtev vy ́pocˇtu je neperspektivnı ́, a usˇetrˇit si tak podstatnou cˇa ́st prohleda ́va ́nı ́. Tento prˇı ́stup vede k algoritmu „zpeˇtne ́ho prohleda ́va ́nı ́ “ (backtracking), prˇi ktere ́m budujeme cˇa ́stecˇne ́ rˇesˇenı ́ a pru ̊beˇzˇneˇ ho kontrolujeme. Pokud zjistı ́me, zˇe aktua ́lnı ́ cˇa ́stecˇne ́ rˇesˇenı ́ nemu ̊zˇe by ́t platny ́m rˇesˇenı ́m, opustı ́me aktua ́lnı ́ veˇtev a vra ́tı ́me se k poslednı ́mu platne ́mu cˇa ́stecˇne ́mu rˇesˇenı ́, ktere ́ rozvineme novy ́m smeˇrem. Tento prˇı ́stup se prˇirozeneˇ implementuje pomocı ́ rekurze.

Dalsˇı ́ mozˇnost, jak hrubou sı ́lu vylepsˇit, jsou heuristiky. Heuristika je postup, ktery ́ cˇasto pomu ̊zˇe, ale nenı ́zarucˇeno, zˇe funguje. Naprˇı ́klad prˇi bloudeˇnı ́ bludisˇteˇm je jednoduchou heuristikou „preferuj cesty vedoucı ́ prˇı ́mo k cı ́li“. Toto pravidlo odpovı ́da ́ hladove ́mu algoritmu a samo o sobeˇ je pro bloudeˇnı ́ v bludisˇti nedostatecˇne ́. Mu ̊zˇe na ́m ale pomoct urychlit prohleda ́va ́nı ́ pomocı ́ hrube ́ sı ́ly.

S teˇmito pojmy souvisı ́ mnoho cvicˇenı ́. Za ́kladnı ́ hruba ́ sı ́la, tj. proste ́ vyzkousˇenı ́ vsˇech mozˇnostı ́, se vyuzˇije u u ́loh 5.4 Rozlomenı ́ sˇifer, 5.5 Prˇesmycˇky a 7.4 Logik. Backtracking se pouzˇı ́va ́ u u ́loh 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. Prohleda ́va ́nı ́ s heuristikou se pouzˇı ́va ́ u u ́loh 6.11 Sokoban, 7.6 Tetris, 7.8 Pisˇkvorky. 2.6. Grafy a stavove ́ prostory 21 2.6 Grafy a stavove ́ prostory Grafy slouzˇı ́ k zachycenı ́ vztahu ̊ mezi objekty a jsou klı ́cˇovou datovou strukturou v informatice. Graf se skla ́da ́ z vrcholu ̊ a hran, prˇicˇemzˇ hrany zachycujı ́ vztah mezi dveˇma vrcholy. Stavovy ́ prostor proble ́mu je graf, ktery ́ zachycuje vsˇechny mozˇne ́ konfigurace (vrcholy) a prˇechody mezi nimi (hrany). Naprˇı ́klad obra ́zek 6.3 zachycuje stavovy ́ prostor logicke ́ u ́lohy Hanojske ́ veˇzˇe.

Vy ́klad grafovy ́ch pojmu ̊ lze najı ́t v mnoha ucˇebnicı ́ch nebo snadno i na

Internetu. Zde pouze zmı ́nı ́me seznam za ́kladnı ́ch pojmu ̊, ktere ́ jsou pouzˇı ́va ́ny v popisech cvicˇenı ́ nebo se hodı ́ prˇi rˇesˇenı ́: cesta v grafu, de ́lka cesty, vzda ́lenost vrcholu ̊, strom, reprezentace grafu v pocˇı ́tacˇi (seznamy na ́slednı ́ku ̊, matice sousednosti), prohleda ́va ́nı ́ do sˇı ́rˇky, prohleda ́va ́nı ́ do hloubky.

Za ́kladnı ́ grafove ́ pojmy se vyskytujı ́ v cvicˇenı ́ch 6.5 Hleda ́nı ́ cest v bludisˇti,

6.6 Generova ́nı ́ bludisˇt’, 6.1 C

ˇ

ı ́selne ́ bludisˇteˇ a 8.6 Grafove ́ algoritmy. Stavove ́

prostory jsou explicitneˇ uvedeny v cvicˇenı ́ch 6.3 Hanojske ́ veˇzˇe a 6.11 Sokoban. 2.7 Objektoveˇ orientovane ́ programova ́nı ́ Objektoveˇ orientovane ́ programova ́nı ́ je programovacı ́ paradigma zalozˇene ́ na vyuzˇitı ́ objektu ̊ – datovy ́ch struktur zastrˇesˇujı ́cı ́ch data a funkce pracujı ́cı ́ s teˇmito daty (metody). Objektoveˇ orientovane ́ programova ́nı ́ je klı ́cˇove ́ prˇi programova ́nı ́ „ve velke ́m“. Cvicˇenı ́ uvedena ́ v te ́to knize se zameˇrˇujı ́ na programova ́nı ́ „v male ́m“ a na procvicˇenı ́ algoritmizace, takzˇe pouzˇitı ́ objektu ̊ nenı ́ nezbytne ́. U neˇktery ́ch prˇı ́kladu ̊ vsˇak je vyuzˇitı ́ objektu ̊ smysluplne ́ a prˇirozene ́. V teˇchto prˇı ́padech je vhodne ́ objekty vyuzˇı ́vat a procvicˇit si je. Veˇtsˇinou jde pouze o za ́kladnı ́ vyuzˇitı ́ objektu ̊, typicky pro zapouzdrˇenı ́ a zprˇehledneˇnı ́ ko ́du dı ́ky eliminaci globa ́lnı ́ch promeˇnny ́ch. Pokrocˇilejsˇı ́ prvky, jako je polymorfismus a deˇdicˇnost, se veˇtsˇinou nevyuzˇijı ́.

Vhodne ́ u ́lohy pro vyuzˇitı ́ objektoveˇ orientovane ́ho programova ́nı ́:

• na ́rocˇneˇjsˇı ́ logicke ́ u ́lohy a hry (prˇirozene ́ vyuzˇitı ́ objektu ̊ pro reprezen

taci stavu u ́lohy): 6.9 Polyomina, 6.11 Sokoban, 6.10 Sudoku, 7.6 Tetris,

8.2 Simula ́tor hry Z

ˇ

ivot,

• souboje strategiı ́ (reprezentace jednotlivy ́ch strategiı ́ pomocı ́ objektu ̊):

7.1 Ka ́men, nu ̊zˇky, papı ́r, 7.8 Pisˇkvorky, 7.9 Souboje virtua ́lnı ́ch robotu ̊,

• cvicˇenı ́ na sˇifrova ́nı ́ (5.2, 5.3, 5.4) prˇi zkombinova ́nı ́ neˇkolika zada ́nı ́ do

veˇtsˇı ́ho sˇifrovacı ́ho syste ́mu,

• veˇtsˇina logicky ́ch u ́loh a her prˇi rozsˇı ́rˇenı ́ zada ́nı ́ o interaktivnı ́ graficke ́

uzˇivatelske ́ rozhranı ́. 2. Prˇehled pojmu ̊ 2.8 Grafika Veˇtsˇina prˇı ́kladu ̊ ma ́ cˇisteˇ textove ́ vstupneˇ-vy ́stupnı ́ chova ́nı ́, takzˇe nenı ́ proble ́m je realizovat te ́meˇrˇ v jake ́mkoliv programovacı ́m jazyce. C

ˇ

a ́st prˇı ́kladu ̊

vsˇak vyuzˇı ́va ́ i grafiku. Realizace grafiky mu ̊zˇe by ́t pro zacˇı ́najı ́cı ́ programa ́tory v neˇktery ́ch programovacı ́ch jazycı ́ch trochu na ́rocˇna ́. Bylo by vsˇak sˇkoda nechat se odradit, protozˇe prˇı ́klady s graficky ́m vy ́stupem jsou atraktivnı ́. Navı ́c zde zmı ́neˇne ́ prˇı ́klady vyuzˇı ́vajı ́ jen neˇkolik za ́kladnı ́ch graficky ́ch operacı ́ a prˇi vhodne ́m prˇı ́stupu je lze take ́ docela snadno realizovat v jake ́mkoliv prostrˇedı ́.

Nejjednodusˇsˇı ́ mozˇnost je textova ́ grafika – cozˇ nenı ́ plnohodnotna ́ grafika, ale pouze simulace bitmapove ́ grafiky pomocı ́ textove ́ho vy ́stupu. Neˇkdy se tento styl grafiky nazy ́va ́ te ́zˇ „ASCII art“. Takove ́ „obra ́zky“ mu ̊zˇeme snadno realizovat pomocı ́ za ́kladnı ́ho prˇı ́kazu pro vy ́pis. Pro vykreslova ́nı ́ slozˇiteˇjsˇı ́ch obra ́zku ̊ se hodı ́ operace typu „zapisˇ znak A na pozici x,y“. V unixovy ́ch prostrˇedı ́ch (a cˇa ́stecˇneˇ i pod Windows) se za tı ́mto u ́cˇelem veˇtsˇinou pouzˇı ́va ́ knihovna curses, ktera ́ je v ru ̊zny ́ch obmeˇna ́ch dostupna ́ ve vı ́ce programovacı ́ch jazycı ́ch.

Textova ́ grafika je pouzˇita vy ́razneˇ v prˇı ́kladech 4.1 Textova ́ grafika, 7.6 Tetris, 8.2 Simula ́tor hry Z

ˇ

ivot a da ́le okrajoveˇ u veˇtsˇiny logicky ́ch u ́loh a her pro

vykreslova ́nı ́ zada ́nı ́ a rˇesˇenı ́ u ́loh.

Graficke ́ forma ́ty, ve ktery ́ch pracujeme s jednotlivy ́mi body, se nazy ́vajı ́ bitmapova ́ grafika. Obra ́zek je zde reprezentova ́n mrˇı ́zˇkou n × m bodu ̊, velikost mrˇı ́zˇky uda ́va ́ rozlisˇenı ́ (kvalitu) obra ́zku. Za ́kladnı ́ operace v bitmapove ́ grafice je prˇı ́kaz putpixel(x,y,c), ktery ́ zakreslı ́ bod barvy c na sourˇadnice x,y. U

́

secˇky, kruzˇnice a dalsˇı ́ geometricke ́ objekty se vykreslujı ́ jako posloup

nost jednotlivy ́ch bodu ̊. Pokud obra ́zek v bitmapove ́ grafice zveˇtsˇujeme, sta ́va ́ se zrnity ́m.

Pro pra ́ci s bitmapovou grafikou nabı ́zı ́ veˇtsˇina programovacı ́ch jazyku ̊ podporu skrze specializovanou knihovnu. Bud

’

ma ́me k dispozici pla ́tno (can

vas), cozˇ je samostatne ́ okno, do ktere ́ho mu ̊zˇeme vykreslovat, nebo na ́m knihovna da ́va ́ prˇı ́stup k datove ́ strukturˇe „bitmapovy ́ obra ́zek“, do ktere ́ mu ̊zˇeme zapisovat body a pote ́ obra ́zek ulozˇit a prohle ́dnout si jej v beˇzˇne ́m prohlı ́zˇecˇi obra ́zku ̊.

Bitmapova ́ grafika je pouzˇita v prˇı ́kladech: 4.4 Sierpi ́nske ́ho frakta ́l, 4.5 Bitmapova ́ grafika, 4.6 Mandelbrotova mnozˇina.

Jiny ́ zpu ̊sob reprezentace obra ́zku ̊ prˇedstavuje vektorova ́ grafika, ve ktere ́ je obra ́zek popsa ́n pomocı ́ geometricky ́ch u ́tvaru ̊. Naprˇı ́klad u ́secˇka je zada ́na sourˇadnicemi krajnı ́ch bodu ̊ a nikoliv pevny ́m vy ́cˇtem bodu ̊, jak je tomu v bitmapove ́ grafice (viz obra ́zek 2.1). Kdyzˇ vektorovy ́ obra ́zek zveˇtsˇujeme, mu ̊zˇeme libovolneˇ zlepsˇovat prˇesnost, a obra ́zek se tedy nestane zrnity ́m. Pro 2.8. Grafika 23

Obra ́zek 2.1: Ilustrace bitmapove ́ (vlevo) a vektorove ́ (vpravo) grafiky

veˇtsˇinu prˇı ́kladu ̊ uvedeny ́ch v te ́to knize vystacˇı ́me se za ́kladnı ́ operacı ́ vektorove ́ grafiky, kterou je vykreslenı ́ u ́secˇky.

Podobneˇ jako bitmapovou grafiku, i vektorovou grafiku mu ̊zˇeme ve veˇtsˇineˇ programovacı ́ch jazyku ̊ realizovat pomocı ́ vhodne ́ specializovane ́ knihovny. Alternativnı ́ zpu ̊sob, ktery ́ je zcela neza ́visly ́ na pouzˇite ́m programovacı ́m jazyce, nabı ́zı ́ forma ́t SVG (Scalable Vector Graphics). Jde o textovy ́ forma ́t zalozˇeny ́ na XML, ktery ́ mu ̊zˇeme snadno generovat programem. Vsˇe, co pro zvla ́dnutı ́ vektorove ́ho graficke ́ho vy ́stupu potrˇebujeme, je tedy umeˇt vypisovat text do souboru a nastudovat si za ́kladnı ́ syntax SVG, ktera ́ je jednoducha ́. Naprˇı ́klad pomocı ́ na ́sledujı ́cı ́ho vy ́pisu vytvorˇı ́me obra ́zek obsahujı ́cı ́ dveˇ kolme ́ protı ́najı ́cı ́ se u ́secˇky (prvnı ́ je tucˇna ́ a modra ́, druha ́ tenka ́ a zelena ́). <svg version=”1.1” xmlns=”http://www.w3.org/2000/svg”> <line x1=”100” y1=”0” x2=”100” y2=”200”

style=”stroke-width:4;stroke:rgb(00,00,99);” />

<line x1=”0” y1=”100” x2=”200” y2=”100”

style=”stroke-width:1;stroke:rgb(00,99,00);” />

</svg>

K prohlı ́zˇenı ́ SVG souboru ̊ lze pouzˇı ́t libovolny ́ webovy ́ prohlı ́zˇecˇ, umı ́ je zobrazit i mnoho graficky ́ch programu ̊, pomocı ́ ktery ́ch mu ̊zˇeme SVG soubor zkonvertovat do bitmapovy ́ch forma ́tu ̊. Pro manua ́lnı ́ u ́pravy SVG souboru ̊ lze vyuzˇı ́t volneˇ dostupny ́ editor Inkscape.

Vektorova ́ grafika je pouzˇita v prˇı ́kladech: 4.2 Z

ˇ

elvı ́ grafika: za ́klady,

4.3 Z

ˇ

elvı ́ grafika: frakta ́ly, 4.4 Sierpi ́nske ́ho frakta ́l, 4.7 Konvexnı ́ obal, 4.8 Trian

gulace, 6.6 Generova ́nı ́ bludisˇt’. Da ́le ji lze okrajoveˇ vyuzˇı ́t i u dalsˇı ́ch logicky ́ch u ́loh (naprˇ. prˇi generova ́nı ́ zada ́nı ́). 3 Pocˇı ́ta ́nı ́ s cˇı ́sly

U

́

cˇel vy ́pocˇtu ̊ je vhled, nikoliv cˇı ́sla.

R. Hamming

Tato kapitola obsahuje na ́meˇty na prˇı ́klady, ktere ́ majı ́ velmi jednoduche ́ vstupneˇ-vy ́stupnı ́ chova ́nı ́: vesmeˇs pouze nacˇtou cˇı ́sla a na vy ́stup opeˇt dajı ́ cˇı ́sla. Pocˇı ́ta ́nı ́ s cˇı ́sly pro veˇtsˇinu lidı ́ nenı ́ tak atraktivnı ́ jako trˇeba grafika, logicke ́ u ́lohy nebo hry. Nicme ́neˇ prˇı ́klady s cˇı ́sly jsou vhodne ́ jako u ́vodnı ́ cvicˇenı ́, protozˇe k nim stacˇı ́ velmi ma ́lo znalostı ́ o syntaxi konkre ́tnı ́ho jazyka. Veˇtsˇinou vystacˇı ́me s celocˇı ́selny ́mi promeˇnny ́mi, cykly, funkcemi a prˇı ́padneˇ jednorozmeˇrny ́mi poli.

Veˇtsˇina uvedeny ́ch zada ́nı ́ navı ́c ilustruje zajı ́mave ́ vlastnosti cˇı ́sel cˇi al

goritmu ̊, prˇı ́padneˇ se k u ́loha ́m va ́zˇou zajı ́mave ́ souvislosti, jako naprˇı ́klad historicke ́ zajı ́mavosti nebo nevyrˇesˇene ́ otevrˇene ́ proble ́my. Pokud o teˇchto souvislostech vı ́me, i jednoduche ́ pocˇı ́ta ́nı ́ s cˇı ́sly dosta ́va ́ na zajı ́mavosti. 3.1 Hra ́tky s cˇı ́sly

Na ́pad: 1

Ko ́dova ́nı ́: 1

Styl u ́lohy: Jednoduche ́ cvicˇenı ́ na za ́kladnı ́ procvicˇenı ́ pra ́ce s celocˇı ́selny ́mi

promeˇnny ́mi a s cykly.

Program nacˇte prˇirozene ́ cˇı ́slo n a vypı ́sˇe vy ́sledek vy ́pocˇtu nad tı ́mto cˇı ́slem. Na ́meˇty na vy ́pocˇty:

1. soucˇet prvnı ́ch n prˇirozeny ́ch cˇı ́sel,

2. faktoria ́l cˇı ́sla n, tj. soucˇin prvnı ́ch n cˇı ́sel,

3. celou cˇa ́st odmocniny z cˇı ́sla n, tj. nejveˇtsˇı ́ cele ́ x takove ́, zˇe x

2

≤ n,

4. ciferny ́ soucˇet cˇı ́sla n,

5. pocˇet jednicˇek obsazˇeny ́ch v cˇı ́sle n,

6. cˇı ́slo n zapsane ́ pozpa ́tku,

7. informace o tom, zda n je platne ́ rodne ́ cˇı ́slo. 3. Pocˇı ́ta ́nı ́ s cˇı ́sly Doplnˇujı ́cı ́ komenta ́rˇ Toto cvicˇenı ́ slouzˇı ́ prˇedevsˇı ́m k procvicˇenı ́ cyklu ̊. Z tre ́ninkovy ́ch du ̊vodu ̊ je uzˇitecˇne ́ vyrˇesˇit stejny ́ u ́kol neˇkolika ru ̊zny ́mi zpu ̊soby. V rˇesˇenı ́ch na konci knihy je naprˇı ́klad uvedeno 5 mozˇnostı ́, jak zapsat rˇesˇenı ́ prvnı ́ho u ́kolu. U prˇı ́kladu ̊ 4.–7. spocˇı ́va ́ za ́kladnı ́ princip v procha ́zenı ́ jednotlivy ́ch cifer cˇı ́sla. Toho snadno dosa ́hneme tak, zˇe cˇı ́slo postupneˇ deˇlı ́me 10 a zkouma ́me zbytek po deˇlenı ́ 10 (operace modulo). 3.2 Posloupnosti

Na ́pad: 1-3

Ko ́dova ́nı ́: 1-2

Styl u ́lohy: Procvicˇenı ́ pra ́ce s celocˇı ́selny ́mi promeˇnny ́mi, s cykly a prˇı ́padneˇ

poli.

Odhalte princip na ́sledujı ́cı ́ch posloupnostı ́ a pote ́ napisˇte pro kazˇdou z nich program, ktery ́ dostane na vstup cˇı ́slo n a na vy ́stup vypı ́sˇe prvnı ́ch n cˇlenu ̊ dane ́ posloupnosti.

1. 1, 2, 3, 4, 5, 6, . . .

2. 1, 3, 5, 7, 9, 11, . . .

3. 1, 5, 9, 13, 17, 21, 25, 29, . . .

4. 1, 2, 4, 7, 11, 16, . . .

5. 1, 2, 4, 8, 16, 32, . . .

6. 1, 2, 6, 24, 120, . . .

7. 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, . . .

8. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, . . .

9. 1, 2, 4, 7, 9, 12, 18, 24, 32, 38, 42, 50, 56, 64, 71, 73, 75, 81, . . .

10. 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, . . .

11. 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, . . .

Doplnˇujı ́cı ́ komenta ́rˇ Principy posloupnostı ́ jsou na ́sledujı ́cı ́:

1. prˇirozena ́ cˇı ́sla,

2. licha ́ cˇı ́sla, tj. aritmeticka ́ posloupnost s krokem 2,

3. aritmeticka ́ posloupnost s krokem 4,

4. aritmeticka ́ posloupnost 2. stupneˇ – rozdı ́ly mezi cˇleny tvorˇı ́ aritmetickou

posloupnost s krokem 1, tj. prˇirozena ́ cˇı ́sla,

5. mocniny dvojky, tj. geometricka ́ posloupnost s krokem 2, 3.3. Collatzu ̊v proble ́m 27

6. faktoria ́ly,

7. u ́seky prˇirozeny ́ch cˇı ́sel postupneˇ se prodluzˇujı ́cı ́ de ́lky,

8. prvocˇı ́sla,

9. dalsˇı ́ cˇlen vznikne tak, zˇe k aktua ́lnı ́mu cˇlenu prˇicˇteme pocˇet jeho deˇlitelu ̊,

10. popis prˇedchozı ́ho cˇlenu, dalsˇı ́ cˇlen dostaneme tak, zˇe prˇedchozı ́ cˇlen

„prˇecˇteme nahlas“: „jedna jednicˇka“, „dveˇ jednicˇky“, „jedna dvojka,

jedna jednicˇka“,

11. Golombova sebe-popisujı ́cı ́ posloupnost, neklesajı ́cı ́ rˇada kladny ́ch cˇı ́sel,

jejı ́zˇ n-ty ́ cˇlen rˇady uda ́va ́, kolikra ́t se opakuje cˇı ́slo n.

Prvnı ́ch 6 posloupnostı ́ lze vyrˇesˇit jednodusˇe pomocı ́ jednoho for cyklu

a neˇkolika celocˇı ́selny ́ch promeˇnny ́ch, dalsˇı ́ 3 posloupnosti vyzˇadujı ́ vnorˇene ́ cykly nebo pouzˇitı ́ pomocne ́ funkce. Z uvedeny ́ch posloupnostı ́ jsou nejna ́rocˇneˇjsˇı ́ dveˇ poslednı ́, i kdyzˇ i u nich je na ́rocˇne ́ prˇijı ́t prˇedevsˇı ́m na princip posloupnosti, programa ́torsky jsou vcelku prˇı ́mocˇare ́. V prˇı ́padeˇ posloupnosti s popisem prˇedchozı ́ho cˇlenu mu ̊zˇe by ́t vy ́hodneˇjsˇı ́ pracovat s cˇleny jako rˇeteˇzci spı ́sˇe nezˇ jako s cely ́mi cˇı ́sly. Golombova sebe-popisujı ́cı ́ rˇada vyzˇaduje pouzˇitı ́ jednorozmeˇrne ́ho pole.

Mnoho dalsˇı ́ch zajı ́mavy ́ch na ́meˇtu ̊ na zada ́nı ́ lze najı ́t v internetove ́ en

cyklopedii celocˇı ́selny ́ch posloupnostı ́ (The On-Line Encyclopedia of Integer Sequences, oeis.org). V te ́to encyklopedii je uvedena take ́ rˇada doplnˇujı ́cı ́ch komenta ́rˇu ̊ a zajı ́mavostı ́.

Zajı ́mavy ́m rozsˇı ́rˇenı ́m te ́to u ́lohy je automaticke ́ doplnˇova ́nı ́ rˇad – imple

mentace „umeˇle ́ inteligence“, ktera ́ odhalı ́ princip posloupnosti a automaticky ji doplnı ́. Toto je rea ́lne ́ jen pro relativneˇ jednoduche ́ posloupnosti,jako je prvnı ́ch 5 uvedeny ́ch posloupnostı ́. I tak tato varianta prˇedstavuje u ́kol obtı ́zˇnosti 4–5. 3.3 Collatzu ̊v proble ́m

Na ́pad: 1

Ko ́dova ́nı ́: 1

Styl u ́lohy: Programa ́torsky jednoduche ́ cvicˇenı ́, ktere ́ ilustruje velmi zajı ́mavy ́

proble ́m z teorie cˇı ́sel.

Prˇedmeˇtem tohoto cvicˇenı ́ je matematicky ́ proble ́m, ktery ́ je zna ́m pod mnoha ru ̊zny ́mi na ́zvy – kromeˇ na ́zvu Collatzu ̊v proble ́m se mu ̊zˇete setkat te ́zˇ s oznacˇenı ́m3n+1proble ́m, Ulamu ̊v proble ́m, Syrakusky ́ proble ́m a spoustou dalsˇı ́ch jmen. Proble ́m se ty ́ka ́ na ́sledujı ́cı ́ho postupu: „vezmi prˇirozene ́ cˇı ́slo, pokud je sude ́, vydeˇl jej dveˇma, pokud je liche ́, vyna ́sob jej trˇemi a prˇicˇti jednicˇku; 3. Pocˇı ́ta ́nı ́ s cˇı ́sly tento postup opakuj, dokud nedostanesˇ cˇı ́slo jedna“. Program tedy vypada ́ na ́sledovneˇ: def collatz(n):

while n != 1:

print n

if n % 2 == 0:

n = n / 2

else: