Algoritmy v jazyku

Kniha obsahuje tato témata:  Algoritmy pro třídění a vyhledávání  Binární vyhledávací stromy, AVL stromy  Algoritmy numerické matematiky  Algoritmy na grafech, toky v sítích  Dynamické programování Kniha vám mimo jiné odpoví na tyto otázky:  Jaké výhody vám přinese C++?  Jak vyvážit AVL strom?  Jak prolomit zašifrovaný text?  Kdy použít rekurzi a kdy ne?  K čemu se dají použít grafy?

Grada Publishing, a. s. U Průhonu 22, 170 00 Praha 7 tel.: +420 234 264 401 fax: +420 234 264 400 e-mail: [email protected] www.grada.cz

ISBN 978-80-247-5467-3

9 788024 754673

Algoritmy v jazyku C a C++

O autorovi Ing. Jiří Prokop je absolventem elektrotechnické fakulty ČVUT. Od roku 1968 pracoval jako programátor ve Vývojovém výpočetním středisku potravinářského průmyslu při o. p. Čokoládoven. Po vybavení střediska počítačem EC1040 zastával funkci vedoucího systémového inženýra a podílel se na projektech, které se rozšířily do mnoha výpočetních středisek v bývalém Československu. V roce 1988 absolvoval postgraduální studium Tvorba programových systémů na elektrotechnické fakultě ČVUT. Pracoval v softwarových firmách APP, Pragodata a Slavia Data a v roce 2001, kdy získal tzv. zelenou kartu, pracoval v Německu ve firmě AM-Informatik, zabývající se tvorbou informačních systémů pro pojišťovny. Jako spoluautor profesora J. Habra se podílel na práci Příspěvek k řešení jedné strategické systémové úlohy, vydané v EML ČSAV v roce 1973. Dále byl autorem řady příspěvků ve sbornících seminářů Algoritmy, SOFSEM a Programování. Od roku 2002 učí na Gymnáziu Ch. Dopplera Informatiku a výpočetní techniku, mj. volitelný předmět Programování v jazyku C.


Jiří Prokop

Třetí rozšířené a aktualizované vydání úspěšné knihy naučí čtenáře nejdůležitější algoritmy a umožní mu prohloubit si znalost jazyka C i schopnost samostatné tvorby algoritmů. Knihu mohou využít středoškolští i vysokoškolští studenti technických, ekonomických i přírodovědných směrů, ale i profesionální programátoři. Získají znalost algoritmů z následujících oblastí: třídění a vyhledávání údajů, teorie a využití grafů, numerické matematiky, dynamického programování a prohledávání textu. Kniha se vyznačuje důrazem na zdrojový text algoritmů se stručným doprovodným textem pro jejich vysvětlení, je tudíž ideální pro praxi i jako učební text. Na stránkách Grady naleznete programy ke stažení, uspořádané podle kapitol knihy.

3., aktualizované a rozšířené vydání

www.grada.cz

Algoritmy v jazyku

C a C++ 3., aktualizované a rozšířené vydání

Jiří Prokop      

Seznámení s jazykem C a úvod do C++ Vyhledávání a třídění Datové struktury a práce s grafy Algoritmy z numerické matematiky Kryptologické algoritmy Dynamické programování

Algoritmy v jazyku

C a C++ 3., aktualizované a rozšířené vydání

Jiří Prokop

Upozornění pro čtenáře a uživatele této knihy Všechna práva vyhrazena. Žádná část této tištěné či elektronické knihy nesmí být reprodukována a šířena v papírové, elektronické či jiné podobě bez předchozího písemného souhlasu nakladatele. Neoprávněné užití této knihy bude trestně stíháno.

Algoritmy v jazyku C a C++ 3., aktualizované a rozšířené vydání Jiří Prokop Vydala Grada Publishing, a.s. U Průhonu 22, Praha 7 [email protected], www.grada.cz tel.: +420 234 264 401, fax: +420 234 264 400 jako svou 5855. publikaci Odpovědný redaktor Petr Somogyi Sazba Petr Somogyi Počet stran 200 Třetí vydání, Praha 2015 Vytiskly Tiskárny Havlíčkův Brod, a.s. © Grada Publishing, a.s., 2015 Cover Design © Grada Publishing, a.s., 2015 Cover Photo © fotobanka Allphoto V knize použité názvy programových produktů, firem apod. mohou být ochrannými známkami nebo registrovanými ochrannými známkami příslušných vlastníků. ISBN 978-80-247-5467-3 (tištěná verze) ISBN 978-80-247-9746-5 (elektronická verze ve formátu PDF) ISBN 978-80-247-9747-2 (elektronická verze ve formátu EPUB)

Obsah

1.

Úvod..............................................................................................................................................9 Jazyk C.....................................................................................................................................11 1.1 Stručný přehled jazyka C......................................................................................11 1.1.1 Deklarace...........................................................................................................11 1.1.2 Výrazy a přiřazení..........................................................................................11 1.1.3 Priorita a asociativita operátorů.............................................................12 1.1.4 Příkazy a bloky................................................................................................13 1.1.5 Preprocesor......................................................................................................14 1.1.6 Funkce................................................................................................................15 1.1.7 Vstup a výstup................................................................................................15 1.1.8 Ukazatele ..........................................................................................................17 1.1.9 Adresní aritmetika.........................................................................................17 1.1.10 Ukazatele a funkce.......................................................................................18 1.1.11 Pole.......................................................................................................................18 1.1.12 Ukazatele a pole............................................................................................18 1.1.13 Řetězce znaků.................................................................................................19 1.1.14 Vícerozměrná pole.......................................................................................19

1.2 Algoritmy a jejich programování....................................................................20 1.3 Jednoduché algoritmy...........................................................................................24 1.3.1 1.3.2 1.3.3 1.3.4 1.3.5 1.3.6 1.3.7

Vyhledání minimálního prvku v nesetříděném poli...................24 Vyhledání zadaného prvku v nesetříděném poli.........................24 Určení hodnoty Ludolfova čísla.............................................................24 Mzdová výčetka.............................................................................................25 Největší společný dělitel dvou čísel....................................................26 Pascalův trojúhelník.....................................................................................26 Kalendář.............................................................................................................27

1.4 Permutace......................................................................................................................29

2. 3.

1.4.1 Násobení permutací....................................................................................29 1.4.3 Inverzní permutace......................................................................................32

Rekurze...................................................................................................................................35 2.1 Hanojské věže..............................................................................................................35 2.2 W-křivky..........................................................................................................................36 2.3 Fibonacciho čísla........................................................................................................39 2.4 Odstranění rekurze...................................................................................................40 Algoritmy pro třídění..........................................................................................43 3.1 Třídění výběrem (selectsort)..............................................................................43 3.2 Třídění vkládáním (insertsort)..........................................................................44 3.3 Bublinkové třídění (bubblesort)......................................................................44

Obsah 5

4. 5.

3.4 3.5 3.6 3.7 3.8 3.9

Časová a paměťová složitost..............................................................................46 Třídění slučováním (mergesort).......................................................................46 Třídění rozdělováním (quicksort)....................................................................47 Shellův algoritmus...................................................................................................48 Třídicí algoritmy obecněji....................................................................................48 Metoda „rozděl a panuj“ ......................................................................................49

Datové struktury.......................................................................................................51 4.1 Dynamické datové struktury..............................................................................51 4.1.1 4.1.2 4.1.3 4.1.4

Lineární spojový seznam...........................................................................52 Lineární spojový seznam obousměrný..............................................53 Lineární spojový seznam setříděný.....................................................55 Setřídění vytvořeného lineárního seznamu....................................57

4.2 Zásobník a fronta......................................................................................................59 4.3 Nerekurzivní verze quicksortu..........................................................................61 Práce s grafy.....................................................................................................................63 5.1 Úvod do teorie grafů...............................................................................................63 5.2 Reprezentace grafu v paměti počítače........................................................64 5.3 Topologické třídění..................................................................................................69 5.4 Minimální kostra grafu..........................................................................................71 5.5 Bipartitní graf.............................................................................................................73 5.6 Práce se soubory dat...............................................................................................75 5.6.1 Datové proudy...............................................................................................76 5.6.2 Proudy a vstup/výstup znaků.................................................................76 5.6.3 Proudy a vstup/výstup řetězců..............................................................77 5.6.4 Formátovaný vstup/výstup z/do proudu.........................................77 5.6.5 Proudy a blokový přenos dat..................................................................77 5.6.6 Další užitečné funkce..................................................................................77

6. 6

5.7 Vzdálenosti v grafu..................................................................................................78 5.8 Hledání nejkratší (nejdelší) cesty v acyklickém orientovaném grafu................................................................................................82 Vyhledávací algoritmy......................................................................................85 6.1 Binární hledání v setříděném poli..................................................................85 6.2 Binární vyhledávací strom...................................................................................85 6.3 Vynechání vrcholu v binárním vyhledávacím stromu........................89 6.4 Procházení stromem...............................................................................................95 6.5 AVL stromy.....................................................................................................................95 6.6 Transformace klíče................................................................................................. 102 6.7 Halda.............................................................................................................................. 102 6.8 Využití haldy pro třídění – heapsort.......................................................... 104


7. 8. 9. 10. 11. 12.

