Algoritmizace Ing. Jana Pšenčíková
Nakladatelství a vydavatelství
Vzdìlávání, které baví www.c o mp u t e r m e d i a . c z
R
Obsah Obsah ALGORITMUS .............................................................................................................................. 7 CO JE TO ALGORITMUS A PROČ VYTVÁŘÍME ALGORITMY ................................................................................................................ 7 Začátek a konec algoritmu .............................................................................................................................................................................. 7 Věcná správnost ............................................................................................................................................................................................... 9 Jednoznačnost............................................................................................................................................................................................... 10 Obecnost ....................................................................................................................................................................................................... 12 Opakovatelnost .............................................................................................................................................................................................. 12 Srozumitelnost ............................................................................................................................................................................................... 13
MOŽNOSTI ZÁPISU ALGORITMŮ .......................................................................................................................................................... 13 Slovní vyjádření algoritmu .............................................................................................................................................................................. 13 Matematický zápis .......................................................................................................................................................................................... 14 Rozhodovací tabulky ...................................................................................................................................................................................... 14 Vývojové diagramy ......................................................................................................................................................................................... 16 Počítačový program ....................................................................................................................................................................................... 18 Další formy zápisu algoritmů ......................................................................................................................................................................... 18
SEKVENCE ................................................................................................................................ 19 Jednoduchá sekvence s jedním sekvenčním blokem – příkaz výstupu ......................................................................................................... 19 Sekvence se dvěma sekvenčními bloky ......................................................................................................................................................... 19 Součet obsahu dvou buněk, přiřazovací příkaz ............................................................................................................................................. 20 Výměna obsahu dvou buněk .......................................................................................................................................................................... 21 Další typické sekvenční algoritmy .................................................................................................................................................................. 22 Rozdíl a součin .............................................................................................................................................................................................. 22 Obdélník – obvod a plocha ............................................................................................................................................................................ 23 Obvod kružnice a plocha kruhu ..................................................................................................................................................................... 23 Rovnostranný trojúhelník – obvod a plocha ................................................................................................................................................... 23 Objem a plocha válce .................................................................................................................................................................................... 24 Šestiúhelník - obvod a obsah ......................................................................................................................................................................... 24 Výměna hodnot ve dvou buňkách bez pomocné buňky ................................................................................................................................. 25 Pythagorova věta ........................................................................................................................................................................................... 25
VĚTVENÍ .................................................................................................................................... 26 OŠETŘENÍ NEŽÁDOUCÍCH DŮSLEDKŮ ............................................................................................................................................... 26 Křižovatka ...................................................................................................................................................................................................... 26 Podíl ............................................................................................................................................................................................................... 27 Obecnější výraz s dělením ............................................................................................................................................................................. 27 Odmocnina .................................................................................................................................................................................................... 28 Obecný výraz ................................................................................................................................................................................................. 28
VĚTVENÍ Z DŮVODU NĚKOLIKA ŽÁDOUCÍCH MOŽNOSTÍ ................................................................................................................. 29 Nedělní program ............................................................................................................................................................................................ 29
VÝRAZY S ABSOLUTNÍ HODNOTOU, VLASTNOSTI ČÍSEL ................................................................................................................. 29 Absolutní hodnota .......................................................................................................................................................................................... 29 Zjištění, zda je číslo kladné, či záporné ......................................................................................................................................................... 30 Zjištění, zda je číslo sudé, či liché ................................................................................................................................................................. 30 Dělitelnost ...................................................................................................................................................................................................... 31
POROVNÁVÁNÍ A ŘAZENÍ ČÍSEL, MAXIMUM A MINIMUM .................................................................................................................. 32 Porovnání dvou čísel podle velikosti............................................................................................................................................................... 32 Seřazení dvou čísel s pomocnou buňkou ...................................................................................................................................................... 33 Největší ze tří čísel – bez pomocné buňky .................................................................................................................................................... 33 Maximum ze tří čísel s použitím pomocné buňky .......................................................................................................................................... 34 Maximum ze tří čísel s použitím dočasného maxima ..................................................................................................................................... 34 Seřazení tří čísel podle velikosti bez pomocné buňky .................................................................................................................................... 35 Seřazení tří čísel s použitím pomocné buňky ................................................................................................................................................ 36 Seřazení tří čísel podle velikosti s respektováním výsledku předchozího kroku ............................................................................................ 37 Seřazení čtyř čísel podle velikosti – s pomocnou buňkou .............................................................................................................................. 38
ÚLOHY Z GEOMETRIE ............................................................................................................................................................................ 39 Trojúhelník ...................................................................................................................................................................................................... 39 Test na trojúhelník rovnoramenný, rovnostranný, obecný ............................................................................................................................... 40 Test na pravoúhlý trojúhelník .......................................................................................................................................................................... 41
KOMBINOVANÉ ALGORITMY ................................................................................................................................................................. 43 Lineární rovnice .............................................................................................................................................................................................. 43 Soustava dvou lineárních algebraických rovnic ............................................................................................................................................. 43 Kvadratická rovnice s reálnými kořeny ........................................................................................................................................................... 44 Kvadratická rovnice s komplexně sdruženými kořeny .................................................................................................................................... 45 Kalkulačka ...................................................................................................................................................................................................... 47 Rychlost, dráha, čas ....................................................................................................................................................................................... 48 Pohyb rovnoměrně zrychlený ......................................................................................................................................................................... 49 Vlaky .............................................................................................................................................................................................................. 50
CYKLY ....................................................................................................................................... 53 CYKLUS A JEHO TYPY ........................................................................................................................................................................... 53
3
Algoritmizace Cykly s pevným počtem opakování ............................................................................................................................................................... 54 Cyklus řízený podmínkou – podmínka je na začátku cyklu ............................................................................................................................ 55 Cyklus řízený podmínkou – podmínka je na konci cyklu ................................................................................................................................ 56 Čekací smyčka ............................................................................................................................................................................................... 57
ÚLOHY S OPAKOVÁNÍM ......................................................................................................................................................................... 58 Paralelní odpory ............................................................................................................................................................................................. 58 Kalkulačka ...................................................................................................................................................................................................... 59
SUMY, PROHLEDÁVÁNÍ ŘADY ČÍSEL, MAXIMUM A MINIMUM ............................................................................................................ 61 Zobrazení čísel od jedničky do desítky .......................................................................................................................................................... 61 Zobrazení čísel od dvojky do dvacítky, jen sudé ............................................................................................................................................ 61 Suma čísel od 1 do 10 ................................................................................................................................................................................... 62 Suma 10 různých čísel, resp. libovolného počtu čísel .................................................................................................................................... 62 Maximum z deseti kladných čísel ................................................................................................................................................................... 63 Maximum a minimum z celých čísel, jejichž počet bude zadán předem ........................................................................................................ 65 Suma čísel, jejichž počet není předem znám – test uprostřed cyklu ............................................................................................................ 67 Suma čísel, jejichž počet není předem znám – s testem na začátku ............................................................................................................ 67 Suma čísel, jejichž počet není znám předem – s testem na konci cyklu ....................................................................................................... 68 Maximum z neznámého počtu čísel .............................................................................................................................................................. 69 Maximum a minimum z neznámého počtu celých čísel ................................................................................................................................. 70 Zjištění, kolik čísel je kladných a kolik záporných – celkový počet je znám ................................................................................................... 71 Zjištění, kolik čísel je kladných, kolik záporných - přijde-li nula, pak cyklus skončí ........................................................................................ 72 Zjištění, kolikrát se v textu objeví zadané písmeno – text je zadáván po znacích ......................................................................................... 73 Zjištění, kolikrát se v textu objeví zadané písmeno – text je zadán najednou ............................................................................................... 74 Zjištění počtu slov ve větě – znak po znaku ................................................................................................................................................... 75 Zjištění počtu slov ve větě – načte se celá věta najednou ............................................................................................................................. 76 Součin pomocí součtu ................................................................................................................................................................................... 77 Dělení pomocí odečítání ................................................................................................................................................................................ 78 Největší společný dělitel ................................................................................................................................................................................ 79 Součet číslic v čísle ....................................................................................................................................................................................... 80 Test, kolikrát se vyskytuje určitá číslice v daném čísle ................................................................................................................................... 81
ODDECHOVÉ ÚLOHY .............................................................................................................................................................................. 82 Písnička „Když jsem já sloužil“ ....................................................................................................................................................................... 82 Společenská hra „Severní pól“ ...................................................................................................................................................................... 84 Zajíci a bažanti .............................................................................................................................................................................................. 85
ČÍSELNÉ SOUSTAVY A PŘEVODY MEZI NIMI ...................................................................................................................................... 86 Převod z desítkové soustavy do dvojkové – nové cifry se vypisují od nejvyšších ........................................................................................ 88 Převod čísla z dvojkové soustavy do desítkové ............................................................................................................................................. 89
ŘADY – ARITMETICKÉ, GEOMETRICKÉ, DALŠÍ .................................................................................................................................. 90 Aritmetická řada – výpočet hodnoty prvků řady, prvky se zobrazují průběžně .............................................................................................. 90 Aritmetická řada – výpočet hodnoty prvků řady, všechny prvky se zobrazí nakonec ..................................................................................... 91 Aritmetická řada – součet ............................................................................................................................................................................... 92 Geometrická řada – výpočet hodnoty prvků řady, prvky se zobrazují průběžně ............................................................................................ 93 Geometrická řada – výpočet hodnoty prvků řady, všechny prvky se zobrazí nakonec .................................................................................. 94 Geometrická řada – Suma ............................................................................................................................................................................. 95 Složité úrokování ........................................................................................................................................................................................... 96 Stavební spoření ............................................................................................................................................................................................ 98 Faktoriál ....................................................................................................................................................................................................... 100 Algoritmus pro výpočet Ludolfova čísla ................................................................................................................................................... 101 Algoritmus pro výpočet hodnoty přirozeného logaritmu čísla 2 ................................................................................................................... 102 Algoritmus pro výpočet funkce sinus x pomocí mocninné řady ................................................................................................................... 103 Algoritmus pro výpočet funkce ex pomocí mocninné řady ........................................................................................................................... 104
OPERACE S VEKTORY A MATICEMI ................................................................................................................................................... 105 Součet vektorů ............................................................................................................................................................................................. 105 Skalární součin vektorů ................................................................................................................................................................................ 106 Minimum z řady čísel, metoda přímého výběru – řešení pomocí vektoru ................................................................................................... 107 Maximum z řady čísel, metoda probublávání – řešení pomocí vektoru ....................................................................................................... 108 Matice – načtení prvků ................................................................................................................................................................................ 109 Matice – počet kladných a záporných prvků ............................................................................................................................................... 110 Největší a nejmenší prvek matice ................................................................................................................................................................ 111 Pozice největšího a nejmenšího prvku matice ............................................................................................................................................ 112 Trojúhelníková matice .................................................................................................................................................................................. 113 Diagonální matice ........................................................................................................................................................................................ 114 Matice otočená kolem hlavní diagonály ....................................................................................................................................................... 116 Součet matic ................................................................................................................................................................................................ 118 Součin matic ................................................................................................................................................................................................ 119
TŘÍDICÍ ALGORITMY ............................................................................................................................................................................. 121 Select Sort (třídění přímým výběrem) ........................................................................................................................................................... 121 Bubble Sort (třídění probubláváním) - zjednodušený ................................................................................................................................... 123 Bubble Sort (třídění probubláváním) - klasický ............................................................................................................................................ 124 Shake Sort (třídění přetřásáním) .................................................................................................................................................................. 126
4
Algoritmus - proces algoritmizace
Algoritmus CÍL KAPITOLY: UVEDENÍ DO PROBLEMATIKY ALGORITMIZACE Důležité pojmy: •
Algoritmus
•
Vlastnosti správného algoritmu
•
Možnosti zápisu algoritmu
•
Vývojový diagram
•
Začátek a konec algoritmu
•
Sekvence
•
Větvení
•
Cyklus
•
Rozhodovací tabulky
•
Program
•
Překladač
CO JE TO ALGORITMUS A PROČ VYTVÁŘÍME ALGORITMY Každý student v dnešní době už přišel do styku s počítačem a pracoval s počítačovými programy, byť jako uživatel. Tyto programy musel předtím někdo vytvořit – musel počítači přesně říci, co mají dělat. To znamená, že: •
napřed musel vymyslet postup, kterému říkáme algoritmus;
•
pak tento postup musel přepsat do kódu, kterému počítač bude rozumět – přepsat jej do nějakého programovacího jazyka.
Algoritmus je přesný postup, který je potřeba k vykonání určité činnosti. Musí splňovat následující podmínky: •
musí mít začátek a konec – po konečném počtu kroků musí dojít od počátku do konce;
•
musí být věcně správný;
•
musí být jednoznačný - v každém jeho kroku musí být jasné, jaký bude jeho následující krok;
•
musí být obecný;
•
musí být opakovatelný;
•
musí být srozumitelný.
Význam těchto podmínek bude ukázán na příkladech.
Začátek a konec algoritmu Podívejte se nejprve, jak by vypadal špatný algoritmus, ve kterém by byla tato základní podmínka porušena. Možná znáte písničku Pes jitrničku sežral – zapsána do algoritmu by vypadala takto: Vidíte, že se písnička bude zpívat pořád dokola a tento algoritmus nikdy neskončí. Pokud byste podle tohoto algoritmu napsali program, fungoval by tak, že by se po jeho spuštění neustále vypisoval text písničky a program by nebyl k zastavení. Musel by být násilně ukončen, nebo byste museli vypnout počítač (což v obou případech není nejlepší řešení).
docela maličkou
Jak tedy algoritmus upravit? V běžném životě spoléháme na inteligenci člověka (v našem případě zpěváka písničky) – až ho přestane zpívání bavit nebo až všichni posluchači usnou, skončí. Počítač však vlastní inteligenci nemá a dělá pouze to, co mu přikážete. 7
Sekvence - jednodušší vývojové diagramy
Sekvence CÍL KAPITOLY: TVORBA NEJJEDNODUŠŠÍCH TYPŮ VÝVOJOVÝCH DIAGRAMŮ Důležité pojmy a nové dovednosti: •
Sekvence
•
Přiřazovací příkaz
•
Součet obsahu dvou buněk
•
Výměna obsahu dvou buněk
•
Matematické operace, které se mohou vyskytovat v sekvenci
V této kapitole se seznámíte s jedním ze tří základních typů algoritmu, který se nazývá sekvence. Sekvence je nejjednodušším typem algoritmu, který se skládá (kromě mezních značek) pouze ze sekvenčních bloků. Pamatujte: Během sekvence nesmí docházet k větvení algoritmu ani k návratu zpět (k cyklu).
Sekvence jsou jedním ze základních stavebních kamenů algoritmů. Existuje sice málo postupů, ve kterých byste vystačili pouze se sekvencí, ale právě sekvence jsou součástí všech algoritmů, tedy i těch nejsložitějších.
Jednoduchá sekvence s jedním sekvenčním blokem – příkaz výstupu Pro začátek nejprve to nejjednodušší - prvním příkladem bude algoritmus programu, který zobrazí na displeji větu: „Jsi chytrý a krásný.“ Vývojový diagram je na obrázku vlevo dole.
Sekvence se dvěma sekvenčními bloky Abychom si o sobě tolik nemysleli, hned to napravíme. Algoritmus bude upraven tak, že napřed sice zobrazí větu „Jsi chytrý a krásný“, ale pak doplní „ale ne zas tak moc.“ Vývojový diagram je tentokrát na obrázku vpravo dole. Sekvence s jedním sekvenčním blokem - příkaz výstupu
Sekvence se dvěma sekvenčními bloky
19
Algoritmizace Součet obsahu dvou buněk, přiřazovací příkaz V předchozích úlohách byly prováděny operace s buňkami tak, že se s operátorem := (přiřazeno) pracovalo stejným způsobem jako s operátorem = (rovná se), který znáte z matematiky. Mezi oběma operátory je však rozdíl. Operátor := (přiřazeno) umožňuje to co rovnítko, ale ještě také něco navíc. Rozdíl si ukážeme na vztahu součtu C:=A+B. K této operaci jsou zapotřebí celkem tři buňky - A, B, C. Můžete si představit, že máte sklenici A (například se třemi díly vody) a sklenici B (se dvěma díly vody). Obsah obou sklenic nalijete do sklenice C, která nakonec bude obsahovat pět dílů vody (v tomto případě je to stejné, jako kdybyste použili rovnítko). Vývojový diagram
Sklenice A se třemi díly vody
Sklenice B se dvěma díly vody
Sklenice C s pěti díly vody
Celou operaci by ale bylo možné provést i tak, že byste jednu sklenici (buňku) ušetřili. Vezmete jednoduše sklenici B a přilijete její obsah k tomu, co už je ve sklenici A. Sklenice B se dvěma díly vody
Vývojový diagram
Sklenice A, nyní již s pěti díly vody
Vztah bude mít formu zápisu:
A:=A+B ....... a je čten jako: A přiřazeno A+B (novému A přiřadíte staré A, ke kterému ještě přičtete B). Poznámka: Stejným způsobem lze realizovat odečítání, násobení, dělení nebo i složitější funkce, kde nová hodnota buňky je nějakou funkcí hodnoty původní buňky. 20
Algoritmizace
Větvení CÍL KAPITOLY: TVORBA TYPICKÝCH ALGORITMŮ S POUŽITÍM VĚTVENÍ Nové dovednosti: •
Ošetřování nežádoucích důsledků v algoritmech
•
Rozvětvení algoritmu v případech, kde přichází v úvahu několik žádoucích možností
•
•
výrazy s absolutní hodnotou, zjišťování vlastností čísel (lichá, sudá, kladná, záporná, dělitelnost...)
•
vyhledávání maxima a minima, řazení čísel podle velikosti
•
úlohy z geometrie
Kombinované algoritmy – rozvětvení algoritmu z důvodu více korektních řešení v kombinaci s ošetřováním nežádoucích důsledků
OŠETŘENÍ NEŽÁDOUCÍCH DŮSLEDKŮ Jedním z nejčastějších a nejdůležitějších důvodů, proč se používá v algoritmu větvení, je ošetření nežádoucích důsledků. Jak už víte, správný algoritmus musí dojít vždy do konce. Musí mít připravenou cestu pro všechny možnosti, které mohou nastat, tedy i pro ty, kde zadaná úloha nemá řešení a došlo by k havárii (ať v běžném životě, nebo ve virtuální realitě počítačového programu). Několik typických příkladů vám pomůže pochopit uvedenou problematiku.
Křižovatka Představte si, že stojíte na neřízené křižovatce a chcete přejít na druhou stranu. Nejdříve se musíte rozhlédnout, zda nejede auto: •
pokud nic nejede, můžete bez z obav přejít na druhou stranu;
•
jede-li něco, musíte zůstat stát.
Každý si jistě dokáže představit následky, pokud by se nerozhlédl a vstoupil do křižovatky, nebo kdyby se rozhlédl až poté, co by do křižovatky vstoupil. Vidíte, že cílem algoritmu není „přejít křižovatku okamžitě za každou cenu“, ale přejít ji, když víte, že se vám nic nestane. Pokud není možno přejít, pak jediným správným řešením je zůstat stát. Algoritmus skončí a k havárii nedojde (a vy můžete algoritmus po chvíli zkusit znovu).
Nejprve se situace vyhodnotí.
Teprve poté se činnost provede.
Upozornění: Při tvorbě algoritmu je potřeba pečlivě zvážit, zda v některém jeho kroku není skryto nebezpečí havárie. Pokud krok toto nebezpečí skrývá, musíte nejdříve otestovat, zda jej můžete provést. Na základě výsledku testu se algoritmus rozvětví - krok buď provedete, nebo volíte jinou cestu, ve které se krok neprovede. V dalších příkladech se bude výklad zabývat algoritmy pro výpočet matematických operací, u kterých je skryto nebezpečí havárie, což je nezbytně nutné ošetřit právě větvením. Je to především:
26
•
dělení;
•
výpočet výrazů s odmocninou;
•
některé další funkce (např. goniometrické - tangens).
Algoritmizace Maximum ze tří čísel s použitím pomocné buňky Nyní si ukážeme, jak je možné stejné zadání zpracovat pomocí algoritmu výměny obsahu buněk. Použité proměnné: A ... první číslo (zadané zvenčí) B ... druhé číslo (zadané zvenčí) C ... třetí číslo (zadané zvenčí) POM ... pomocná buňka Je testováno, zda není první číslo větší než druhé .
Pořadí A a B je správné, není zapotřebí vykonávat další operaci.
Bez ohledu na to, jaký byl stav na počátku, teď je B > A, o C zatím není nic známo.
Pořadí B a C je správné, není nutné vykonávat další operaci.
Pořadí je nesprávné, obsahy buněk je nutné mezi sebou vyměnit.
Testuje se, zda není druhé číslo větší než třetí.
Pořadí je nesprávné, obsahy buněk je nutné mezi sebou vyměnit. Bez ohledu na to, jaký byl stav na počátku, teď je C největší.
Maximum ze tří čísel s použitím dočasného maxima Příklad stejného zadání bude zpracován do třetice, ovšem opět jiným algoritmem. Povídka o masajském princi Masajský princ si hledal nevěstu a chtěl si vybrat tu nejkrásnější. Taková masajská krasavice musí být pěkně buclatá – čím tlustší, tím krásnější. Rozhodl se tedy, že pozve všechny krásky z okolí a bude je vážit. Jako váha mu posloužil kmen stromu, který uprostřed podepřel obětním kamenem. Takže měl houpačku, na jejíž konce hodlal posadit proti sobě dvě krásky – která tu druhou převáží, ta bude krásnější. Krajina byla řídce obydlená, proto se nevěsty trousily po jedné. Když přišla první, princ ji neměl s kým zvážit, proto ji zatím prohlásil za nejkrásnější a zdržel ji – co kdyby už žádná jiná nepřišla? Po chvíli přišla další. Posadil tedy Masajky na houpačku a vážil. Tu těžší z nich opět zdržel a prohlásil ji prozatím za nejkrásnější, druhou vyhodil. A tak to opakoval, dokud nevěsty chodily (tentokrát přišly jen tři, ale algoritmus by se dal opakovat pořád dokola pro velký počet adeptek). Použité proměnné:
34
A ... první číslo (zadané zvenčí)
C ... třetí číslo (zadané zvenčí)
B... druhé číslo (zadané zvenčí)
MAX ... pomocná buňka
Tvorba algoritmů s použitím cyklů
Cykly CÍL KAPITOLY: NAUČIT SE VYTVÁŘET ALGORITMY S POUŽITÍM CYKLŮ Nové pojmy: •
Cyklus s předem daným počtem opakování
•
Cykly řízené podmínkou •
podmínka na začátku cyklu
•
podmínka na konci cyklu
Nové dovednosti – typické algoritmy, jejichž základem je cyklus: •
Úlohy s opakováním – algoritmy, které byly v minulé kapitole řešeny jednorázově, budou rozšířeny o možnost opakování
•
Sumy, hledání maxima a minima, prohledávání řady čísel a textů
•
Oddechové úlohy – písničky, hry, hádanky
•
Číselné soustavy a převody mezi nimi
•
Řady – aritmetické, geometrické, mocninné a další
•
Operace s vektory a maticemi
•
Třídicí algoritmy
CYKLUS A JEHO TYPY Jedním z nejsilnějších nástrojů algoritmů jsou cykly. Jejich podstatou je opakování určité části algoritmu buď se stejnými, nebo pokaždé s jinými daty. Protože však každý algoritmus musí být konečný, nesmí žádný cyklus běžet pořád dokola. Musí být jednoznačně definováno, kdy (jak dlouho) nebo za jakých podmínek se bude cyklus opakovat a kdy už musí skončit. Podle způsobu řízení opakování rozeznáváme tři typy cyklů. Jsou to: •
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.
Vzpomeňte si na písničku „Pes jitrničku sežral“ z první kapitoly učebnice Algoritmizace. Víte, že správný algoritmus musí mít konec a že nelze písničku doopravdy zpívat pořád dokola. Cyklus můžete ukončit tak, že: •
Písničku zazpíváte například třikrát dokola a pak přestanete – v tom případě se bude jednat o cyklus s pevně daným počtem opakování.
•
Budete zpívat s podmínkou, že budete mít nějaké posluchače - napřed se rozhlédnete, je-li někdo nablízku. Pokud ano, dáte se do zpěvu a budete zpívat tak dlouho, dokud lidé neutečou – pak je to cyklus řízený podmínkou na začátku cyklu.
•
Dáte do zpěvu, aniž byste cokoli zjišťovali, a budete zpívat tak dlouho, dokud neochraptíte – pak se bude jednat o cyklus řízený podmínkou na konci cyklu.
docela maličkou
Nekonečný cyklus - opakuje se neustále dokola
53
Algoritmizace Zjištění, kolikrát se v textu objeví zadané písmeno – text je zadán najednou Tato úloha řeší stejný problém jako předešlá, ovšem s tím vylepšením, že testovaný text nebudete zadávat znak po znaku, ale celý najednou. Nové informace, které budete využívat v tomto algoritmu: •
Programovací jazyky mají možnost také pracovat s textovými řetězci (řadou znaků), které načtou do jediné proměnné. Tato proměnná je strukturovaná – každý znak tvoří jednu položku řetězce. Například: Textový řetězec VETA je “Ahoj”. Pak tedy:
VETA [1] = A VETA [2] = H VETA [3] = O
Načte se celá věta naráz
VETA [4] = J •
Programovací jazyky mají také možnost zjistit délku textového řetězce (mají na to potřebnou funkci). Nebudete proto zjišťovat délku textu sami, ale budete předpokládat, že bude v budoucím programu využita funkce, která to udělá za vás.
Hledané písmeno
Vynulování počítadla
Použité proměnné: VETA ... strukturovaná proměnná (řetězec), do které se načte celá věta VETA [I] ... I-tý znak proměnné VETA I ... řídicí proměnná cyklu s pevným počtem opakování POCZN ... počet znaků – proměnná, do níž se uloží číslo, které udává počet znaků ve větě (zjistí funkce v budoucím programu) X ... písmeno, které hledáte v textu POC ... počítadlo, do nějž se ukládá počet znaků věty, které jsou shodné s hledaným znakem
74
POCZN je počet znaků ve větě
Algoritmizace ODDECHOVÉ ÚLOHY Na závěr této podkapitoly si můžete vyzkoušet několik „oddechových“ algoritmů na práci s textem pomocí cyklu.
Písnička „Když jsem já sloužil“ Vytvořte algoritmus pro zobrazení textu písničky „Když jsem já sloužil“. Zde je text pro ty, kdo písničku neznají:
Když jsem já sloužil to první léto, vysloužil jsem si kuřátko za to, a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře. Když jsem já sloužil to druhé léto, vysloužil jsem si kačenku za to, a ta kačka bláto tlačká a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře. Když jsem já sloužil to třetí léto, vysloužil jsem si husičku za to, a ta husa chodí bosa a ta kačka bláto tlačká a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře. Když jsem já sloužil to čtvrté léto, vysloužil jsem si prasátko za to, a ten vepř jako pepř a ta husa chodí bosa a ta kačka bláto tlačká a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře.
Když jsem já sloužil to páté léto, vysloužil jsem si telátko za to, a to tele hubou mele a ten vepř jako pepř a ta husa chodí bosa a ta kačka bláto tlačká a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře. Když jsem já sloužil to šesté léto, vysloužil jsem si kravičku za to, a ta kráva mléko dává a to tele hubou mele a ten vepř jako pepř a ta husa chodí bosa a ta kačka bláto tlačká a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře. Když jsem já sloužil to sedmé léto, vysloužil jsem si volečka za to, a ten vůl jako kůl a ta kráva mléko dává a to tele hubou mele a ten vepř jako pepř a ta husa chodí bosa a ta kačka bláto tlačká a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře.
Princip řešení: •
Text písničky je jako stvořený pro cykly s pevným počtem opakování – v tomto případě půjde o dva cykly, které budou vnořeny do sebe.
•
Vnější cyklus s řídicí proměnnou I se bude opakovat 7x, jeden průchod cyklem pro každou sloku.
•
Vnitřní cyklus s řídicí proměnnou J zařídí vyjmenovávání všech zvířat (i s příměrem, co dělají nebo jak vypadají), která si dotyčný vysloužil. Všimněte si, že v každé sloce přibude jedno nové zvíře a pak se zopakují pozpátku všechna zvířata z předchozích slok. Číslo sloky tedy udává, kolik v ní bude zvířat. Proto řídicí proměnná bude mít meze od I do 1 (zvířata se vyjmenovávají pozpátku, proto bude J při každém průchodu cyklem o jedničku klesat).
Použité proměnné: I ... řídicí proměnná 1. cyklu (vnějšího) J ... řídicí proměnná 2. cyklu (vnitřního) Abyste nemuseli ve vývojovém diagramu psát dlouhé texty, uložte si je do strukturovaných proměnných. Tabulka strukturovaných proměnných je uvedena na následující stránce. 82
Tvorba algoritmů s použitím cyklů Tabulka strukturovaných proměnných Text1[1] := ”kuřátko” Text1[2] := ”kačenku”
Text2[1] := ”a to kuře krákoře, chodí po dvoře, má panenka pláče doma v komoře”
Text1[3] := ”husičku”
Text2[2] := ”a ta kačka bláto tlačká”
Text1[4] := ”prasátko”
Text2[3] := ”a ta husa chodí bosa”
Text1[5] := ”telátko”
Text2[4] := ”a ten vepř jako pepř”
Text1[6] := ”kravičku”
Text2[5] := ”a to tele hubou mele”
Text1[7] := ”volečka”
Text2[6] := ”a ta kráva mléko dává” Text2[7] := ”a ten vůl jako kůl”
Upozornění: V této úloze tentokrát použijete jiný typ strukturované proměnné než v úloze Zjištění, kolikrát se v textu objeví zadané písmeno na str. 73. V předešlé úloze jste do jedné položky strukturované proměnné mohli ukládat jediné písmeno (protože to tak vyhovovalo), zde můžete do každé položky uložit celý řetězec, budete pracovat s polem řetězců. Takový typ proměnné rovněž podporuje většina programovacích jazyků.
Pamatujte: •
•
Je-li v algoritmu několik cyklů vzájemně do sebe vnořených, pak se tyto cykly nesmějí křížit. To znamená, že cyklus, který začal nejpozději, musí skončit nejdříve, cyklus, který začal jako druhý nejpozdější, musí skončit jako druhý atd. Cyklus, který začal jako první, musí skončit až jako poslední.
Vnější cyklus Řídicí proměnná I řídí číslo sloky. Vnitřní cyklus
Opakuje se jednou na začátku každé sloky, za TEXT1[I] se dosadí výše uvedený text.
Řídicí proměnná J řídí vyjmenovávání zvířat v rámci každé sloky – po každém průchodu cyklem klesne o jedničku.
Za TEXT2[J] se dosadí příslušný text.
V algoritmu se také mohou vyskytovat cykly jeden za druhým, v tom případě se také nesmějí křížit. To znamená, že první, který začne, musí skončit ještě předtím, než začne druhý.
83
Algoritmizace Stavební spoření Vypracujte algoritmus pro výpočet částky, kterou naspoříte za celý jeden cyklus stavebního spoření. Podmínky stavebního spoření a vysvětlení pojmů, které budete dále potřebovat: •
Klient (střadatel) vkládá pravidelně jednou měsíčně dohodnutou částku (pořád stejnou).
•
Spoří takto pravidelně po celý cyklus, který trvá několik let od ledna do prosince (dříve to bylo 5 let, nyní je to 6 let, za čas to bude zase jiná doba, proto bude ponechána doba obecná – bude zadávána zvenčí). Délka cyklu musí být dodržena.
•
Peníze, které klient ukládá, jsou úročeny obvyklým způsobem (viz předchozí příklad Složité úrokování na str. 96-97). Bude předpokládáno, že úroková míra během celého cyklu zůstane stejná.
Až potud by se jednalo o obvyklou úlohu složitého úrokování, ovšem je dále ještě vylepšena: •
Naspoří-li klient během roku určitou maximální částku (dříve to bylo 18 000 Kč, nyní to je 20 000 Kč, za čas to bude třeba jinak, proto ji necháte obecnou a bude zadávána zvenčí), potom mu přísluší za tento rok maximální prémie (dříve to bylo 4 500 Kč, nyní to je 3 000 Kč, ponecháte ji proto zase obecnou a bude opět zadávána zvenčí): •
naspoří-li za rok méně než maximální částku, pak se maximální prémie úměrně zkrátí;
•
naspoří-li více, maximální prémie se už nezvýší.
•
Do naspořené částky se počítají i všechny úroky a prémie, které byly v daném roce připsány.
•
Naspořená částka se vyhodnotí každý rok koncem prosince, prémie se však připisuje až v květnu.
•
Jakmile se prémie připíše ke vkladu, normálně se úročí jako všechno ostatní.
(Poznámka: Úloha je mírně zjednodušena.) Použité proměnné: ULOZ ... pravidelná měsíční úložka PR ... roční procentní úroková sazba N ... počet let, po která střadatel spoří MPR ... maximální prémie, která může být střadateli připsána, pokud naspoří za rok maximální částku, z níž se odvozuje prémie: •
naspoří-li za rok částku vyšší, pak už prémie dál neroste
•
naspoří-li za rok částku nižší, pak se prémie zkrátí v poměru naspořené částky ku maximální částce, ze které se odvozuje prémie
PREM ... prémie, která bude střadateli připsána. Počítá se jako poměrná část z maximální prémie: •
naspoří-li za rok částku vyšší nebo rovnou maximální roční uspořené částce (MCR), pak dostane maximální prémii (MPR)
•
naspoří-li za rok částku nižší, pak se prémie zkrátí v poměru naspořené částky ku maximální částce, ze které se odvozuje prémie
MCR ... maximální roční uspořená částka, ke které přísluší maximální prémie (pokud by střadatel naspořil víc, prémie se už dál nezvyšuje) Do roční uspořené částky se započítávají i připsané úroky a prémie za minulý rok. MPL ... počet let, po která bude střadatel spořit SUMR ... suma úspor v průběhu jednoho roku (do této částky se kromě vkladů započítávají i úroky a prémie za minulý rok) SUMC ... celková suma za uplynulé období UROKC ... roční úrok z částky, která leží na účtu déle než rok UROKR ... úrok z úložek, které přicházely na účet během posledního roku Princip řešení: • 98
Nebýt prémie, která se připisuje vždy jednou za rok v květnu, jednalo by se o obyčejnou úlohu o složitém úrokování (viz předchozí příklad Složité úrokování na str. 96-97).
Tvorba algoritmů s použitím cyklů •
Opět v tomto algoritmu poběží souběžně dva cykly složitého úrokování – jeden s úložkou 1x měsíčně a jeden s úložkou 1x ročně.
•
Vezmete-li v úvahu jen interval jednoho roku, pak se v něm projeví pouze měsíční úložky – většinou pravidelné, pouze v 5. měsíci zvednuté o prémii. Tím můžete vytvořit cyklus s pevným počtem opakování (a to 12).
•
Cyklus, který je zmíněn v předchozím bodu, bude součástí dalšího cyklu – rovněž s pevný počtem opakování (počet let). V tom se zjistí, kolik klient naspořil, vypočítá se prémie, na kterou bude mít příští rok v květnu nárok a připočítají se úroky.
Všechny proměnné, ke kterým se bude něco přičítat, musí být vynulovány.
Vnější cyklus - počet let
Vnitřní cyklus – měsíční úložky během roku
Je-li květen, připočítá se prémie.
Připočítá se další úložka. Připočítá se úrok.
Výpočet prémie – uspoří-li klient více, dostane nakonec stejně jen maximální prémii.
Úrok z částky, která je na účtu déle než rok
Poměrná částka z maximální prémie Nová celková částka, do které je připočítána naspořená částka za uplynulý rok a jsou připsány všechny úroky.
Vynuluje roční sumu a roční úrok.
99
