20.12.2011
ALGORITMIZACE 1
PROGRAMOVÁNÍ VT3/VT4 Mgr. Martin ŠTOREK
LITERATURA
ALGORITMIZACE Ing. Jana Pšenčíková ComputerMedia http://www.computermedia.cz/
2
1
20.12.2011
ALGORITMUS
Algoritmus je přesný postup, který je potřeba k vykonání určité činnosti
Nezbytné podmínky:
musí mít začátek a konec (musí dojít do konce) musí být věcně správný (správný matematický vztah) musí být jednoznačný (každý krok musí být jasný) musí být obecný (řešení nejširšího množství úloh) musí být opakovatelný (lze kdykoli zopakovat) musí být srozumitelný (pochopitelný pro programátora) 3
ZAČÁTEK A KONEC ALGORITMU začátek
začátek
I:=0
Čti: A, B
Čti: A, B C:= A + B
C:= A + B Vypiš: C
Vypiš: C
I:=I+1
I=5
konec
4 špatný algoritmus opakuje neustále stejné kroky nebo „zatuhne“ nebo systém havaruje z důvodu přetečení paměti
2
20.12.2011
VĚCNÁ SPRÁVNOST
– PLOCHA OBDÉLNÍKU
začátek
začátek
Čti: A, B
Čti: A, B
S:= 2A + B
S:= A * B
Vypiš: S
Vypiš: S
konec
konec
špatný algoritmus poskytuje nesprávné výsledky, program zdánlivě pracuje správně; většinou chyba ve vzorci (zlomky a odmocniny)
5
JEDNOZNAČNOST
začátek začátek
Bude hezky?
„půjdu do kina“
„půjdu na výlet“ „půjdu do kina“
„půjdu na výlet“
konec
další chyby: - dělení nulou - chybějící větev v podmínce
konec
špatný algoritmus poskytuje v některých případech správné výsledky, v jiných případech havaruje nebo poskytuje nesprávné výsledky
6
3
20.12.2011
OBECNOST začátek začátek
Čti: A, B 2:= 1 + 1 C:= A + B Vypiš: výsledek Vypiš: C konec konec
algoritmus musí být co nejobecnější, aby bylo možno pomocí něj řešit co nejširší množství úloh
7
OPAKOVATELNOST začátek
začátek Čti: A, B
Čti: A, B
X:= 7
C:= X*A + B
C:= X*A + B
Vypiš: C
Vypiš: C
konec
konec
algoritmus lze kdykoli zopakovat a při stejných podmínkách se bude chovat stejně (při stejných vstupech – stejný výstup)
8
4
20.12.2011
SROZUMITELNOST
Každý algoritmus musí být natolik srozumitelný, aby mu rozuměl programátor, který bude dle něho vytvářet aplikaci a samozřejmě i sám tvůrce, který bude schopen na základě přání uživatele algoritmus (postup) upravit.
Pro zápis algoritmu se proto volí přehledná a srozumitelná metoda.
Používání komentářů v dostatečné míře
Všechny použité proměnné řádně popsat a vysvětlit jejich význam
9
ZÁPIS ALGORITMŮ
SLOVNÍ VYJÁDŘENÍ (recept, školní řád, smlouva)
domluva i s laikem když není jiná možnost nejméně přehledná nelze „uhlídat“ zda je algoritmus jednoznačný a přesný
MATEMATICKÝ ZÁPIS (vzoreček, rovnice)
je jednoznačný (nutná znalost úpravy matem. výrazů) většinou málo podrobný (většinou nelze přímo zadat počítači – podmínky řešitelnosti)
x1, 2 =
− b ± b 2 − 4ac 2a
10
5
20.12.2011
ZÁPIS ALGORITMŮ
ROZHODOVACÍ TABULKY (rozvrh, výpočet daně)
zápis jednoznačný, přehledný a pochopitelný vhodný pro více možností – každé řešení zvlášť nehodí se vždy někdy nutno delší vysvětlování
základ daně od
základ daně do
daň
ze základu přesahující
0
121 200
12%
121 200
218 400
14 544 + 19%
121 200
218 400
331 200
33 012 + 25%
218 400
331 200
a více
61 212 + 32%
331 200 11
ZÁPIS ALGORITMŮ POČÍTAČOVÉ PROGRAMY
jediná forma srozumitelná pro člověka (programátor) a počítač (nutno kompilovat do strojového kódu) rozumí pouze programátor (znalost programovacího jazyka) málo názorná a přehledná (kombinuje se z vývoj. diagramem)
VÝVOJOVÉ DIAGRAMY (schémata)
symbolický programovací jazyk pro názorné zobrazení algoritmu nejdokonalejší forma zápisu používá se při vývoji SW
komunikace mezi programátory a analytiky dokumentační účely
12
nutná znalost jednotlivých symbolů
6
20.12.2011
ZNAČKY VÝVOJOVÝCH DIAGRAMŮ Mezní značky Začátek (vystupuje pouze jedna hrana) Konec (vstupuje pouze jedna hrana)
Sekvenční bloky Zpracování (příkazy sečtení, vynásobení, jiná matematická nebo logická operace) Může být zapsáno i více instrukcí 13
ZNAČKY VÝVOJOVÝCH DIAGRAMŮ Sekvenční bloky Vstup (načtení potřebných dat; obsahuje text: Čti:) Výstup (zobrazení výstupů programu na zobrazovací zařízení; obsahuje text: Zobraz:)
Rozhodovací blok Podmínka (k rozvětvení programu na základě podmínky)
14
7
20.12.2011
SEKVENCE Sekvence je nejjednodušším typem algoritmu, který se skládá pouze ze sekvenčních bloků. Během sekvence nesmí docházet k větvení ani k cyklům (opakování). Příklady:
Obdélník – obvod a obsah Obvod kružnice a obsah kruhu Rovnostranný trojúhelník – obvod a obsah Součet, rozdíl a součin
POZOR na podíl a odmocninu (nutnost ošetření vstupů) – nutnost větvení- NENÍ sekvence
15
SOUČET OBSAHU DVOU BUNĚK, PŘIŘAZENÍ C:= A + B
sklenice A
sklenice B
sklenice C
A:= A + B
sklenice A
sklenice B
sklenice A 16
8
20.12.2011
VÝMĚNA PROMĚNNÝCH
- PROHOZENÍ
Jak vyměnit obsah sklenic A a B ? krok 2
krok 1
krok1 C:= B krok 2 B:=A krok 3 A:=C krok 3
sklenice A
sklenice B
sklenice C
17
SEKVENČNÍ ALGORITMY ÚKOL Sestavte algoritmus pro výpočet obvodu a obsahu kruhu
18
9
20.12.2011
LOGICKÝ SOUČIN A SOUČET Výrok A
Výrok B
A AND B
A OR B
1
1
1
1
1
0
0
1
0
1
0
1
0
0
0
0
OR
AND
19
LOGICKÉ FUNKCE
Logický součin (A AND B)
A … půjde na rande dívka (ANO×NE) B … půjde na rande chlapec (ANO×NE) A AND B … rande se uskuteční (ANO×NE)
Výrok A
Výrok B
A AND B
1
1
1
1
0
0
0
1
0
0
0
0
20
10
20.12.2011
LOGICKÉ FUNKCE
Logický součet (A OR B)
A … první posel doručí zprávu (ANO × NE) B … druhý posel doručí zprávu (ANO × NE) A OR B … zpráva bude doručena (ANO × NE)
Výrok A
Výrok B
A OR B
1
1
1
1
0
1
0
1
1
0
0
0 21
ÚKOLY Součet dvou proměnných, přiřazovací příkaz Výměna obsahu dvou proměnných (prohození) Obvod kružnice a obsah kruhu Obvod a obsah šestiúhelníka
22
11
20.12.2011
ALGORITMY VĚTVENÍ začátek
ÚKOL Sestavte algoritmus pro výpočet podílu dvou čísel A,B
Čti: A, B
B=0
C:= A / B
Zobraz: „Dělení nulou !!“
Vypiš: C
konec
23
ÚKOLY Dělení výrazů ( A + B děleno C+D) Trojúhelníková nerovnost Druhá odmocnina Libovolná odmocnina Absolutní hodnota čísla A Číslo kladné, záporné či nula? Číslo sudé či liché? Dělitelnost čísla libovolným číslem Porovnání čísel a zobrazení dle velikosti Seřazení dvou čísel (pomocná proměnná – prohození)
24
12
20.12.2011
ÚKOLY Největší ze tří čísel (bez a s pomocnou proměnnou) Největší ze tří čísel (s dočasným maximem) Seřazení tří čísel dle velikosti (bez a s pomocnou prom.) Trojúhelník rovnostranný, rovnoramenný a obecný Pravoúhlý trojúhelník (Pythagorova věta) Lineární rovnice Soustava dvou lineárních rovnic Kvadratická rovnice s reálnými kořeny Jednoduchá kalkulačka (+, -, *, /) Rychlost, dráha, čas Srážka vlaků (S, V1, V2)
25
ALGORITMY CYKLŮ – s pevným počtem opakování začátek
ÚKOL Vypiš čísla od 1 do 20
cyklus I:= 1 to 20
Vypiš: I
konec cyklu
konec
26
13
20.12.2011
ÚKOLY Čísla od 2 do 20 jen sudá (bez a s krokem) Suma čísel od 1 do 30, resp. suma čísel od X do Y Suma 10 různých čísel resp. libovolného počtu čísel Největší z 10 kladných čísel (pomocí dočasného maxima) Max a Min z celých čísel; počet bude znám předem (Max položte -32768 a Min položte +32767) Počet kladných a záporných čísel z daného počtu Součin pomocí součtu (A*B = A+A+A+…+A) Aritmetická řada (první prvek a diference) Součet aritmetické řady (první prvek, diference, počet prvků) Geometrická řada (první prvek a kvocient) Faktoriál Složené úrokování s pravidelnou měsíční úložkou
27
ALGORITMY CYKLŮ – s podmínečným opakování začátek
začátek
podmínka
instrukce
instrukce
podmínka
konec
Cyklus s podmínkou na začátku
konec
Cyklus s podmínkou na konci
Vytvoříte-li věcně správný algoritmus a podmínka bude uprostřed, pak upravit algoritmus – podmínka na začátku/konci – vždy to jde!!!
28
14
20.12.2011
ALGORITMY CYKLŮ – s podmínečným opakování Suma čísel, jejichž počet není předem znám začátek
začátek
začátek SUMA:=0
SUMA:=0
SUMA:=0 Čti: X
X:=0
Čti: X
X = -1
Čti: X
X <> -1 Zobraz: X
Zobraz: X
SUMA:=SUMA +X
SUMA:=SUMA +X
SUMA:=SUMA +X
konec
konec
Čti: X
test cyklu uprostřed
X <> -1
test cyklu na konci
Zobraz: X
konec
test cyklu na začátku 29
ÚKOLY Paralelní odpory (ukončení na dotaz) Suma libovolného počtu kladných čísel (konec při -1) Maximum z neznámého počtu čísel (konec při -1) Kolik čísel kladných a kolik záporných (konec při -1) NSD – největší společný dělitel (postupné odčítání) Součet číslic v čísle Převod z desítkové do binární soustavy Restaurace (konec při řetězci „platím“)
30
15
20.12.2011
TŘÍDÍCÍ ALGORITMY načtená data musí být před tříděním uložena v paměti či na disku – ke každé položce se několikrát vrací požadavky na algoritmus:
složitost nároky na paměť rychlost – počet porovnávání
typy algoritmu
Select Sort – třídění přímým výběrem Bubble Sort – třídění probubláváním Shake Sort – třídění přetřásáním 31
16