Reprezentace aritmetického výrazu binárním stromem............................................................................................... 107 7.1 Vyhodnocení výrazu zadaného v postfixové notaci......................... 107 7.2 Převod infixové notace na postfixovou.................................................... 110 7.3 Převod postfixové notace na binární strom.......................................... 113 Ještě grafy....................................................................................................................... 117 8.1 Procházení grafem................................................................................................ 117 8.2 Hledání silně souvislých komponent orientovaného grafu........ 122 8.3 Toky v sítích (Ford-Fulkersonův algoritmus)......................................... 125 Průchod stavovým prostorem............................................................. 129 9.1 Prohledávání do šířky.......................................................................................... 129 9.2 Prohledávání s návratem (backtracking)................................................ 131 9.3 Osm dam na šachovnici...................................................................................... 135 9.4 Sudoku.......................................................................................................................... 136 9.5 Hry pro dva hráče................................................................................................... 140 Kryptologické algoritmy............................................................................. 143 10.1 Základní pojmy........................................................................................................ 143 10.2 Jednoduchá (monoalfabetická) substituční šifra.............................. 143 10.3 Playfairova šifra...................................................................................................... 148 10.4 Vigenèrova šifra...................................................................................................... 151 10.5 Transpoziční šifry.................................................................................................... 152 10.6 Jednorázová tabulka (Vernamova šifra)................................................. 153 10.7 Moderní šifrování................................................................................................... 153 Úvod do C++................................................................................................................. 155 11.1 Nové možnosti jazyka.......................................................................................... 155 11.2 Objektové datové proudy.................................................................................. 155 11.3 Objektově orientované programování..................................................... 156 11.4 Šablony......................................................................................................................... 159 Algoritmy numerické matematiky................................................ 163 12.1 Řešení nelineární rovnice f(x) = 0............................................................... 163 12.1.1 Hornerovo schéma................................................................................... 163 12.1.2 Metoda půlení intervalu (bisekce).................................................... 163 12.1.3 Metoda tětiv (regula falsi)...................................................................... 165 12.1.4 Newtonova metoda (metoda tečen)............................................... 167

12.2 Interpolace................................................................................................................. 169 12.2.1 Newtonův interpolační vzorec........................................................... 169 12.2.2 Lagrangeova interpolace....................................................................... 172

Obsah 7

12.3 Soustavy lineárních rovnic............................................................................... 173 12.3.1 Gaussova eliminační metoda.............................................................. 173 12.3.2 Výpočet determinantu Gaussovou metodou............................. 176 12.3.3 Iterační (Jacobiova) metoda................................................................. 177 12.3.4 Gauss-Seidelova metoda....................................................................... 179

12.4 Numerické integrování....................................................................................... 181

13. 14.

12.4.1 Lichoběžníkový vzorec............................................................................ 181 12.4.2 Newtonovy-Cotesovy kvadraturní vzorce..................................... 182 12.4.3 Rombergova integrační metoda....................................................... 183

Dynamické programování........................................................................ 185 13.1 Roy-Warshallův algoritmus............................................................................. 185 13.2 Násobení matic........................................................................................................ 188 13.3 Problém loupežníkova batohu...................................................................... 190 Vyhledání znakového řetězce v textu...................................... 193 14.1 „Naivní“ algoritmus.............................................................................................. 193 14.2 Zjednodušený Boyer-Mooreův algoritmus............................................ 194 14.3 Karp-Rabinův algoritmus................................................................................. 195 Literatura.......................................................................................................................... 197 Rejstřík................................................................................................................................. 199

8


Úvod V roce 2002, kdy jsem na Gymnáziu Christiana Dopplera poprvé vedl seminář „Programování v jazyku C“, neexistovala na našem knižním trhu učebnice, jež by se věnovala algoritmům a používala jazyk C. Algoritmy byly po řadu let prezentovány téměř výlučně v jazyku Pascal, např. [Wir89] a [Top95]. Musel jsem tedy během šesti let pro účely výuky naprogramovat potřebné algoritmy – a tak vznikl základ této knihy. Kniha nechce být učebnicí jazyka C, i když může být k užitku všem, kdo jazyk právě studují. Dobrých učebnic jazyka je dostatek, doporučit lze např. [Her04] nebo [Ka01], pro C++ pak [Vi02], [Vi97]. Přesto jsem do knihy zařadil alespoň stručný přehled jazyka C a také úvod do C++. Je to proto, aby čtenář měl při studiu knihy vše potřebné pro porozumění zdrojovým textům algoritmů po ruce a nemusel hledat informace jinde. Kdo je s jazykem C seznámen do té míry, že zná nejdůležitější operátory, výrazy a přiřazení, příkazy pro řízení programu, příkazy vstupu a výstupu, funkce a vedle jednoduchých datových typů ještě pole, je už ke studiu jednoduchých algoritmů dostatečně vybaven. Potřebný přehled jazyka obsahuje právě první kapitola, následně lze studovat druhou, věnovanou rekurzi, a třetí, která se zabývá třídicími algoritmy. Teprve v kapitole 4 je pro studium datových struktur nutné rozšířit zatím popsanou podmnožinu jazyka o struktury a dynamické přidělování paměti. Tyto znalosti jsou pak potřebné i pro pochopení algoritmů na grafech a pro vyhledávání pomocí binárních stromů. Stromy se využívají rovněž k reprezentaci aritmetických výrazů a pro počítačové řešení hlavolamů a her. Popsaná podmnožina jazyka je v těchto kapitolách dále podle potřeby rozšiřována. Algoritmy z kapitol 1 až 8 jsou napsány v jazyku C, teprve 9. kapitola je úvodním popisem C++, algoritmy v dalších kapitolách jsou již v C++. Z tohoto stručného průvodce obsahem knihy vyplývá samozřejmé doporučení studovat jednotlivé kapitoly postupně, bez přeskakování, protože v každé kapitole se už počítá s tím, co si čtenář osvojil z kapitol předchozích. Výjimkou jsou části přidané ve druhém vydání této knihy, ty je možné při prvním čtení přeskočit. Jedná se o podkapitoly 1.3 (Permutace), 6.5 (AVL stromy), o kapitolu 9 (Kryptologické algoritmy) a podkapitolu 11.4 (Numerické integrování). Podobně je možné přeskočit některé části, o něž bylo rozšířeno vydání třetí (například podkapitoly 8.3, 13.1 a 13.2). Rovněž mohu vřele doporučit aktivní studium, pomůže k tomu fakt, že všechny algoritmy rozdělené podle kapitol najdete na webových stránkách nakladatelství Grada (www.grada.cz). Zdrojové texty tedy není potřeba pracně vkládat, čtenář může provádět v programech úpravy (mnohde k tomu zdrojový text přímo vybízí tím, že jeho části jsou „ukryté“ v komentářích). Často lze algoritmus snáze pochopit, zobrazíme-li některé mezivýsledky. Aktivní způsob studia je kromě toho určitě mnohem zajímavější. Algoritmy byly ověřeny s použitím kompilátoru Dev C++, některé i pomocí kompilátoru Microsoft Visual C++. Třetí vydání, které držíte v rukou, bylo rozšířeno o kapitolu 8 (další algoritmy na grafech), dále pak o podkapitoly 1.2, 2.4, 4.1.2, 12.3.2, 13.1 a 13.2. Pro toto vydání byly rovněž připraveny nové kvalitnější ilustrace, za což patří poděkování mým kolegům Mgr. Ondřeji Machů a Mgr. Michaele Švecové. Čtenář, který by měl ke knize jakékoli připomínky, mě může kontaktovat na e-mailové adrese [email protected]. Na závěr už jen zbývá popřát všem čtenářům mnoho úspěchů při studiu!

Úvod 9

1.

Jazyk C

1.1 Stručný přehled jazyka C Jazyk C rozlišuje velká a malá písmena. „Prog“, „prog“ a „PROG“ jsou tedy tři různé identifikátory. Identifikátory sestávají z písmen, číslic a podtržítka, číslice nesmí být na prvním místě. Pro oddělování klíčových slov, identifikátorů a konstant slouží oddělovače (tzv. „bílé znaky“). Všude tam, kde mohou být oddělovače, může být komentář. /* toto je komentář */

Struktura programu: direktivy preprocesoru, deklarace, definice, funkce. V každém programu je právě jedna funkce hlavní (main), jež se začne po spuštění programu vykonávat.

1.1.1 Deklarace

Deklarace jsou povinné. Deklaraci jednoduché proměnné tvoří specifikátor typu a jméno (identifikátor proměnné). int a; /* deklarace celočíselné proměnné a */ int b=1; /* definice proměnné b */

Podle umístění dělíme deklarace na globální (na začátku programu) a lokální (v těle funkce). Lokální proměnné nejsou implicitně inicializovány a obsahují náhodné hodnoty. Specifikátory typu pro celá čísla: int, char, short int (nebo jen short), long int (nebo jen long). Každý z nich může být signed (se znaménkem) nebo unsigned (bez znaménka), implicitně je signed. Specifikátory typu pro racionální proměnné: float (32 bitů), double (64), long double (80). U konstant je typ dán způsobem zápisu. Pomocí klíčového slova const můžeme deklarovat konstantní proměnnou, jejíž obsah nelze později měnit: const float pi=3.14159;

1.1.2 Výrazy a přiřazení

