Základy algoritmizace a programování
1
Základy algoritmizace a programování
1.1
Algoritmus
Algoritmus je posloupnost operací, která řeší daný úkol v konečném počtu kroků. Je to přesný postup, který je potřeba k vykonání určité činnosti. Jinak řečeno - algoritmus je jednoznačný a přesný popis řešení problému. Každý algoritmus musí mít tyto vlastnosti: Rezultativnost (konečnost) – algoritmus musí mít začátek a konec.Musí proběhnout v konečném počtu kroků Determinovanost (předurčenost) – algoritmus musí být jednoznačný. Všechny operace i jejich návaznosti musí být jednoznačně určeny (definovány) a nic nesmí být náhodné. Činnost algoritmu nesmí záviset na libovůli osoby ani na vlastnostech zařízení, které ho realizují. Obecnost (hromadnost) – algoritmus musí řešit úlohu pro různé vstupní hodnoty. Opakovatelnost – při stejných vstupních hodnotách musíme dostat vždy stejný výsledek. Správnost – algoritmus musí být věcně správný. Srozumitelnost – algoritmus musí být srozumitelný i pro uživatele, který daný algoritmus nevytvářel.
Možnosti zápisu algoritmů
1.1.1
Slovní vyjádření Používá se pro skupinu lidí, která nemá programátorské vzdělání návody k obsluze, recepty, postup práce. Výhodou je, že se lze domluvit i s laikem. Nevýhodou je malá přehlednost a absence nástrojů k dodržení vlastností algoritmu. Příklad:
Algoritmus přípravy polévky ze sáčku Formulace problému: Uvař polévku ze sáčku. Analýza úlohy Vstupní údaje: polévka, voda, hrnec, lžíce, vařič Výstupní údaje: uvařená polévka Analýza: Polévku nesmíme převařit ani vyvařit
Sestavení algoritmu Slovní popis: - vyber požadovanou polévku - do hrnce napusť studenou vodu - rozmíchej polévku ve studené vodě lžící - zapni vařič - vař polévku 10 minut - Vypni vařič
393
Základy algoritmizace a programování Matematické vyjádření Používá se tam, kde je možné daný problém popsat matematickým vyjádřením. Výhodou je, že jednoznačný. Nevýhodou může být, že při neošetření vstupních podmínek nemusí být věcně správný Vývojový diagram Je to symbolický, algoritmický jazyk, který se používá pro názorné zobrazení algoritmu. Je to jednoznačný komunikační prostředek při týmové práci, je přehledný a má nástroje k dodržení algoritmu. Výborně se hodí k dokumentačním účelům, kde je přehlednější než výpis programu. Nevýhodou může být, že mu laik nemusí rozumět. Rozhodovací tabulka Tento zápis se používá v případě, kdy se v dané úloze vyskytuje několik možností a vlastní řešení je pro každou možnost jednoznačně popsatelné (rozvrh, tabulka logického součinu..) Výhodou jednoznačný a přehledný zápis. Je výhodný zejména při větším počtu možností řešení. Bývá srozumitelný i laikům. Nevýhodou může být u velkých tabulek ztráta přehlednosti a nemusí se hodit pro každý typ úlohy. Počítačový program Používá se pro zápis instrukcí z vytvořeného algoritmu, kterému počítač rozumí a umí z něho vytvořit strojový kód. Výhodou je forma zápisu, které rozumí člověk i počítač (pokud je vybaven příslušným překladačem). Nevýhodou je, že zápisu rozumí pouze programátor, který umí daný programovací jazyk. Výpis počítačového programu může být málo názorný a nepřehledný. Objektová analýza Tato metoda se používá v objektově orientovaném programování. Výhodou je forma zápisu, které rozumí člověk i počítač (pokud je vybaven příslušným překladačem). Nevýhodou je, že zápisu rozumí pouze programátor, který umí daný programovací jazyk. Výpis počítačového programu může být málo názorný a nepřehledný.
1.2
Algoritmizace
Algoritmizace je postup při tvorbě programu pro počítač, kterým lze prostřednictvím algoritmu řešit nějaký problém. Algoritmizaci lze rozdělit do několika částí - formulace problému - analýza úlohy - vytvoření algoritmu - sestavení programu - odladění programu
394
Základy algoritmizace a programování Formulace problému V této části je třeba přesně formulovat požadavky, určit výchozí hodnoty, požadované výsledky, jejich formu a přesnost řešení. Analýza úlohy Při analýze úlohy si ověříme, zda je úloha řešitelná a uděláme si první představu o jejím řešení. Dále zjistíme, zda výchozí hodnoty jsou k řešení postačující a zda má úloha více řešení. Podle charakteru úlohy vybereme nejvhodnější řešení. Vytvoření algoritmu úlohy Provádí se při tvorbě jakéhokoliv programu. Sestavíme jednoznačný sled jednotlivých operací, které je třeba provést, aby byla úloha správně vyřešena. Algoritmus přesně popisuje postup zpracování daného úkolu, nedává však odpověď na daný problém, ale pouze postup, jak ji získat. Sestavení programu Na základě algoritmu řešené úlohy sestavíme program (zdrojový text) v konkrétním programovacím jazyce. Ze zdrojového textu se pomocí překladače do strojového kódu vytvoří spustitelný program. Dá se tedy říci, že dobře provedená analýza úlohy a algoritmizace daného problému je základním předpokladem sestavení programu pro počítač. Odladění programu Cílem odladění je odstranění chyb z programu. Chyby se nejčastěji projeví nesprávnou činností programu nebo špatnými výsledky. Chyby v programech mohou být syntaktické nebo logické. Syntaktické - špatně zapsaný nějaký příkaz. Překlad programu se zastaví a zobrazí se hlášení o chybě. Tyto chyby jsou snadno opravitelné. Logické - program je funkční, ale nedělá co má. Může skončit v nekonečném cyklu. Pro ladění se vždy používá několik kontrolních příkladů. Při odstraňování těchto chyb může pomoci ladící program (debugger) umožňující sledování aktuálního stavu proměnných a krokování. Teprve po odstranění všech druhů chyb můžeme program použít k praktickému řešení úloh. Tyto chyby se velmi špatně identifikují. Důležité pojmy v rámci algoritmizace a programování Proměnná - je to místo v paměti počítače, ve kterém se nachází určitá hodnota Identifikátor - je název proměnné Datový typ - je to určitý typ proměnné char - znak integer - celé číslo real - reálné číslo boolean - logická proměnná Deklarace – stanovení proměnných jakého jsou typu. Provádí se vždy na začátku programu. Syntaxe – přesné určení, jak se mají jednotlivé příkazy a části programu zapisovat Strojový kód – je to programový kód, který jediný dokáže počítač přímo zpracovávat.
395
Základy algoritmizace a programování
1.3
Rozdělení programovacích jazyků
Strojově orientované - strojový jazyk (jazyk fyzického procesoru) - asembler (jazyk symbolických adres) Vyšší programovací jazyk – je to programovací jazyk, jehož příkazy jsou tvořeny pomocí klíčových slov, jejichž význam musí být převeden do strojového kódu, aby mohl program napsaný ve vyšším programovacím jazyce být spuštěn. - obecné - (C, C++, C#, Objekt Pascal, Visual Basic, .NET Framework, Java) - databázové (MS Fox Pro, Oracle) - pro webové klienty (Java, JavaScript, ActiveX) - specializované (makrojazyky, simulační jazyky) Aby mohl procesor napsaný program zpracovat musí být před zpracování přeložen do strojového kódu. To zajistí tzv. překladače. Rozeznáváme dva druhy těchto překladačů. - Překladač neboli kompilátor je program, který ze zdrojového kódu vytvoří spustitelný soubor. Vytvoří instrukce pro procesor. - Iterpreter načítá program v textovém zápisu a okamžitě jednotlivé příkazy vykonává. Program tedy není předem přeložený. Používá se například u skriptů ve webových stránkách Strukturované programování Je to soubor doporučení, jak by měl dobře napsaný program vypadat. Tato doporučení vytvářejí jakési „mantinely“ pro programátory. Strukturované programování je založeno na dvou principech. - Složitou úlohu rozdělíme na dílčí úkoly, které řešíme samostatně a metodou shora dolů propojíme úlohu v jeden celek. - Při návrhu řešení dílčích úloh použijeme pouze povolené řídící struktury - sekvence - větvení - cykly - přepínače Objektové programování Je to soubor doporučení, jak by měl dobře napsaný program vypadat. Přínosem objektového programování je také větší strukturovanost a modularita vytvářeného programu. Objektově orientovaný přístup tvorby programu je charakterizován třemi základními vlastnostmi. Obalení (zapouzdření) - je realizováno novým datovým typem – objekt. Obsahuje kromě datových položek také řídící struktury – metody. Oním obalením tedy můžete rozumět obalení datových položek řídícími strukturami – metodami, které zajišťují přístup k datovým položkám. 396
Základy algoritmizace a programování Dědičnost – inheritance - umožňuje vytvářet nové objekty jako potomky již existujících objektů – předků, přebírat od nich datové položky a metody a modifikovat je či upřesňovat. Polymorfismus (mnohotvarost) - polymorfismus je vlastnost objektové programování, která umožňuje pojmenovat metodu jedním jménem a tato metoda může být společná pro různé objekty ve stromové hierarchii, i když pro každý objekt v této hierarchii se bude chovat různě. Při objektovém přístupu k tvorbě programu nezkoumáme způsob funkce programu, ale způsob změn dat. Objektový program je řízem tokem událostí. Vizuální programování Vizuální programování je dnes většinou objektové a současně strukturované. Spočívá v tom, že velké množství standardně používaných objektů (tlačítka, políčka, práci se soubory) je již připraveno a jen je myší přetahujeme do vytvářeného programu. Vývojové prostředí Je to komplexní nástroj na tvorbu programů. Obsahuje: - překladač pro určený programovací jazyk - nástroje na vizuální tvorbu programu - hotové komponenty programů - nástroje pro ladění a odstraňování chyb
1.4
Vývojový diagram
Vývojový diagram je grafické vyjádření požadovaného algoritmu (znázornění jednotlivých příkazů, ze kterých se algoritmus skládá). Pro vývojový diagram se používají stanovené značky, které nelze měnit. Spojnice - orientované - neorientované
397
Základy algoritmizace a programování Mezní značky
ZAČÁTEK
KONEC
RETURN
Ruční zadání vstupních dat
A
R=
Zpracování VÝPOČET
C=A+B
Výstup TISK
Vstup ČTI: A, B
Spojka 3
Podmínka (rozhodování) ANO A>20
NE
Přepínání 1
12 k=
30
398
k=
Základy algoritmizace a programování Cyklus I= 2,8,15
tělo
Konec I
I= 2,8,15
tělo
Konec I
Podprogram 6200
1.4.1
Chyby v algoritmech
Při psaní programů musíte dbát na správný zápis matematických vzorců. V programech nelze použít zlomkové čáry. Místo zlomkové čáry se používá lomítko /. Rovnici musíme zapsat takto: X:=(A+B)/(C+D) V programech nelze dále použít √ (odmocninu) a . (násobení). Místo znaku √ používáme výraz SQRT a místo znaku . používáme znak *. Místo znaku používáme výraz PI.
Špatný algoritmus, protože byla porušena podmínka rezultativnosti - konečnosti - algoritmus musí proběhnout v konečném počtu kroků. Písnička se bude zpívat pořád dokola a nikdy neskončí. Došlo k zacyklení programu.
399
Základy algoritmizace a programování
Správné řešení
Špatný algoritmus, protože byla porušena podmínka rezultativnosti - konečnosti - algoritmus musí proběhnout v konečném počtu kroků. Co když hned ze začátku je I větší než 10? Došlo k zacyklení programu.
Správné řešení
400
Základy algoritmizace a programování
Špatný algoritmus, protože byla porušena podmínka věcné správnosti. Algoritmus je funkční, ale dostanete nesprávný výsledek
Špatný algoritmus, protože byla porušena podmínka jednoznačnosti – (determinovanost podmíněnost) - všechny operace i jejich návaznosti musí být jednoznačně určeny (definovány) a nic nesmí být náhodné.
Správné řešení
401
Základy algoritmizace a programování
Špatný algoritmus, protože byla porušena podmínka jednoznačnosti – (determinovanost podmíněnost) - všechny operace i jejich návaznosti musí být jednoznačně určeny (definovány) a nic nesmí být náhodné. Co když ve jmenovateli bude 0? Musíme ošetřit hodnoty, které se blíží k nekonečnu. Pokud je řešení v oboru reálných čísel, nesmí být výraz pod odmocninou záporný Jsou to nejzávažnější chyby v programech.
Správné řešení
Špatný algoritmus, protože byla porušena podmínka obecnosti – (hromadnosti) - algoritmus musí řešit úlohu pro různé vstupní hodnoty.
402
Základy algoritmizace a programování
Správné řešení
Špatný algoritmus, protože byla porušena podmínka opakovatelnosti - při stejných vstupních hodnotách musíme dostat vždy stejný výsledek. Proměnná I je neznámá.
Správné řešení
403
Základy algoritmizace a programování
Ukázky algoritmů
1.4.2
Sekvence Sekvence je nejjednodušším typem algoritmu, který se skládá (kromě mezních značek) pouze ze sekvenčních bloků. Během sekvence nesmí docházet k větvení algoritmu ani k návratu zpět.
Větvení Nejčastějším důvodem větvení je ošetření nežádoucích důsledků. Musí být ošetřeny všechny možnosti, které mohou nastat. Situace se musí nejdříve vyhodnotit. Teprve poté se provede činnost. - dělení - výpočet výrazů s odmocninou - další funkce (goniometrické)
404
Základy algoritmizace a programování
Cykly Cykly jsou jedním z nejsilnějších nástrojů algoritmů. Podstatou je opakování určité části algoritmu. Cyklus musí být konečný. - cykly s pevným počtem opakování - cykly řízené podmínkou s podmínkou na začátku cyklu - cykly řízené podmínkou s podmínkou na konci cyklu Cyklus s pevným počtem opakování
Cyklus řízený podmínkou - podmínka je na začátku
Cyklus řízený podmínkou - podmínka je na konci
405
Základy algoritmizace a programování
Čekací smyčka
Příklady 1. 2. 3.
Je dán obdélník o stranách A, B. Vytvořte algoritmus pro výpočet obvodu (O) a obsahu (S) tohoto obdélníka. Je dána kružnice o poloměru R. Vytvořte algoritmus pro výpočet obvodu (O) této kružnice a výpočet obsahu (S) kruhu, který leží uvnitř této kružnice. Je dán rovnostranný trojúhelník o stranách A. Vytvořte algoritmus pro výpočet obvodu (O) a obsahu (S) tohoto trojúhelníka.
4. 5.
Je dán pravoúhlý trojúhelník o stranách A, B, C. Vypočítejte stranu C. Vytvořte algoritmus pro výpočet výrazu tak, aby se výpočet alespoň jednou uskutečnil.
6. 7.
Vytvořte algoritmus pro výpočet výrazu Vytvořte algoritmus pro výpočet výrazu
8. 9. 10. 11. 12.
Vytvořte algoritmus pro zjištění zda zadané číslo je kladné, či záporné. Vytvořte algoritmus pro porovnávání a řazení dvou čísel od největšího do nejmenšího. Vytvořte algoritmus pro nalezení největšího ze tří zadaných čísel. Vytvořte algoritmus pro určení, zda tři čísla A, B, C mohou tvořit strany trojúhelníka. Vytvořte algoritmus pro řešení lineární rovnice - A*X + B =0 - proměnné A, B jsou načítány zvenčí - X – hledaný kořen rovnice Vytvořte algoritmus pro vytvoření kalkulačky, která bude pracovat se dvěma čísly. Požadované matematické operace - sčítání, odečítání, násobení, dělení Vytvořte algoritmus pro výpočet veličin rychlost, dráha a čas pohybu rovnoměrného přímočarého. Vytvořte algoritmus pro výpočet výsledného odporu R, který se skládá ze dvou paralelních odporů R1 a R2. Algoritmus bude fungovat tak, že budete moci postupně zadávat různé hodnoty odporů R1 a R2 pro výpočet výsledného odporu R.
13. 14. 15.
16. 17. 18. 406
Vytvořte algoritmus pro zobrazení čísel od jedničky do desítky. Vytvořte algoritmus pro sečtení čísel od jedničky do desítky. Vytvořte algoritmus pro výpočet faktoriálu zadaného čísla.
Základy algoritmizace a programování
407
