Algoritmizace
Algoritmizace - osnova otázky:
1. algoritmus, vlastnosti algoritmu,
2. vývojové diagramy, značky VD, převod VD na program
Algoritmus
Algoritmus je přesný postup, který je potřeba k vykonání určité činnosti. Přesně definovaná
konečná posloupnost operací.
Vlastnosti algoritmu:
1. Jednoznačnost (determinovanost) - jednotlivé kroky algoritmu a pořadí, v jakém budou
prováděny, jsou jednoznačně určeny. Při stejných počátečních hodnotách vede
algoritmus k témuž výsledku.
2. Konečnost (rezultativnost) - algoritmus vede vždy k určitým výsledkům v konečném
čase.
3. Obecnost (hromadnost) - algoritmus lze použít pro řešení obecné úlohy, slouží k řešení
libovolné úlohy, která patří do jisté třídy úloh.
4. Opakovatelnost - znamená, že algoritmus vede vždy ke stejným výsledkům, jsou-li
zadána stejná data.
5. Srozumitelnost a přehlednost - je podmínkou pro pozdější snadné úpravy.
Možnosti zápisu algoritmu
-
slovní vyjádření – v přirozeném jazyce
matematický zápis – soustava rovnic, vztah mezi veličinami
graficky - vývojové diagramy
počítačové programy – kódem srozumitelným pro počítač
Značky vývojových diagramů
Mezní značky
Představují vstup s vnějšího prostředí do programu nebo výstup z programu do vnějšího
prostoru (začátek, konec). Používá se i pro začátek nebo konec samostatně zpracované
části.
Začátek
Konec
Začátek - použitá na začátku, do značky nesmí vstupovat žádná hrana
a musí s ní vystupovat právě jedna hrana z dolního okraje směrem
dolů, před touto značkou už nesmí být žádná jiná značka
Konec - používá se na konci, do značky smí vstupovat právě jedna
hrana z horního okraje směrem dolů, nesmí z ní vystupovat žádná
hrana, za touto značkou nesmí být žádná jiná značka
Algoritmizace
Sekvenční bloky
Vyskytuji se uvnitř vývojových diagramů, označuji sekvenční postup algoritmu, v jejich
průběhu nesmí dojít k rozvětvení.
Sekvenční blok - musí mít právě jeden vstup a jeden výstup
Čti: A, B
A:= A+B
Vstup nebo Výstup
Vstup – načtení dat potřebných pro činnost programu, uvnitř je Čti:
Výstup – zobrazení výstupu programu na zobrazovacím zařízení,
uvnitř je Zobraz:… (Piš…)
Zpracování - znázorňuje část programu, při níž dochází k transformaci
dat (mat. operace). V bloku může být zapsána jedna nebo více
instrukci.
Větvení
V některých případech nelze v algoritmu postupovat sekvenčně, ale ho potřeba rozvětvit.
K větvení dochází na základě nějaké podmínky, je-li podmínka splněna, pak program
pokračuje jednou cestou, není-li splněna, pokračuje cestou jinou (větví se)
+
Podmínka
-
Rozhodovací blok - slouží k rozvětvení programu na základě
podmínky. Není rozhodující, zda větev + bude vlevo nebo
vpravo. Hrany nemusejí vycházet vždy z bočních vrcholů.
V některých publikacích se setkáte s označením větví –
a) ano, ne
b) yes, no
Další značky
Příprava - přípravná fáze programu, například pro zahájení cyklu o
známém počtu opakování. Stejná značka může být i na konci cyklu
s textem Konec cyklu
Cyklus
I:= 1, N
Spojka - spojuje dvě části vývojového diagramu, které nebylo možno
zakreslit souvisle. Spojky na konci přerušení a na začátku pokračování
musí být označeny stejným číslem
1
Načíst matici
A
Podprogram - samostatná část programu, která může obsahovat větší
množství kroků:
a) vyskytuje-li se v programu nějaká část na více místech, je vhodné
zpracovat samostatně, označit jako jeden blok a vložit do výsledného
algoritmu
b) vyskytuje-li se ve více algoritmech hodně často jedna část,
zpracujeme ji jako část samostatnou
2
Algoritmizace
Syntaxe a sémantika
syntaxe příkazu
- popisuje, jak příkaz správně a bezchybně vytvořit
sémantika příkazu - popisuje význam tohoto příkazu
v ČJ: syntax (skladba)
př.: Děti četli knihu.
X
sémantika (smysl)
Kniha četla děti.
Syntaxi známe z hodin českého jazyka. Popisuje jak správně napsat větu. Pokud spletete
i/y nebo písmeno znamená to, že jste udělali syntaktickou chybu.
Sémantika hovoří o smyslu informace, kterou nám věta říká.
Příklad chyby syntaxe:
Dělníci vykopaly tunel. Mám rád hranolki. Hnet příjdu!
Příklady chyb sémantiky: Klára prší. Zítra byl jsem včera. Medvěd liška zvítězíme.
Základní pojmy algoritmizace
Algoritmus
přesný postup, jenž vede k vyřešení určitého problému
Proces
děj, událost, operace apod., který probíhá u objektů v určitém čase, je
dynamická
Cyklus
jakýkoliv cyklicky se opakující děj, událost, proces či jev
Spojka
značka používající se pro přehlednost a zjednodušení, díky ní můžeme
propojit různé bloky vývojového diagramu na kterýchkoli místech v
diagramu (z důvodu nekřížení jednotlivých větví v diagramu)
slouží pro stručnější vyjádření změn hodnot proměnných
základ všech algoritmů
syntax:
proměnná : = výraz
sémantika: nejprve se vyhodnotí hodnota výrazu, tato hodnota je pak
přiřazena proměnné uvedené na levé straně příkazu
místo v paměti počítače označené identifikátorem, do kterého se
ukládá hodnota. Velikost tohoto místa je určená datovým typem
objekt, který má pevně stanovené označení a nese určitou hodnotu;
hodnota se může během programu měnit
pro označení se používají písmena abecedy a číslice, první musí být
písmeno
Pozor!
- proměnné potřebné pro výpočty je třeba na začátku nastavit
(pro číselné proměnné to obvykle znamená přiřazení 0)
- proměnná, která dosud nezískala žádnou hodnotu, má
neidentifikovatelný obsah, nelze spoléhat na to, že obsahuje nulu
nebo mezeru
- použijeme-li v programu nedefinovanou proměnnou, dojde k chybě
- stejná proměnná se může objevit na pravé i levé straně
přiřazovacího příkazu (např. i: = i+1)
- příkaz i:=i+1 zvýší hodnotu proměnné o jedničku
objekt určité hodnoty, jež se nemění
(např. konstanta pi obsahuje hodnotu 3.14)
jméno proměnné nebo konstanty
příklady správných identifikátorů: a, b, i, suma, počet, A1, s5
Přiřazovací příkaz
Proměnná (variable)
Konstanta (constant)
Identifikátor
3
Algoritmizace
Rozhodovací blok
-
základním prvkem je podmínka (condition) – logický výraz, jehož
hodnotou je pravda nebo nepravda
syntaxe: proměnná
relační operátor výraz,
- relační operátory: >, <, =, >=, <=, <>,
- výraz: lze použít proměnné, konstanty, (),
- pomocí logických spojek and, or lze sestavovat složené podmínky,
- větve plus a minus se na konci musí sbíhat v jednom bodě
sémantika:
- vyhodnocení podmínky, pokud podmínka platí, provede se příkaz
uvedený ve větvi plus (+),
- pokud podmínka neplatí, provede se příkaz uvedený ve větvi
minus (-),
podmínka v podmínce, složený podmíněný příkaz:
příkazem uvnitř podmínky je další podmíněný příkaz
neúplný podmíněný příkaz:
jedna z větví rozhodovacího bloku je prázdná (větev minus)
Vývojové diagramy strukturované
Začátek
Větvení - slouží k ošetření nežádoucích důsledků a výběru
možností. Každý algoritmus musí dojít do konce, pokud by
nedošlo k ošetření nežádoucích situací, program by zkolaboval.
Jede
auto
Příklad křižovatka:
-
-
stojíš na neřízené křižovatce a
chceš přejít na druhou stran
sestav slovní algoritmus
(rozhodnutí, zda je volno nebo ne)
-
++
Stůj
Přejít
na
druhou
stranu
Konec
Poznámka:
- při tvorbě algoritmu musíme vždy zvážit všechna nebezpečí, aby nedošlo k havárii
- na základě toho můžeme algoritmus rozvětvit - existuje cesta, ve které se krok
neprovede
Úkol:
Sestavte vývojový diagram, který vytiskne
maximum ze dvou celých čísel.
Slovní algoritmus:
Přečtu dvě čísla, pokud je první vetší než druhé,
vytisknu první číslo, jinak vytisknu druhé číslo.
Poznámky k řešení příkladu:
1. Dvě zadaná čísla se načtou do proměnných a, b.
2. Zkoumá se pravdivostní hodnota podmínky a>b, což
je odpověď na otázku: je a vetší než b?
4
Algoritmizace
3. Pokud podmínka platí (odpověď je ano), pokračuje se větví + a vytiskne se na výstup
číslo a.
4. Pokud podmínka neplatí (odpověď je ne), pokračuje se větví - a vytiskne se na výstup
číslo b.
Je vidět, že hodnota proměnné a bude vytisknuta právě v tom případě, kdy platí a>b.
Bude-li naopak platit a<b, vytiskne se hodnota proměnné b.
Co se ale stane, budou-li obě čísla stejná a platí tedy a=b? Ověřovací podmínka a>b
nebude platit (protože neplatí třeba 3>3), vytiskne se proto hodnota b. Protože však a=b, je
úplně jedno, kterou proměnnou vytiskneme. Obojí je správně.
Úkol: Sestavte vývojový diagram, který zjistí, zda dané číslo je nebo není kladné.
Slovní algoritmus:
Přečtu číslo, pokud je vetší než nula vytisknu odpověď je (kladné), jinak tisknu není
(kladné).
Poznámky k řešení:
1. Do proměnné n je načteno číslo.
2. Zkoumá se pravdivostní hodnota podmínky
n>0, což je odpověď na otázku: je n kladné?
3. Pokud podmínka platí, vytiskne se na výstup
odpověď „Je kladné“.
4. Pokud podmínka neplatí, vytiskne se na
výstup odpověď „Není kladné“.
Je vidět, že kladná odpověď bude vytisknuta
právě v tom případě, kdy je číslo n kladné.
Bude-li ale zadáno záporné číslo, vytiskne se
zpráva, že číslo není kladné.
Co se ale stane, bude-li zadána nula?
Ověřovací podmínka n>0 nebude platit (protože
neplatí 0>0), vytiskne se proto, není kladné.
Je to správně, protože nula není kladné číslo.
5
Algoritmizace
Úkol: Je dáno celé číslo. Rozhodnete, zda je kladné, záporné nebo nula.
Slovní algoritmus:
Přečtu číslo, pokud je vetší než nula, vytisknu je
kladné a končím, pokud není vetší než nula,
muže být
záporné nebo nula. Na tuto informaci se tedy
zeptám a podle výsledku vytisknu odpověď.
Poznámky k řešení:
1. Do proměnné n je načteno číslo.
2. Zkoumá se pravdivostní hodnota podmínky
n>0, což je odpověď na otázku: je n kladné?
3. Pokud podmínka platí, vytiskne se je kladné.
4. Pokud podmínka neplatí, ptáme se dále, platí-li
n=0. V závislosti na platnosti této podmínky se
vytiskne se je záporné nebo je nula.
Pro každé celé číslo vždy musí nastat právě
jedna z uvedených možností. Tento vývojový
diagram ale není řešením jediným. Podmínky
n>0, n=0 je možné vzájemné prohodit,
samozřejmě též i texty u výstupní zprávy.
Podmínky lze zapsat i v negaci (opačné), tedy
n<0, n<>0.
Úkol: Je dáno přirozené číslo. Rozhodnete, zda je jednociferné, dvouciferné či víceciferné.
Slovní algoritmus:
Přečtu číslo, pokud je menší než deset,
vytisknu je jednociferné a kočím, pokud je větší
než deset, muže být dvojciferné nebo
víceciferné. Zeptám se proto, jestli je menší
než 100 a vytisknu odpověď.
Poznámky k řešení:
1. Do proměnné n je načteno číslo.
2. Zkoumá se pravdivostní hodnota podmínky
n<10, což je odpověď na otázku: je n menší
než 10?
3. Pokud podmínka platí, vytiskne se na výstup
odpověď je, jednociferné.
4. Pokud podmínka neplatí, ptáme se dále,
platí-li n<100. V závislosti na platnosti této
podmínky se vytiskne odpověď je dvojciferné či
je víceciferné.
Pro každé celé číslo vždy musí nastat právě
jedna z uvedených možností, tedy musí být
kladné, záporné nebo nula.
6
Algoritmizace
Úkol 6: Uspořádejte dvě daná čísla vzestupně.
Slovní algoritmus:
1. verze: Přečtu čísla a,b, pokud je první z nich vetší než druhé, vytisknu je v opačném
pořadí (b,a), jinak vytisknu v pořadí načtení (a,b).
2. verze: Přečtu čísla a, b pokud je první z nich vetší než druhé, čísla prohodím. Vytisknu
pak a, b.
Poznámky k řešení:
1. verze: je bez komentáře
2. verze: v případě, že je první číslo větší než druhé,
platí podmínka a>b a provede se výměna hodnot a,b.
K tomu je třeba pomocná proměnná pom.
V závěru se vytisknou hodnoty a,b vždy v tomto pořadí.
Vícenásobné větvené - příkazu CASE
hodnoty, podle kterých se uvnitř příkazu rozhoduje, bývají konstanty stejného datového
typu jako řídící proměnná. Tuto hodnotu může tvořit i více údajů
- seznam:
hodnoty oddělené čárkou (1,2,3)
- interval:
dolní a horní mez oddělená znaky .. (1..5)
pokud potřebujeme provést v jedné větvi více
příkazů, je odpovídající příkaz složený a musí se
proto použít závorky begin end.
Příklad: Kalkulačka s rozhodováním.
7
Algoritmizace
Tvorba algoritmů s použitím cyklů
Ve skutečných algoritmech se často setkáváme s cykly. Cyklus lze chápat jako určitý počet
opakování. Protože u každého algoritmu musí platit podmínka konečnosti, musí být i u
cyklu přesně stanoveno, počet opakování, určení, kdy musí algoritmus skončit. Opakování
se ve vývojovém diagramu projeví zpětnou šipkou, která se vrací o několik příkazu nahoru.
Příkazy, které se mají opakovaně vykonávat, tvoří tzv. tělo cyklu.
Podle způsobu opakování rozeznáváme tři typy cyklů:
1. s pevným počtem opakování
2. řízené podmínkou - s podmínkou na začátku cyklu
3. řízené podmínkou - s podmínkou na konci cyklu
Značení cyklu:
Tělo cyklu
Cyklus s pevným počtem opakování
Umožňuje provádět příkazy třeba desetkrát,
stokrát i obecně n krát, kde n je proměnná
načtená na začátku diagramu. Chod tohoto cyklu
řídí jeho počítadlo. Je to proměnná, nejčastěji
označovaná i, která automaticky při každém
průchodu cyklem zvýší svoji hodnotu o jedničku.
Její počáteční hodnota je dána dolní mezí (často
je to 1), konečná hodnota je dána horní mezí
(10,100, n). Po dosažení horní meze cyklus končí.
Máme pro něj speciální značku.
Výhoda tohoto cyklu je ta, že programátor nemusí psát ukončovací podmínku cyklu ani
zvyšovat počítadlo. Přesto je ukončovací podmínka implementována uvnitř cyklu, jedná se
vlastně o cyklus s podmínkou na začátku. Pokud je horní mez menší než dolní mez, cyklus
se neprovede ani jednou.
8
Algoritmizace
Tělo
cyklu
Cyklus řízený podmínku na začátku cyklu
V tomto cyklu nevíme, kolikrát proběhne, ale jeho
průběh bude záviset na tom, zda je nebo není splněná
určitá podmínka řídicího cyklu.
Není – li podmínka splněna hned na začátku před
prvním vstupem do cyklu, pak se do cyklu vůbec
nevstoupí.
Cyklus řízený podmínkou na konci cyklu
Tělo
cyklu
V tomto cyklu opět nevíme, kolikrát proběhne, ale
s určitosti můžeme říct, že proběhne nejméně jedenkrát.
Další průběh bude záviset na tom, zda je nebo není
splněná určitá podmínka.
Není – li podmínka splněna, cyklus se po prvním
opakování ukončí. Cyklus bude probíhat, pokud bude
splněna podmínka cyklu.
Tvorba algoritmů s použitím cyklů – příklady
Cyklus s pevným počtem opakování
Úkol: Sestavte vývojový diagram, který vytiskne čísla od 1 do n. Použijeme cyklus s pevným
počtem opakování.
Poznámky k řešení:
1. Do proměnné n se načte vstupní hodnota.
2. Začíná cyklus, hodnota počítadla i je nastavena na 1.
3. Testuje se platnost ukončovací podmínky cyklu i=n.
4. Pokud podmínka platí, cyklus skončí a následuje také
konec diagramu. Pokud podmínka neplatí, vypíše se
hodnota počítadla a řízení se vrací na začátek těla
cyklu, počítadlo se automaticky zvyšuje o jedničku.
9
Algoritmizace
Obecně lze říci k cyklu s pevným počtem opakování toto:
-
Tělo cyklu nemusí být provedeno ani jednou (je-li počáteční hodnota počítadla vetší
než hodnota koncová, např. pro I=1,0).
Používá se velmi často, známe-li počet opakování.
Zápis tohoto cyklu v Pascalu je velmi přirozený a snadný.
Je oblíbený matematiky i techniky.
Cyklus s podmínkou na konci
Úkol: Je dána posloupnost n čísel. Sestavte vývojový diagram, který vytiskne počet kladných
čísel v této posloupnost (poznámka: kladné číslo je větší než nula). Použijte cyklus s podmínkou
na konci.
Slovní řešení:
Nejprve si problém ujasníme na konkrétních
příkladech:
pro n=5 a posloupnost 4,10,-2,7,-1 je počet
kladných čísel 3
pro n=3 a posloupnost -4, -10, -18 je počet
kladných čísel 0
pro n=6 a posloupnost 2,3,2,8,10,5 je počet
kladných čísel 6
Počet kladných čísel se pohybuje v intervalu
<0,n>. Náš úkol je ho zjistit a vytisknout. Počet
kladných čísel bude obsahovat nějaká
proměnná, například k. Na začátku ji musíme
vynulovat, stejně jako počítadlo cyklu i. Počet
čísel v posloupnosti udává tradičně n, tuto
hodnotu načteme.
Poznámky k řešení:
1. Vynuluje se proměnná k pro výpočet počtu
kladných čísel.
2. Vynuluje se počítadlo cyklu i.
3. Do proměnné n se načte vstupní hodnota.
4. Začíná tělo cyklu: do proměnné a se přečte
jedno číslo, počítadlo se zvýší o jedničku,
testuje se podmínka a>0, ptáme se tedy, je
číslo a kladné?
Pokud podmínka platí, zvýšíme dosavadní
počet kladných čísel o jedničku, pokud
podmínka neplatí, neuděláme nic.
5. Testuje se platnost ukončovací podmínky
cyklu i=n. Pokud podmínka platí, cyklus skončí,
vypíše se výsledný počet kladných čísel a
následuje konec diagramu. Pokud podmínka
neplatí, vracíme se zpět na začátek těla cyklu.
Vyzkoušejte činnost diagramu třeba pro n=5 a
řadu pěti čísel 2 -1 5 10 -3. V této řadě jsou tři
10
Algoritmizace
kladná čísla a hodnotu 3 by měl vytisknout pomocí proměnné k i tento vývojový diagram.
V diagramu byl použit neúplný podmíněný příkaz (pro podmínku a>0).
Pokud v řadě čísel budou samé záporné hodnoty, vytiskne se na závěr nula, což je správně.
V případě zadání záporné či nulové hodnoty do proměnné n se diagram zacyklí. Argumentem
pro správnost uvedeného diagramu je to, že posloupnost - 4 čísel reálně neexistuje. Uživatel,
který tento nesmyslný vstup zadá, to asi také nezdůvodní. I když kdyby to byl čistý matematik,
kdo ví...
Na druhou stranu skutečný program zapsaný v jakémkoliv programovacím jazyku reaguje
smysluplně na jakékoliv (i hodně nesmyslné) vstupní hodnoty. Je tedy nad čím přemýšlet.
Cyklus s podmínkou na začátku
Úkol: Sestavte vývojový diagram, který vytiskne čísel v posloupnosti 1,2,3…n. Použijte cyklus s
podmínkou na začátku.
Poznámky k řešení:
1. vynuluj počítadlo i
2. přečti číslo n - horní mez, počet čísel
3. dokud platí podmínka i<n opakuj
- zvyš i o jedničku
- vytiskni i
Další řešené příklady
Úkol: Zobrazení čísel od jedničky do desítky.
Poznámky k řešení:
Použijeme cyklus s pevným počtem opakování. Při
prvním průchodů cyklem má proměnná I hodnotu 1,
při druhém průchodu cyklem má hodnotu 2, při
třetím průchodů cyklem má hodnotu 3 atd…..., při
desátém průchodů cyklem má hodnotu 10.
11
Algoritmizace
Úkol: Kalkulačka
Začátek
Zobraz: „ zadej
1.
2.
3.
4.
sčítání
odčítaní
násobení
dělení
Použité proměnné:
KOD…kód operace, který je zadán zvenčí
A,B ….dvě čísla zadaná zvenčí, se kterými se bude
provádět požadovaná operace
C……..výsledek operace
Čti: KOD
Čti: A, B
+
C:=A+B
KOD =1
KOD = 2
+
C : = A-B
KOD =3
+
C : = A*B
KOD = 4
-
+
B=0
C : = A/B
+
Zobraz: „B
nesmí být 0“
Zobraz:
„Zadal jsi
špatný kód“
Skončit?
+
Konec
12
Zobraz:
„C“
Algoritmizace
Otázky
1.
2.
3.
4.
5.
6.
Co je to algoritmus?
Jaké jsou základní vlastnosti algoritmu?
Způsoby vyjádření algoritmu
Značky vývojových diagramu – dělení, nákres.
Co popisuje syntaxe a sémantika algoritmu?
Vysvětli pojmy:
- proces
- cyklus
- spojka
- přiřazovací příkaz
- proměnná
- konstanta
- rozhodovací blok
7. Vysvětli syntaxi a sémantiku přiřazovacího příkazu.
8. Může se proměnná vyskytovat na levé či pravé straně přiřazovacího příkazu?
9. Co se stane s hodnotou proměnné, je-li zapsán tento příkaz: i:=i+1 ?
10. Kdy nastavujeme hodnotu proměnné?
11. Co je to identifikátor? (příklady povolených a nepovolených identifikátorů)
12. Co je základním prvkem rozhodovacího bloku a jaká je hodnota tohoto základního
prvku?
13. Vyjmenuj relační operátory rozhodovacího bloku.
14. Popiš syntaxi a sémantiku rozhodovacího bloku.
15. Vysvětli pojem složená podmínka (příklad).
16. Pomocí jakých logických spojek sestavujeme složené podmínky?
17. Vysvětli pojem neúplná podmínka.
18. Vyjmenuj typy cyklů.
19. Který cyklus využiješ při známém počtu opakování (např.5x).
20. Vysvětli rozdíl mezi cyklem s podmínkou na začátku a na konci.
13
Download

Algoritmizace