Výrazy jsou v jazyce C tvořeny posloupností operandů a operátorů. Operátory dělíme podle arity (počet operandů) na unární, binární a ternární, podle funkce na aritmetické: +, –, *, /, % pro zbytek po dělení (operátor / má význam reálného nebo celočíselného dělení podle typů operandů), relační: >, <, >=, <=, == (rovnost), != (nerovnost), logické: || (log. součet), && (log. součin), ! (negace). Jazyk C nezná logický typ, nenulová hodnota představuje true, nulová false. Podmíněný operátor ? (jediný ternární operátor): x=(a
má stejný význam jako if (a
Obecně: v1 ? v2 : v3

Jazyk C 11

v1 je výraz, jehož hodnota je po vyhodnocení považována za logickou. Je-li true, vyhodnotí se výraz v2 a vrátí se jeho hodnota, je-li false, pak se vyhodnotí v3 a vrátí se jeho hodnota. v2 a v3 jsou jednoduché výrazy. Operátory přiřazení: a=a+b; a+=b; /* má význam a=a+b; */

Na místě + může být –, *, /, %, & a další, o nichž zatím nebyla řeč. Operátory inkrementace a dekrementace: a++; /* postfixová verze */ --a; /* prefixová verze */

Příklad: a=10; x=++a; /* x bude mít hodnotu 11, a také */ y=a--; /* y=11, a=10 */

Unární operátory: adresní operátor &, operátor dereference *, unární +, unární -, logická negace ! a prefixová inkrementace ++ a dekrementace --. K postfixovým operátorům patří operátor přístupu k prvkům pole [ ], operátor volání funkce ( ), postfixová inkrementace ++ a dekrementace -- a operátory přístupu ke členům struktury, jimž se budu věnovat později. Operátor přetypování předvedeme na příkladu (i1 a i2 jsou celočíselné proměnné, ale my chceme reálné dělení): f=(float) i1/i2;

Operátor sizeof pro zjištění velikosti: argumentem operátoru může být jak název typu, tak identifikátor proměnné.

1.1.3 Priorita a asociativita operátorů

Prioritu a asociativitu operátorů zachycuje následující tabulka. Priorita 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Operátory ( ) [ ] -> postfix. ++ -! - pref. ++ -- + - (typ) * & sizeof */% (multiplikativní operátor) +(aditivní operátory) << >> (operátory posunů) < <= > >= (relační operátory) == != (rovnost, nerovnost) & (operátor bitového součinu) ^ (exkluzivní nebo) | (operátor bitového součtu) && (operátor logického součinu) || (operátor logického součtu) ?: (ternární podmínkový operátor) = += -= *= /= %= >>= &= |= ^= , (operátor čárky) Tabulka 1.1: Priorita a asociativita operátorů

12 Algoritmy v jazyku C a C++

Vyhodnocuje se zleva doprava zprava doleva zleva doprava zleva doprava zleva doprava zleva doprava zleva doprava zleva doprava zleva doprava zleva doprava zleva doprava zleva doprava zprava doleva zprava doleva zleva doprava

1.1.4 Příkazy a bloky

Napíšeme-li za výraz středník, stává se z něj příkaz, jako je tomu v následujících příkladech: float x,y,z; x=0; a++; x=y=z; y=z=(f(x)+3); /* K hodnotě vrácené funkcí f je přičtena hodnota 3. */ /* Součet je přiřazen jak proměnné z, tak y. */

Příkazy v jazyce C můžeme sdružovat do tzv. bloků nebo složených příkazů. Blok může na počátku obsahovat deklarace proměnných a dále pak jednotlivé příkazy. Začátek a konec bloku je vymezen složenými závorkami. Složené příkazy používáme tam, kde smí být použit pouze jeden příkaz, ale potřebujeme jich více. Za uzavírací složenou závorku se nepíše středník. Příkaz if má dvě podoby: if (výraz) příkaz

nebo if výraz příkaz1 else příkaz2;

Složitější rozhodovací postup můžeme realizovat konstrukcí if else if. Každé else se váže vždy k nejbližšímu předchozímu if. Příkaz switch a break: switch(výraz) { case konst_výraz1: /* příkazy, které se provedou, když výraz=výraz1 */ break; case konst_výraz2: /* příkazy, které se provedou, když výraz=výraz2 */ … break; default: /* příkazy, které se provedou, není-li výraz roven žádnému z předchozích konstantních výrazů */ }

Příkaz break říká, že tok programu nemá pokračovat následujícím řádkem, nýbrž prvním příkazem za uzavírající složenou závorkou příkazu case. V těle příkazu switch budou provedeny všechny vnořené příkazy počínaje tím, na nějž bylo předáno řízení, až do konce bloku (pokud některý z příkazů nezpůsobí něco jiného – např. break). Tím se switch značně liší od příkazu case v Pascalu. Příkaz while: while (výraz) příkaz;

Výraz za while představuje podmínku pro opakování příkazu. Není-li podmínka splněna už na začátku, nemusí se příkaz provést ani jednou. Je-li splněna, příkaz se provede a po jeho provedení se znovu testuje podmínka pro opakování cyklu. Příkaz do-while zajistí alespoň jedno provedení těla cyklu, protože podmínka opakování se testuje na konci cyklu: do příkaz while (výraz);

Jazyk C 13

Příkaz for má nejčastější podobu for (i=0;i
Tento tvar je ekvivalentní zápisu: inicializační výraz; while (podmíněný výraz) { příkaz opakovaný výraz }

Inicializační výraz může být vypuštěn, zůstane po něm však středník. Stejně může být vynechán i podmíněný výraz a opakovaný výraz. Příkaz continue je možné použít ve spolupráci se všemi uvedenými typy cyklů. Ukončí právě prováděný průchod cyklem a pokračuje novým průchodem. Podobně i příkaz break může být použit ve všech typech cyklů k jejich ukončení. Příkaz goto a návěští: příkaz goto přenese běh programu na místo označené návěštím (identifikátor ukončený dvojtečkou). Jsou situace, kdy může být výhodný, např. chceme-li vyskočit z vnitřního cyklu z více vnořených cyklů. Prázdný příkaz se používá všude tam, kde je prázdné tělo, a má podobu: ;

Funkce system() umožňuje vyvolat z programu příkaz operačního systému. Nejčastěji ji použijeme na konci programu těsně před jeho ukončením, a to v podobě: system("PAUSE");

1.1.5 Preprocesor

Preprocesor zpracuje zdrojový text programu před překladačem, vypustí komentáře, provede záměnu textů (například identifikátorů konstant) za odpovídající číselné hodnoty a vloží texty ze specifikovaných souborů. Příkazy pro preprocesor začínají znakem # a nejsou ukončeny středníkem. Nejdůležitějšími příkazy jsou #define a #include. Příkaz #define ID hodnota říká, že preprocesor nahradí všude v textu identifikátor ID specifikovanou hodnotou, například: #define PI 3.14159 #include <stdio.h>

znamená příkaz vložit do zdrojového textu funkce vstupu a výstupu ze systémového adresáře. Další příkaz: #include "filename"

znamená, že preprocesor vloží text ze specifikovaného souboru v adresáři uživatele. Některé standardní knihovny jsou následující: zz stdio.h funkce pro vstup a výstup, zz stdlib.h obecně užitečné funkce, zz string.h práce s řetězci, zz math.h matematické funkce v přesnosti double, zz time.h práce s datem a časem.


1.1.6 Funkce

Každá funkce musí mít definici a zz má určené jméno, jehož pomocí se volá, zz může mít parametry, v nichž předáme data, na kterých se budou vykonávat operace, zz může mít návratovou hodnotu poskytující výsledek, zz má tělo složené z příkazů, které po svém vyvolání vykoná. Příkazy jsou uzavřeny ve složených závorkách {}. Příkaz return vyraz; vypočte hodnotu vyraz, přiřadí ji jako návratovou hodnotu funkce a funkci ukončí. Příklad: int max(int a, int b) /* hlavička */ { if (a>b) return a; return b; }

Nevrací-li funkce žádnou hodnotu, píšeme v místě typu návratové hodnoty void. Nepředáváme-li data, uvádíme jen kulaté závorky nebo void. Neznáme-li definici funkce a přesto ji chceme použít, musíme mít deklaraci funkce (prototyp), která určuje jméno funkce, paměťovou třídu a typy jejích parametrů. Na rozdíl od definice funkce již neobsahuje tělo a je vždy ukončena středníkem: int max(int a, int b);

Nebo jen: int max(int,int);

Pokud neuvedeme paměťovou třídu, je automaticky přiřazena třída extern. Je-li funkce definována v paměťové třídě extern (explicitně nebo implicitně), můžeme definici funkce umístit do jiného zdrojového souboru. Funkce je společná pro všechny moduly, z nichž se výsledný program skládá, a může být volána v libovolném modulu. Je-li deklarována ve třídě static, musí její definice následovat ve stejné překladové jednotce a je dostupná pouze v jednotce, ve níž je deklarována a definována. Volání funkcí vypadá následovně: výraz(seznam skutečných parametrů);

Nemá-li funkce žádné parametry, musíme napsat (). Parametry se vždy předávají hodnotou, jsou tedy následně překopírovány do formálních parametrů funkce. Rekurzivní funkce jsou v C dovoleny.

1.1.7 Vstup a výstup

Standardní vstup a výstup má tuto podobu: stdin, stdout. Standardní vstup a výstup znaků vypadá takto: int getchar(void); int putchar(int znak);

/* načte 1 znak */ /* výstup 1 znaku */

Pro načtení a výstup celého řádku znaků: char *gets(char *radek); int puts(const char *radek);

Funkce gets načte znaky ze standardního vstupu, dokud nenarazí na přechod na nový řádek. Ten už není do pole zapsán. Návratovou hodnotou je ukazatel předaný funkci jako parametr. Pokud došlo k nějaké chybě, má hodnotu NULL. Na řádku nesmíme zadat více znaků, než je velikost pole.

Jazyk C 15

Funkce puts vypíše jeden řádek textu, za který automaticky přidá přechod na nový řádek. Samotný řetězec nemusí tento znak obsahovat. V případě, že výstup dopadl dobře, vrátí funkce nezápornou hodnotu, jinak EOF. Formátovaný vstup a výstup: použijeme funkce printf a scanf s následujícími deklaracemi: int printf(const char *format,…); int scanf(const char *format,…);

Obě funkce mají proměnný počet parametrů, který je určen prvním parametrem – formátovacím řetězcem. Formátovací řetězec funkce printf může obsahovat dva typy informací. Jednak jde o běžné znaky, které budou vytištěny, dále pak o speciální formátovací sekvence znaků začínající znakem % (má-li být % jako obyčejný znak, je třeba jej zdvojit). K tisknutelným znakům patří i escape sekvence, například \n. Funkce scanf se liší tím, že formátovací řetězec smí obsahovat jen formátovací sekvence, a dále pak tím, že druhým a dalším parametrem je vždy ukazatel na proměnnou (adresa proměnné). Formátovací sekvence (printf) vypadá následovně: %[příznak] [šířka] [přesnost] [F] [N] [h] [l] [L] typ

Typ: d, i o u x, X f e, E g, G

znaménkové decimální číslo typu int, neznaménkové oktalové číslo typu int, neznaménkové decimální číslo typu int, neznaménkové hexadecimální číslo typu int, pro x tištěno a, b, c, d, e, f; pro X pak A, B, C…, znaménkové racionální číslo formátu [-] dddd.dddd, float i double, znaménkové racionální číslo ve formátu s exponentem [-d]d.ddde[+|-]ddd, znaménkové racionální číslo ve formátu bez exponentu nebo s exponentem (v závislosti na velikosti čísla), jednoduchý znak, ukazatel na pole znaků ukončené nulovým znakem, tiskne argument jako ukazatel, ukazatel na číslo typu int, do něhož se uloží počet vytištěných znaků.

c s p n Příznak: - výstup zarovnán zleva a doplněn zprava mezerami, + u čísel vždy znaménko, mezera kladné číslo mezera, záporné minus, # závisí na typu. Šířka: n alespoň n znaků se vytiskne doplněno mezerami, 0n je vytištěno alespoň n znaků doplněných zleva nulami, * šířka dána následujícím parametrem. Přesnost: (nic) je různá podle části typ, .0 standardní, .n n desetinných míst, * přesnost dána následujícím parametrem, h argument funkce chápán jako short int – pouze pro d, i, o, u, x, X, l long int, L long double. Formátovací sekvence (scanf) pak má tuto podobu: %[*][šířka][F|A][h|l|L]typ


Typ: d u o x i a e, f, g fl s c * šířka

celé číslo, celé číslo bez znaménka, oktalové číslo, hexadecimální číslo, celé číslo (s předponou o oktalové, 0x hexadecimální), počet přečtených znaků do aktuálního okamžiku, racionální čísla typu float, lze modifikovat pomocí l, L, racionální čísla typu double, řetězec znaků na vstupu oddělený mezerou od ostatních znaků, jeden znak, přeskočení dané položky vstupu, maximální počet znaků vstupu pro danou proměnnou.

Příkazy sprintf a sscanf realizují formátovaný vstup a výstup z paměti. Potřebují textový řetězec, který se bude chovat jako standardní vstup/výstup: int sprintf(char *buffer,const char *format,…); int sscanf(char *buffer,const char *format,…);

1.1.8 Ukazatele

Ukazatel je proměnná, jejíž hodnotou je adresa jiné proměnné nebo funkce. Deklarace ukazatele se skládá z uvedení typu, na nějž ukazujeme, a jména ukazatele, doplněného zleva hvězdičkou. int *pCeleCis; /* může ukazovat na libovolné místo, kde je uložena proměnná typu int */ float *pReal1, *pReal2; /* ukazatele na libovolné proměnné typu float */

Ukazatel po svém založení neukazuje na žádnou platnou proměnnou a označujeme ho jako neinicializovaný ukazatel. S hodnotou neinicializovaného ukazatele nesmíme nikdy pracovat. Inicializaci ukazatele můžeme provést například pomocí operátoru &, který slouží k získání adresy objektu. int Cislo=7; int *pCislo; pCislo=&Cislo;

Jakmile ukazatel odkazuje na smysluplné místo v paměti, můžeme s ním pracovat. K tomu potřebujeme ještě operátor *, kterému říkáme operátor dereference. int x, y=8; int *pInt; pInt=&y; x=*pInt; /* v x je 8 */ y=*pInt+20; /* do y se uloží součet obsahu proměnné, na kterou ukazuje pInt, a konstanty 20 */

1.1.9 Adresní aritmetika

Význam aritmetických operací s ukazateli spočívá ve zvýšení přehlednosti a zrychlení chodu programu. Aritmetika ukazatelů je omezena na operace sčítání, odčítání, porovnání a unární operace inkrementace a dekrementace. Jestliže p je ukazatel, p++ inkrementuje p tak, že zvýší jeho hodnotu nikoli o jedničku, nýbrž o počet bytů představující velikost typu, na který ukazatel p ukazuje. y=*(pInt+50); /* zde zvětšuji hodnotu ukazatele o 50*sizeof(int) */

Jazyk C 17

*

1.1.10 Ukazatele a funkce

Má-li funkce vrátit více než jednu hodnotu, použijeme ukazatele: void vymen(int *px, int *py) { int pom; pom=*px; *px=*py; *py=pom; } int a=7,b=4; vymen(&a, &b); /* tím vlastně dosáhneme předání odkazem */

Ukazatel na funkci a funkce jako parametry funkcí: Definice double (*pf)(); definuje pf jako ukazatel na funkci vracející hodnotu typu double. Dvojice prázdných závorek je nezbytná, jinak by pf byl ukazatel na double. Závorky kolem jména proměnné jsou také nutné, protože double *pf() znamená deklaraci funkce pf, která vrací ukazatel na double. Přiřadíme-li ukazateli pf jméno funkce, můžeme tuto funkci vyvolat příkazem pf(); i (*pf)();. Jméno funkce je tedy adresou funkce, podobně jako jméno pole je adresou pole. Ukazatel, jemuž jsme přiřadili jméno funkce, může být předán i jako parametr jiné funkci. Příklad užitečné aplikace této možnosti si popíšeme v podkapitole 3.8.

1.1.11 Pole

Pole je datová struktura složená z prvků stejného datového typu. Deklarace pole vypadá obecně takto: typ id_pole [pocet];

V hranatých závorkách musí být konstantní výraz, který udává počet prvků pole. Pole v jazyku C začíná vždy prvkem s indexem nula, nejvyšší hodnota indexu je počet prvků minus 1. Jazyk C zásadně nekontroluje meze polí! K prvkům pole přistupujeme pomocí indexu, například id_pole[0] pro první prvek pole. Indexem může být výraz. Pole můžeme při deklaraci inicializovat konstantami uvedenými mezi složenými závorkami a oddělovanými čárkou: int pole[5]={6,7,8,9,10}

Počet inicializátorů by měl být menší nebo roven počtu prvků pole. Má-li pole být parametrem funkce, bude formální parametr tvořen typem a identifikátorem pole, následovaným prázdnými hranatými závorkami, například double pole[]. Jako skutečný parametr stačí jméno pole, tedy adresa začátku pole. Pole se tedy předává (na rozdíl od jednoduchých proměnných) odkazem. Pole nemůže být typem návratové hodnoty funkce (i když struktura obsahující pole jím být může). S polem jako celkem není možné provádět žádné operace, s výjimkou určení velikosti pole operátorem sizeof a určení adresy pole operátorem &. int b[8]; int i=sizeof(b); /*

8*sizeof(int)

*/

1.1.12 Ukazatele a pole int x[12]; /* deklarace pole o 12 prvcích, indexy jsou 0 až 11 */ /* &x[i] = adresa pole x + i * sizeof(typ) */ int *pData; pData=&data[0]; /* není totéž jako pData=&data */ for(i=0;i<12;i++) (pData+i)=0; /* nulování pole - přičítá se i-násobek délky typu - adresní aritmetika */


Inicializaci ukazatele pData můžeme zapsat i takto: pData=data; což je stejné jako: pData=&data[0];. Máme-li deklaraci: int i, *pi, a[N]; /* a[0] je totéž jako &a[0], a, anebo a+0 */

a+i je totéž jako &a[i], *(a+i) je totéž jako a[i]. Je-li N=100 a přiřadíme-li pi=a;, mají výrazy uvedené níže stejný význam: a[i], *(a+i), pi[i], *(pi+i)

1.1.13 Řetězce znaků

Řetězec je jednorozměrné pole znaků ukončené speciálním znakem '\0', který má funkci zarážky. Řetězcové konstanty píšeme mezi dvojici uvozovek, uvozovky v řetězcové konstantě musíme uvést zpětným lomítkem. "abc" je konstanta typu řetězec délky 3+1 znak, "a" je rovněž řetězcovou konstantou délky 1+1, 'a' je znaková konstanta délky 1. Překopírování textového řetězce provedeme následovně: void strcpy(char cil[ ],char zdroj[ ]) /* pro funkci strcpy je potřebné #include <string.h> */ { int i; for (i=0; zdroj[i]!='\0'; i++) cil[i]=zdroj[i]; cil[i]='\0'; }

Alternativně lze postupovat takto: void strcpy(char *cil, char *zdroj) { while(*cil++ = *zdroj++); }

Nejdříve dojde k přiřazení odpovídajících buněk polí, oba ukazatele jsou pak posunuty a výsledek přiřazení je rovněž chápán jako logická hodnota. Nastal-li konec řetězce, cyklus dále nepokračuje.

1.1.14 Vícerozměrná pole

Jazyk C zná pouze jednorozměrné pole. Prvky pole mohou ovšem být libovolného typu, tedy například opět pole, a to umožňuje pracovat s vícerozměrnými poli. Příklad deklarace dvojrozměrného pole: int pole2d [10][20];

Uložení v paměti je po řádcích. Ve funkcích, kde je pole parametrem, nemusíme předat nejvyšší rozměr, všechny ostatní ano. Práci s vícerozměrným polem demonstrujme na příkladu: máme překlopit čtvercovou matici podle hlavní diagonály, tedy vyměnit vzájemně prvky aij a aji pro všechna i různá od j.

Jazyk C 19

void Preklop(float m[][3]) /* překlopení čtvercové matice 3 x 3 podle hlavní diagonály */ { int i,j; float pom; for(i=0;i<2;i++) for(j=1;j<2;j++) { pom=m[i][j]; m[i][j]=m[j][i]; m[j][i]=pom; } }

V hlavním programu jsou deklarace: float a[3][3]; int pocet = 3;

Funkce je volána příkazem: Preklop(a);

Nedostatkem je, že může být překlopena jen matice 3 × 3. Následující funkce je obecnější, využívá toho, že matice je uložena po řádcích, a dovoluje překlopení matice nxn: void Preklop(float *m, int n) /* překlopení čtvercové matice n x n podle hlavní diagonály */ { int i,j; float pom; for(i=0;i
V hlavním programu může vypadat deklarace například takto: float a[4][4]; int pocet=4;

Funkce se volá příkazem: Preklop(a,pocet);

1.2 Algoritmy a jejich programování Algoritmus je konečná posloupnost kroků, po jejichž provedení dojdeme k určitému předem danému cíli (například ke správnému výsledku). Je nutné, aby splňoval následující vlastnosti: musí být konečný, tzn. skončit po konečném počtu kroků (to je sice požadavek velmi samozřejmý, ale všichni, kdo mají zkušenost s praktickým programováním, dobře vědí, jak snadno lze udělat chybu, která způsobí uváznutí v nekonečné smyčce), musí být hromadný, tedy řeší nikoli jednu úlohu, nýbrž celou třídu podobných úloh. Jednotlivé kroky algoritmu musí být definovány jednoznačně. Po každém kroku proces buď skončí – a pokud ne, je známo, kterým krokem pokračuje. Algoritmus je nejlépe popsán zápisem v programovacím jazyce, kde je význam příkazů přesně definován. Často


se setkáváme s popisem v přirozeném jazyce, ale zde je nutné na jednoznačnost dávat větší pozor. Každý algoritmus má nějaké vstupy (hodnoty, z nichž vychází) a výstupy, které jsou jeho výsledkem. Požadavek konečnosti musíme z praktických důvodů zesílit a chtít, aby algoritmus skončil v „rozumně krátkém čase“. Proto má velký význam efektivita algoritmu, které se budeme podrobněji věnovat v podkapitole 3.4. Čtenář této knihy může nabýt dojmu, že se často prohřešuji proti požadavku hromadnosti. Mnoho programů má vstupní data dána v konstantách, místo aby se načetla z klávesnice nebo souboru. Má to ovšem dobrý důvod: při pokusech se zdrojovým textem není nutné se neustále cvičit v práci s klávesnicí, kromě toho lze všechny programy snadno upravit tak, aby data načítaly ze souborů nebo z klávesnice. Pro návrh algoritmu se používaly vývojové diagramy. Na obrázku 1.1 je vývojový diagram pro řešení kvadratické rovnice.

z čti a, b, c a=0ib=0

ANO

Tisk Není rovnice

NE

x1 = –c/b Tisk x1

NE

Tisk Nemá řešení

K

NE a≠0 ANO d = b2 – 4ac d≥0 ANO x1 = (–b + √d) / 2a x2 = (–b – √d) / 2a

Tisk x1, x2

Obrázek 1.1: Vývojový diagram pro výpočet řešení kvadratické rovnice

Kroužek s písmenem Z znamená začátek, kroužek s písmenem K konec výpočetního postupu. Program napsaný podle tohoto vývojového diagramu je zde: /* kvadrovnice.c */ #include <stdio.h> #include #include <math.h> int main() { double a,b,c,d,x1,x2; printf ("zadejte koeficienty:\n"); scanf ("%lf %lf %lf",&a,&b,&c); if((a==0) && (b==0)) printf("To neni rovnice\n"); else if (a!=0) { d=b*b-4*a*c; printf ("d=%f\n",d); if (d>=0)

Jazyk C 21

{ x1=(sqrt(d)-b)/(2*a); x2=(-sqrt(d)-b)/(2*a); printf("x1=%f",x1); printf(" x2=%f\n",x2); } else if (d<0) printf("Rovnice nema reseni\n"); else {x1=(-b)/(2*a); printf("x=%f\n",x1);} } else { x1=-c/b; printf("x=%f",x1); } system("PAUSE"); return 0; }

Později vzniklo strukturované programování, jemuž se nyní budeme věnovat, a vývojové diagramy nahradily struktogramy. Podívejme se, jak k tomu došlo. V roce 1964 Boehm a Jacopini dokázali, že každý program lze sestavit s použitím pouze tří základních konstrukcí: sekvence, selekce (výběr, větvení) a iterace. Nesnažili se vyvodit z toho nějaké důsledky pro praktické programování. Na konci šedesátých let minulého století se však hledaly důvody nízké efektivity práce programátorů, zejména v případech nezbytných úprav dříve vytvořených programových systémů. Výsledkem bylo empirické zjištění, že špatná čitelnost a nesrozumitelnost zdrojových textů je přímo úměrná četnosti použitého příkazu goto. Dijkstra a Wirth se stali průkopníky metodiky strukturovaného programování, spočívající v rozdělování složitého problému na více jednodušších, které jsou opět děleny na jednodušší. Tento proces postupného zjemňování struktury programu nakonec vede k výsledku složenému právě z oněch základních konstrukcí. Protože všechny tři konstrukce mají jeden vstup a jeden výstup, je možné je prostě klást na sebe a vynechat z vývojového diagramu spojnice se šipkami. Pak můžeme postup pro řešení kvadratické rovnice znázornit následujícím struktogramem: čti a, b, c a = 0 i b = 0? NE

ANO a ≠ 0?

ANO

d ≥ 0?

x1 = (–b + √d) / 2a x2 = (–b – √d) / 2a

Tisk Není rovnice

x1 = –c/b

d = b2 – 4ac ANO

NE

NE

Tisk x1

Neexistuje řešení

Tisk x1, x2

Obrázek 1.2: Struktogram pro řešení kvadratické rovnice


Iterace podmínka cyklu tělo cyklu

Selekce podmínka

ANO příkazy 1

NE příkazy 2

Obrázek 1.3: Symbolické znázornění iterace a selekce

Je ovšem důležité, aby programovací jazyk obsahoval potřebné konstrukce, tedy příkaz typu if-then, případně if-then-else pro selekci; pro iteraci se ukázaly vhodnými tři konstrukce: while, do-while a for, navíc pak ještě doplněné příkazy continue a break. Prvním jazykem, splňujícím požadavky strukturovaného programování, se stal Pascal. Starší jazyky Fortran, Cobol, PL/1 se pak postupně upravovaly. Například Cobol86 už nezná příkaz alter, který dokonce umožňoval modifikovat návěští v programu použitých příkazů goto. Někteří programátoři se však vydali mylnou cestou, když ztotožnili pojem „strukturované programování“ s pojmem „programování bez goto“. Vznikly dokonce „receptáře“ s návody, jak v programech nahrazovat goto jinými konstrukcemi. To byl hluboký omyl: žádnými úpravami špatně navrženého programu už nemůžeme získat program dobrý. Kromě toho příkaz goto není sám o sobě nijak škodlivý, škodí jen jeho nadbytečné používání tam, kde se bez něj snadno obejdeme. Metodě strukturovaného programování se říká také metoda shora dolů, anglicky top to down. Název asi vznikl z toho, že takto vytvořený program lze číst také „shora dolů“. Ve většině programů se problém snadno rozdělí například na načtení vstupních dat, kontrolu jejich formální správnosti, vlastní výpočet a zobrazení (tisk) výsledku. S metodou strukturovaného programování byl často spojován požadavek snadné čitelnosti zdrojového textu, aby „čtenářem“ mohl být nejen počítač, ale i člověk. Dosáhneme toho jednak dodržováním určitých zvyklostí (například každý příkaz na jednom řádku) charakteristických pro daný jazyk, a také vhodným využíváním komentářů. Postup shora dolů není ovšem jedinou správnou možností. Jazyk Simula byl prvním programovacím jazykem, kde byla použita datová struktura „třída“. Nejrozšířenějším jazykem s třídami je C++. Třída slouží k vytváření objektů tvořených nejen datovými prvky, ale také funkcemi (v tomto případě jim říkáme metody), které mohou mít jako jediné možnost s daty třídy pracovat. Tím je zabráněno možnosti neoprávněné změny dat objektu. Společnou definici dat a metod označujeme jako zapouzdření (encapsulation). Další důležitou vlastností je dědičnost. Umožňuje vytvářet k objektům „podobjekty“ – nemusíme tedy znovu programovat všechny metody, podobjekty je „zdědí“. Jazyk C++ umožňuje tzv. přetěžování operátorů i funkcí. Této vlastnosti se říká polymorfismus. Představme si, že máme napsat program, který bude pracovat s komplexními čísly. Pak bude vhodné definovat třídu nazvanou třeba komplex, která bude sloužit pro vytváření objektů pro ukládání kom-

Jazyk C 23

plexních čísel. Zároveň vytvoříme metody pro operace s komplexními čísly, přetížíme operátory + a * pro sčítání a násobení komplexních čísel atd. A všimněme si, že toto je postup zdola nahoru, protože nejdříve vytváříme prostředky, které nám usnadní pozdější práci. Podrobnější informace najde čtenář v podkapitole 11.3.

1.3 Jednoduché algoritmy Než se pustíme do složitějších algoritmů, procvičme znalosti jazyka C na jednoduchých příkladech.

1.3.1 Vyhledání minimálního prvku v nesetříděném poli int hledej(p[ ],n]) { int i,min,imin; min=p[0]; imin=0; for(i=1;i
1.3.2 Vyhledání zadaného prvku v nesetříděném poli int najdi(p[ ],n,x) { int i; for(i=0;i
1.3.3 Určení hodnoty Ludolfova čísla

Asi nás nejdříve napadne uchovávat v paměti poslední dvě aproximace, abychom porovnáním jejich rozdílu s požadovanou přesností 0,00001 zjistili, máme-li pokračovat výpočtem další aproximace. Pak bude zdrojový text vypadat následovně: #include <stdio.h> #include int main() { double pi1,pi2,a,b,c,q; a=4; b=3; c=-1; pi1=4; pi2=4.0-4.0/3.0; while (fabs(pi1-pi2)> 0.00001) /* funkce fabs vrací absolutní hodnotu racionálního argumentu */ { pi1=pi2; c=-c; b+=2.0;


pi2=pi1+c*a/b; } printf ("vypočtená hodnota pi je %f\n",pi2); system("PAUSE"); }

Pokud se ale zamyslíme, zjistíme, že stačí, budeme-li v paměti uchovávat pouze poslední aproximaci. S požadovanou přesností můžeme srovnávat člen 4/b, o který se liší poslední aproximace od předchozí. Ušetříme použití funkce pro absolutní hodnotu, operaci přiřazení a místo pro dvě proměnné. Program bude navíc jednodušší: /* určení hodnoty Ludolfova čísla */ #include #include <stdio.h> int main() { double pi,b,c; b=1; c=1; pi=4; while (4/b>0.00001) { c=-c; b+=2; pi+=c*4/b; } printf("vypočtená hodnota pi je %fl\n",pi); system("PAUSE"); }

1.3.4 Mzdová výčetka

Dnes, v době bezhotovostních plateb, se tento algoritmus používá méně často, ale význam ještě úplně neztratil. Má-li pokladník za úkol vyplatit řadě lidí nějaké částky v hotovosti, musí do banky pro celkovou sumu a musí mít rozpis, v jakých bankovkách, resp. mincích mu má banka celkovou částku vydat, aby byl schopen všechny částky vyplatit bez problémů s rozměňováním peněz. Předložené řešení, kde zadáváme i platidla, je odolné i vůči případným změnám měny. /* mzdová výčetka */ #include <stdio.h> #include int main() { int i,j,castka,soucet; int platidla[12]={5000,2000,1000,500,200,100,50,20,10,5,2,1}; int pocet[12]; soucet=0; for (i=0;i<12;i++) pocet[i]=0; printf ("Zadejte částky k výplatě(pro konec -1):\n"); do { scanf("%d",&castka); if(castka>0)

Jazyk C 25

{ soucet=soucet+castka; for (i=0;i<12;i++) while (castka>=platidla[i]) { castka=castka-platidla[i]; pocet[i]++; } } } while(castka>=0); printf ("soucet: %d\n",soucet); for (i=0;i<12;i++) printf("%d %d\n",platidla[i],pocet[i]); system("PAUSE"); return 0; }

1.3.5 Největší společný dělitel dvou čísel

Zde použijeme Euklidův algoritmus: od většího z dvojice čísel odečítáme menší tak dlouho, dokud menší není rovno nule. Větší je pak největším společným dělitelem původně zadaných čísel: int nsd(int a,int b) { if((a<=0) || (b<=0)) return 0; while(a>0) { if (a>b) a-=b; else b-=a; if(b==0)return a; } return 0; }

Užitečnost funkcí si uvědomíme, když si uložíme další úkoly: chceme určit nejmenší společný násobek dvou čísel a dále funkci, která upraví zlomek, zadáme-li jí čitatele a jmenovatele. V obou případech se nám hodí funkce pro určení největšího společného dělitele. Oba úkoly přenechám jako cvičení čtenáři.

1.3.6 Pascalův trojúhelník

Máme za úkol zobrazit Pascalův trojúhelník, jehož n-tý řádek představuje koeficienty rozvoje (a+b)n. Aby v takovém případě trojúhelník vypadal jak má, musíme nejprve uvážit rozměr obrazovky, abychom určili, kolik řádků můžeme zobrazit a jaká bude největší hodnota zobrazeného koeficientu, protože z té vyplyne, na kolik míst máme koeficienty zobrazovat. Jednoduché řešení, které nás jistě napadne, vypadá takto: /* pascal.c - zobrazí 12 řádků Pascalova trojúhelníku */ #include <stdio.h> int main()


{ int p1[13]; int p2[13]; /* hodnoty koeficientů ve dvou po sobě jdoucích řádcích */ int i,j; p1[0]=1; p1[1]=1; /* hodnoty prvního řádku */ for(i=1;i<12;i++) { for(j=12;j>=i;j--) printf(" "); for(j=0;j
I zde ovšem po hlubším zamyšlení zjistíme, že hodnoty dalšího řádku mohou být – postupujeme-li odzadu – vypočteny ve stejném řádku a jedno pole je tedy možné ušetřit. Program je zároveň kratší a jednodušší: /* pascal.c - zobrazi 12 řádků Pascalova trojúhelníku */ #include <stdio.h> int main() { int radek[13]; int i,j; radek[0]=1; radek[1]=1; for(i=1;i<12;i++) { for(j=12;j>=i;j--) printf(" "); for(j=0;j<=i;j++) printf("%3d ",radek[j]); printf("\n"); for(j=i;j>0;j--) radek[j]=radek[j]+radek[j-1]; radek[i+1]=1; } system("PAUSE"); return 0; }

1.3.7 Kalendář

Chceme-li vytvořit počítačem kalendář, potřebujeme především funkci, jež pro zadané datum (tedy den, měsíc, rok) určí, o který den týdne se jedná. O to se nyní budeme snažit. Nejprve si zopakujme, co k tomu potřebujeme vědět: od roku 1584 u nás platí gregoriánský kalendář, ve kterém je každý rok dělitelný čtyřmi a nedělitelný stem přestupný. Výjimku představuje rok dělitelný 400, který je přestupný, i když je také dělitelný stem – naposledy to byl rok 2000. Únor má v přestupném roce 29, v nepřestupném 28 dní; duben, červen, září a listopad mají po 30 dnech, ostatní měsíce 31 dní. Spokojíme-li se s tím, že naše funkce bude použitelná od roku 1600 a prozradíme-li, že 26. prosince

Jazyk C 27

1599 byla neděle (kdybychom to nevěděli, bude stačit, víme-li, jaký den je dnes), vytvoříme nejprve funkci, která je schopná určit počet dní mezi dvěma daty. Pomocí ní určíme počet dnů mezi datem 26. prosince 1599 a datem, pro nějž určujeme den týdne. Tento počet modulo sedm udává den týdne. Funkce DenRoku vrací pro zadané datum pořadové číslo dne v roce a hodí se nám pro vytvoření funkce PocDni, která vrací počet dnů mezi dvěma daty. /* kalendar.c */ #include <stdio.h> int y,m,d; int DenRoku(int y, int m, int d); long PocDni(int y1,int m1,int d1,int y2, int m2,int d2); int DenTydne(int y,int m, int d); int DenRoku(int y, int m, int d) { int i,k; int p[12]={31,28,31,30,31,30,31,31,30,31,30,31}; k=d; for(i=0;i<m-1;i++) k=k+p[i]; printf("k=%d",k); /* počet dnů;, které mají dohromady měsíce 1 az m-1 plus den */ if(m>2) { if ((y%4==0) && (y%100!=0) || (y%400==0)) k++; } return k; } long PocDni(int y1,int m1,int d1,int y2, int m2,int d2) { long k; k=365*(y2-y1); /* "hrubý" počet dnů */ k=k+DenRoku(y2,m2,d2)-DenRoku(y1,m1,d1); /* zpřesnění pomocí pořadových čísel */ y2--; y1--; k=k+y2/4-y2/100+y2/400-y1/4+y1/100-y1/400; /* zpřesnění s ohledem na přestupné roky */ return k; } int DenTydne(int y,int m, int d) { return PocDni(1599,12,26,y,m,d)%7; } int main() { printf("Zadej rok,mesic,den\n"); scanf("%d%d%d",&y,&m,&d); switch (DenTydne(y,m,d)) { case 0: {printf("nedele\n"); break;} case 1:


{printf("pondeli\n"); break;} case 2: {printf("utery\n"); break;} case 3: {printf("streda\n"); break;} case 4: {printf("ctvrtek\n"); break;} case 5: {printf("patek\n"); break;} case 6: {printf("sobota\n");} } system ("PAUSE"); }

Pro praktické použití našich funkcí bychom ale měli ještě zajistit, že zadané parametry pro rok, měsíc a den opravdu představují správné datum. Mohli bychom třeba vytvořit funkci, která to ověří. Smysl by také měly některé další funkce, například pro dané datum a daný počet dnů určit datum, jež bude po uplynutí těchto dnů (resp. bylo před ním). Kalendářní funkce jsou velmi důležité v informačních systémech pojišťoven, bank, ale i výrobních podniků. Možná si čtenáři pamatují problémy, které vznikly v roce 2000 a jež měly pouze dvě příčiny: jednak je rok 2000 výjimkou, s jakou se setkáváme jednou za 400 let, za druhé ve starších informačních systémech se šetřilo na nesprávném místě a jako rok se uvádělo pouze poslední dvojčíslí letopočtu. Dnes nic takového není nutné, vždy uvádějte rok čtyřmi číslicemi!

1.4 Permutace Permutací rozumíme změnu uspořádání prvků a můžeme ji zapsat do dvouřádkové notace: 123456 2 4 6 1 5 3

(1)

Zápis znamená, že prvek 2 zaujme místo prvku 1, prvek 4 zaujme místo prvku 2, prvek 6 místo prvku 3… atd. Je zřejmé, že v tomto zápisu můžeme libovolně měnit pořadí sloupců, aniž by se změnil význam. Můžeme také použít cyklickou notaci, v níž lze permutaci (1) zapsat jako: (1 2 4) (3 6)

(2)

Opět to znamená, že z 1 se stane 2, z 2 bude 4, ze 4 bude 1. Z 3 se stane 6 a z 6 bude 3. Číslo 5 zůstane na místě, což můžeme, ale nemusíme zapsat. Stejný význam jako (2) ale mají i zápisy (3 6)(1 2 4), (6 3)(2 4 1) a řada dalších. Někdy proto může být vhodné použít kanonickou formu cyklické notace, která jednoznačná je. Dostaneme ji následujícím způsobem: zz zapíšeme explicitně všechny jednoprvkové cykly, zz v každém cyklu bude na prvním místě nejmenší prvek, zz cykly seřadíme v klesajícím pořadí jejich prvních prvků.

1.4.1 Násobení permutací

Násobení permutací není komutativní. Cykly však můžeme zaměnit, tedy místo (1 2 4)(3 6) lze napsat (3 6)(1 2 4), jsou-li množiny prvků v cyklech disjunktní. Vynásobíme-li permutaci (1 2 4) (3 6) permutací (1 3 6)(4 5), dostaneme (1 2 5 4 3). Součin (1 2 4)(3 6)(1 3 6)(4 5) určujeme následovně: zz 1 přejde na 2, zz 2 přejde na 4, 4 na 5,

Jazyk C 29

zz 3 přejde na 6, 6 na 1, zz 4 přejde na 1, 1 na 3, zz 5 přejde na 4, zz 6 přejde na 3, 3 na 6, tedy 6 zůstane na místě, a konečný výsledek je tedy (1 2 5 4 3). Pro tento postup můžeme napsat program – zde je: /* nasob_permut1.c */ /* násobení permutací */ /* neprovádí se kontrola vstupu */ #include <stdio.h> #define DELKA 18 /* délka zápisu */ int main() { char *zapis="(124)(36)(136)(45)"; int i,j,k,m,jeste; int q; /* pro mzv */ char znak,current,start; char oznac[DELKA]; char vstup[DELKA]; char vystup[DELKA]; j=DELKA; for(i=0;i<j;i++) { oznac[i]='0'; vstup[i]=zapis[i]; } for(i=0;i<j;i++) { if(vstup[i]=='(') { oznac[i]='1'; znak=vstup[i+1]; } else if(vstup[i]==')') { vstup[i]=znak; oznac[i]='1'; } } /* otevření */ i=0; jeste=1; k=0; while(jeste==1) { while(i<j) { jeste=0; if (oznac[i]=='0') { jeste=1; start=vstup[i]; vystup[k]='('; k++; vystup[k]=vstup[i]; oznac[i]=1; for(q=0;q<=k;q++) printf("%c",vystup[q]); /* mzv */ printf("\n"); /* getch(); */ i++; current=vstup[i]; m=i+1; L: while(m<j)


{ if(vstup[m]==current) { oznac[m]='1'; m++; current=vstup[m]; } m++; } if(current!=start) { k++; vystup[k]=current; m=0; for(q=0;q
Nevýhodou tohoto algoritmu ale je, že zápisem součinu permutací musíme v jeho průběhu projít vícekrát. Algoritmus je navíc složitý a nepřehledný. Existuje ale algoritmus, který vystačí s jediným průchodem. Zobrazuje jej následující tabulka: ( 2 5 1 3 4 6

1 2 5 1 ) 4 6

2 3 5 1 ) 4 6

4 3 2 1 ) 4 6

) 3 2 1 5 4 6

( 3 2 1 5 4 6

3 3 2 1 5 4 )

6 3 2 6 5 4 )

) 3 2 6 5 4 1

( 3 2 6 5 4 1

1 3 2 6 5 4 )

3 1 2 6 5 4 )

6 1 2 3 5 4 )

) 1 2 3 5 4 6

( 1 2 3 5 4 6

4 1 2 3 5 ) 6

5 1 2 3 4 ) 6

) 1 2 3 4 5 6

Sloupec pod každým znakem cyklické notace uvádí, jakou permutaci představují částečné cykly vpravo od něj; například sloupec pod číslicí 6 nejvíce vpravo vyjadřuje permutaci: 1 2 3 4 5 6 1 2 3 5 4 ?

Tabulku je možné vytvořit tak, že začneme s identickou permutací vpravo a budeme postupovat zprava doleva. Sloupec pod číslicí x se liší od sloupce vpravo jen v řádku x. Nová hodnota v řádku x je ta, která v předchozí změně zmizela. Program je na první pohled jednodušší: když v něm odstraníme komentář ukrývající tisk mezivýsledků, zobrazí se výše uvedená tabulka.

Jazyk C 31

/* nasob_permut2.c */ /* násobení permutací */ /* neprovádí se kontrola vstupu */ #include <stdio.h> #define ZAPIS 17 #define PRVKU 7 int main() { char *vstup="(124)(36)(136)(45)"; int pom,z,i,j,k; int t[PRVKU]; for(k=1;k=0;k--) { if (vstup[k]==')') z=0; else if (vstup[k]=='(') t[j]=z; else { pom=z; z=t[vstup[k]-48]; t[vstup[k]-48]=pom; if (pom==0) j=vstup[k]-48; } /* printf("%2d ",k); for(i=1;i
1.4.3 Inverzní permutace

Inverzní permutace P–1 k permutaci P je takové uspořádání, které vrací zpět účinky P. Součin P . P–1 je roven identické permutaci. V [Kn08] můžeme najít dva algoritmy pro nalezení inverzní permutace k permutaci zadané dvouřádkovou notací. Zde upřednostníme úlohu praktičtější: mějme dvě pole, z nichž jedno obsahovalo klíče tvořené očíslováním přirozenými čísly, druhé nějaká data. Podle těchto dat jsme obě pole setřídili a nyní bychom rádi obnovili původní stav. To samozřejmě můžeme provést novým setříděním podle klíčů, ale vzhledem k tomu, že klíče tvoří řada přirozených čísel, je to možné provést jednodušeji a v kratším čase. Jde vlastně rovněž o inverzní permutaci, jen jinak zadanou:


/* poradi.c (inverzní permutace) */ #define DIM 7 #include <stdio.h> int klice[DIM]={3,5,7,1,4,2,6}; int data[DIM]={2,4,7,8,10,11,13}; void vymen(int *x,int*y) { int pom; pom=*x; *x=*y; *y=pom; } int main() { int i; for (i=0; i

Jazyk C 33

2.

Rekurze

Funkce je rekurzivní, jestliže obsahuje volání sebe sama (v tomto případě je to přímá rekurze). Jestliže funkce p volá funkci q, a v té je obsaženo volání funkce p, jde o nepřímou rekurzi. Rekurze se vyskytuje často v matematických definicích; příkladem může být definice faktoriálu: 1. 0! = 1; 2. je-li n > 0, je n! = n . (n – 1)! Všude tam, kde je už samotný objekt definován rekurzivně, je pro práci s ním vhodná rekurze. U rekurze je nutné dbát na to, aby algoritmus byl konečný, v rekurzivní funkci musí existovat větev, která rekurzivní volání neobsahuje, a musí být jisté, že nastane stav, kdy se do této větve dostaneme.

2.1 Hanojské věže Klasickou úlohou pro použití rekurze je hlavolam zvaný „Hanojské věže“. Je tvořen třemi tyčemi, na jedné z nich je navlečeno n kotoučů různých průměrů tak, že hořejší kotouč má vždy menší průměr než kotouč pod ním. Úkolem je přesunout celou věž kotoučů na třetí tyč (s využitím druhé jako pomocné), abychom vždy přemisťovali jeden kotouč a nikdy ho neumístili na kotouč s průměrem menším. I když jde o hlavolam, je pomocí rekurze snadno řešitelný. Pro n = 1 je řešení nasnadě, prostě kotouč přemístíme. Pro n > 1 použijeme rekurzi. Označíme-li tyče A, B, C a úkolem je přemístění věže z A na C, je postup následující: 1. Přenes věž o n – 1 kotoučích z tyče A na tyč B s využitím tyče C jako pomocné. 2. Přenes nejspodnější kotouč z tyče A na tyč C. 3. Přenes věž o n – 1 kotoučích z tyče B na tyč C s využitím tyče A jako pomocné.

A

B

C

Obrázek 2.1: Hanojské věže pro n = 4

Nyní by měl být zápis algoritmu srozumitelný, až na smysl proměnné counter. Ta slouží ke zjištění hloubky rekurze, tedy počtu rekurzivních volání. Musí být deklarována s atributem static. Statické proměnné nejsou umístěny v zásobníku, ale v datové oblasti programu, a toto místo je společné všem vnořeným rekurzím funkce. Proměnná nemusí být inicializována, statické proměnné inicializuje nulou překladač. #include <stdio.h> int PVez(int vyska,int odkud,int kam,int pomoci)

Rekurze 35

{ static int counter; counter++; if (vyska > 0) { PVez((vyska-1),odkud,pomoci,kam); printf("prenes kotouc z %i na %i\n", odkud,kam); PVez((vyska-1),pomoci,kam,odkud); } return counter; } int main() { int n; int cnt; printf ("Zadej pocet kotoucu: \n"); scanf("%i",&n); cnt=PVez(n,1,2,3); printf ("Pocet volani: %i\n",cnt); system("PAUSE"); return 0; }

2.2 W-křivky Tuto podkapitolu můžete klidně přeskočit, nebude to mít vliv na studium dalšího textu. Vynechání lze dokonce doporučit, pokud nemáte k dispozici knihovnu graphics.h a nemůžete tedy sami experimentovat. Ve Wirthově knize [Wir89] jsou popsány algoritmy pro zobrazení Hilbertovy křivky a Sierpińského křivky. Zde si popíšeme algoritmus pro zobrazení W-křivky, který je tam uveden jako cvičení. Budou nám stačit dvě funkce pro práci s grafikou: moveto(x,y) nastaví počáteční bod se souřadnicemi (x,y) a funkce linerel(a,b) nakreslí úsečku vedoucí z aktuálního bodu (x,y) do bodu (x+a,y+b). Více vědět nemusíme, příkazy na začátku hlavního programu jsou ve všech programech používajících grafiku stejné.

Obrázek 2.2: Rekurzivní schéma W-křivky

Na obrázku 2.2 vidíme W-křivku 4. řádu, na obrázcích 2.4, 2.5 a 2.6 W-křivky 1., 2. a 3.řádu. Křivka je uzavřená, tedy základní rekurzivní schéma bude vyjádřeno křivkou otevřenou a čtyři části budou spojeny čarami, které nejsou součástí rekurzivního obrazce (na dalších obrázcích jsou znázorněny plnější čarou). Označíme-li čtyři základní obrazce symboly A, B, C, D (jsou identické, až na pootočení o 90°), bude základní rekurzivní schéma W-křivky vypadat jako na obrázku 2.3.


Obrázek 2.3: W-křivka 4. řádu




Jednotlivé obrazce jsou vykreslovány stejně pojmenovanými funkcemi s nepřímou rekurzí. Proto jsou na začátku uvedeny jejich deklarace, specifikující pouze hlavičku funkce, tedy jméno funkce, typ návratové hodnoty a parametr, jímž je řád křivky. #include #include <stdio.h> int h; void b(int i); void c(int i); void d(int i); void a(int i) { if (i>1) { a(i-1); linerel(h,0); linerel(0,h); d(i-1); linerel(0,h); b(i-1); linerel(0,h); linerel(-h,0); a(i-1); } else linerel(0,h); } void b(int i)

Rekurze 37

{ if (i>1) { b(i-1); linerel(0,h); linerel(-h,0); a(i-1); linerel(-h,0); c(i-1); linerel(-h,0); linerel(0,-h); b(i-1); } else linerel(-h,0); } void c(int i) { if (i>1) { c(i-1); linerel(-h,0); linerel(0,-h); b(i-1); linerel(0,-h); d(i-1); linerel(0,-h); linerel(h,0); c(i-1); } else linerel(0,-h); } void d(int i) { if (i>1) { d(i-1); linerel(0,-h); linerel(h,0); c(i-1); linerel(h,0); a(i-1); linerel(h,0); linerel(0,h); d(i-1); } else linerel(h,0); } int main(void) { /* request auto detection */ int gdriver = DETECT, gmode, errorcode; /* inicializace grafických a lokálních proměnných */ initgraph(&gdriver, &gmode, "d:\\install\\bc\\bgi"); /* čtení výsledku inicializace*/ errorcode = graphresult(); /* vyskytla se chyba */ if (errorcode != grOk) { printf("Graphics error: %s\n", grapherrormsg(errorcode)); system("PAUSE"); exit(1); } setcolor(getmaxcolor());


/* kreslení W-krivky */ int n=6; int h0=640; int i,x0,y0; int rad;

printf("Zadej rad krivky (1-6):\n"); scanf("%i",&rad); i=0; h=h0/4; x0=2*h; y0=2*h; do { i=i+1; x0=x0-h; h=h/2; y0=y0+h; if (i==rad) { moveto(x0+160,y0-160); d(i); linerel(0,-h); linerel(h,0); c(i); linerel(-h,0); linerel(0,-h); b(i); linerel(0,h); linerel(-h,0); a(i); linerel(h,0); linerel(0,h); } } while(i
2.3 Fibonacciho čísla Rekurze je nástrojem velmi užitečným, v některých případech může však její použití vést k neefektivním algoritmům. Klasickým příkladem je úloha nalézt n-té Fibonacciho číslo. Fibonacciho čísla se definují takto: zz Fib(0) = 0; zz Fib(1) = 1; zz Pro n > 1 Fib(n) = Fib(n – 1) + Fib(n – 2). Protože definice je rekurzivní, zdá se použití rekurze samozřejmostí. Rekurzivní funkce vypadá následovně: longint fibo(int n); { if((n==0) || (n==1)) return n; else return(fibo(n-1)+fibo(n-2)); }

Bude-li ale např. n = 7, musí se spočítat fibo(5) a fibo(6), pro určení hodnoty fibo(5) se musí určit fibo(4) a fibo(3), pro určení hodnoty fibo(6) se bude znovu počítat fibo(5) a fibo(4) – atd. Nemusíme už pokračovat, abychom viděli, kolik zbytečných výpočtů navíc se bude provádět. Mnohem efektivnější bude tedy algoritmus, který počítá všechna Fibonacciho čísla od začátku a průběžně uchovává poslední dvě vypočtené hodnoty (f1 a f2):

Rekurze 39

int function fibon(int n); { int f1,f2,nove,i; f1=0; f2=1; if (n<=1) return n; else { i=2; while (i
Počet průchodů cyklem odpovídá zadanému n, algoritmus v iterační podobě je daleko efektivnější než byla jeho rekurzivní verze.

2.4 Odstranění rekurze V podkapitole 2.3. jsme ukázali, že použití rekurze může vést k neefektivnímu programu. Může také (při větší hloubce rekurze) vést k přeplnění zásobníku. Ve [Vi08] je popsán formální postup odstranění rekurze takto: Máme např. funkci se třemi parametry x, y, z a třemi proměnnými a, b, c předávanými hodnotou. Rekurzivní volání nahradíme skokem na začátek těla funkce. Musíme se postarat o to, aby se zachovaly hodnoty lokálních proměnných a formálních parametrů v okamžiku volání, neboť tyto hodnoty budeme po návratu potřebovat. 1. Na začátku deklarujeme zásobník jako objekt sdílený všemi voláními. Bude sloužit k ukládání parametrů, lokálních proměnných a návratových adres. 2. Před 1. příkaz funkce dáme návěští L0. 3. U i-tého rekurzivního volání, kde i = 1, … k, provedeme následující kroky: ■■ Uložíme do zásobníku hodnoty lokálních proměnných a, b, c a hodnoty formálních parametrů x, y, z. ■■ Vytvoříme návěští Li a hodnotu i uložíme do zásobníku. Později bude použita ke stanovení místa návratu. ■■ Vyhodnotíme skutečné parametry nového volání a přiřadíme je formálním parametrům. ■■ Odstraníme toto rekurzivní volání a na jeho místo vložíme nepodmíněný skok na začátek funkce, tedy na L0. 4. K prvnímu příkazu bezprostředně za skokem vloženým v předchozím kroku přidáme návěští Li. 5. Na konci funkce: je-li zásobník prázdný, skončíme. Jinak vyjmeme ze zásobníku hodnotu i určující, kam se máme vrátit. 6. Vyjmeme ze zásobníku hodnoty formálních parametrů a uložíme je do x, y, z. 7. Vyjmeme ze zásobníku hodnoty lokálních proměnných a, b, c a vložíme nepodmíněný skok na návěští Li. O parametry předané odkazem se nemusíme starat. Předání výsledku funkce zařídíme buď použitím globální proměnné, nebo zásobníku. Konečný výsledek můžeme upravit (ale nemusíme, jak jsme vysvětlili dříve, příkazy goto můžeme ponechat). Použijeme-li popsaný postup na program pro hanojské věže, dostaneme:


Algoritmy v jazyku

Recommend Documents