Vysoká škola finanční a správní, o.p.s.
Úvod do programování
Studijní text pro posluchače 1. ročníku oboru Aplikovaná informatika
Pavel Töpfer
Praha 2013
Obsah
1. Úvod ....................................................................................................................................... 3
2. Algoritmy ............................................................................................................................... 5
3. Efektivita algoritmů................................................................................................................ 7
4. Struktura programu .............................................................................................................. 11
5. Základní příkazy................................................................................................................... 16
6. Další příkazy a datové typy.................................................................................................. 28
7. Procedury a funkce............................................................................................................... 34
8. Pole a jejich použití .............................................................................................................. 40
9. Znaky a znakové řetězce ...................................................................................................... 53
10. Záznamy a soubory ............................................................................................................ 59
11. Halda a heapsort ................................................................................................................. 68
12. Dodatky .............................................................................................................................. 72
2
1. Úvod
Tento text není ucelenou učebnicí pro předmět Úvod do programování, ale zahrnuje rozšířené
a doplněné prezentace k přednáškám a ukázkové programy s doprovodným vysvětlením,
jakým způsobem jsou programy navrženy a jak fungují. Práce se studijním textem vám tedy
v žádném případě nemůže nahradit účast na přednáškách a cvičeních, může vám však dobře
pomoci při průběžném studiu a při přípravě ke zkoušce.
Začneme vysvětlením, čím se vůbec budeme v předmětu Úvod do programování zabývat.
Programování není jenom psaní programů na počítači, jak si mnozí představují. To je ve
skutečnosti pouze jedna fáze celého procesu, který má řadu dalších složek. V předmětu
budeme studovat programování ze všech stránek a budeme se postupně věnovat následujícím
oblastem:
Algoritmizace - metody řešení úloh na počítači, vhodné postupy
Správnost algoritmu – konečnost výpočtu, ověření správnosti výsledků
Efektivita algoritmu (složitost algoritmu)
- časová (počet vykonaných operací)
- prostorová (paměť potřebná na uložení dat)
Programovací jazyk
- nástroj pro formální zápis algoritmu do podoby programu
- syntaxe (gramatika) a sémantika (význam) konstrukcí programovacího jazyka
Vývoj programu (programování jako „řemeslo“)
- práce ve vývojovém prostředí (editor, překladač, ladicí prostředky)
- návrh testovacích dat, proces ladění programu
Budeme využívat programovací jazyk Pascal, který byl navržen právě pro potřeby výuky
základů programování a pro tento účel je stále nejvhodnější. V praxi se sice tento
programovací jazyk již téměř nepoužívá, ale jeho principy, konstrukce a postupy jsou platné
stále a využívají je i současné moderní programovací jazyky, k jejichž výuce přejdeme
v dalším roce studia.
Jelikož Pascal není náš cílový programovací jazyk, ale pouze prostředek pro ovládnutí
základů programování, nebudeme se učit jeho technické detaily. Zaměříme se v něm na
obecné principy a prostředky, které mají trvalou platnost. Co konkrétně se z programovacího
jazyka naučíme:
- deklarace (proměnné, konstanty, typy, inicializované proměnné)
- jednoduché a strukturované datové typy (čísla, znaky, boolean, pole, záznamy, znakové
řetězce)
- jednoduché a strukturované příkazy (dosazovací příkaz, if, while, repeat, for, case, with)
- procedury a funkce (lokalita identifikátorů, způsoby předávání parametrů)
- práce s textovými soubory (včetně formátování výstupních dat)
- práce s datovými soubory (přímý přístup)
3
- unity, návrh a použití vlastních unit, standardní jednotka CRT
- generátor pseudonáhodných čísel
- základní parametry překladače (paměťová omezení, přepínače $R, $B, $Q, $I)
Pro psaní a ladění programů je nutná rovněž aktivní znalost integrovaného vývojového
prostředí. Můžete používat libovolné vývojové prostředí – klasické je například prostředí
Turbo Pascal (resp. Borland Pascal), z novějších volně šiřitelných nástrojů Free Pascal,
z modernějších nástrojů pak třeba DevPascal, Lazarus nebo Delphi. Ovládneme práci
s editorem, překlad programu, spuštění výpočtu, ladění programů a testování jejich správnosti
(tzn. krokování a trasování výpočtu, sledování hodnot proměnných atd.).
Jak jsme již uvedli, vedle znalosti programovacího jazyka a ovládnutí nástrojů pro ladění
programů potřebujeme znát a umět správně využívat také základní algoritmy, datové
struktury a programovací techniky. Naučíme se následující:
- dělitelnost čísel, Eukleidův algoritmus
- test prvočíselnosti, Eratosthenovo síto
- Hornerovo schéma
- rozklad celého čísla na cifry, poziční číselné soustavy
- algoritmy vyhledávání v poli (sekvenční, binární, zarážka)
- jednoduché třídění v poli (přímé metody)
- práce s maticemi (základní operace)
- implementace zásobníku a fronty v poli
- aritmetika s vyšší přesností („dlouhá čísla“ v poli)
- halda a haldové operace, heapsort
- práce se znakovými řetězci (vyhledávání, záměny, rozklad)
- operace se soubory, vnější třídění.
Naši úvodní kapitolu uzavřeme shrnutím, co všechno obnáší práce programátora a jak vlastně
probíhá práce na vývoji jednoho programu:
1. algoritmus
programovací jazyk
2. program
textový editor
3. zdrojový text programu
Překladač
4.a) syntaktická chyba
zpět na opravu zdrojového textu
4.b) bez syntaktických chyb → přeložený program
spustit se vstupními daty
5.a) běhová chyba (příp. zacyklení výpočtu)
ladicí prostředky, testování, zpět na opravu zdrojového textu
5.b) bez běhové chyby
posouzení výsledků
6.a) podezřelé výsledky → logická chyba
ladicí prostředky, testování, zpět na opravu zdrojového textu
6.b) dobré výsledky
ověřit správnost opakovaně pro různá testovací vstupní data
4
2. Algoritmy
Jeden daný problém lze mnohdy řešit různými postupy – algoritmy. Ty se mohou lišit
z různých hledisek, například rychlostí výpočtu, paměťovými nároky či obtížností takový
algoritmus naprogramovat a odladit. Nejvhodnější algoritmus zvolíme podle toho, jakému
kritériu při řešení daného problému dáváme přednost. Ukážeme si příklad jednoho
konkrétního problému a několika algoritmů na jeho řešení.
Nalezení největšího společného dělitele dvou přirozených čísel
Jsou dána dvě kladná celá čísla X, Y. Máme určit hodnotu jejich největšího společného
dělitele NSD(X,Y).
Možné algoritmy:
1. Nechť X < Y. Hodnota NSD(X,Y) je přímo podle definice rovna největšímu z celých čísel
od 1 do X, které je dělitelem obou čísel X a Y. Budeme tedy postupně zkoušet jednotlivá celá
čísla, nejlépe v pořadí od X dolů k 1, až do nalezení prvního takového společného dělitele
čísel X a Y.
2. Určíme prvočíselné rozklady čísel X a Y. Jejich maximální společná část určuje hodnotu
NSD(X,Y)
Například 396 = 2.2.3.3.11, 324 = 2.2.3.3.3.3 → NSD(396, 324) = 2.2.3.3 = 36
3. Eukleidův algoritmus
Platí následující rekurzivní vztahy:
když X < Y pak NSD(X,Y) = NSD(X,Y-X)
když X > Y pak NSD(X,Y) = NSD(X-Y,Y)
když X = Y pak NSD(X,Y) = X
Jejich postupnou aplikací snadno získáme požadovaný výsledek. Příklad: NSD(396,324) =
NSD(72,324) = NSD(72,252) = NSD(72,180) = NSD(72,108) = NSD(72,36) = NSD(36,36) =
36
Algoritmus zapíšeme schematicky takto:
dokud X ≠ Y dělej
od většího z čísel X, Y odečti menší z čísel X, Y
po skončení předchozího výpočtu bude platit X = Y
a tato hodnota je zároveň hledaným výsledkem
Správnost Eukleidova algoritmu
1. Konečnost
- na začátku výpočtu i stále v jeho průběhu je X>0, Y>0
- v každém kroku výpočtu se hodnota X+Y sníží alespoň o 1
→ nejpozději po X+Y krocích výpočet skončí, je tedy konečný
5
2. Parciální (částečná) správnost
- pro X = Y zjevně platí NSD(X,Y) = X
- ukážeme, že pro X > Y platí NSD(X,Y) = NSD(X-Y,Y):
Nechť N=NSD(X,Y), tedy N dělí X a zároveň N dělí Y. Proto také N dělí X-Y a je tedy N
společným dělitelem X-Y a Y. Pokud by neplatilo, že N=NSD(X-Y,Y), musí existovat A>1
tak, že N.A=NSD(X-Y,Y). Tedy N.A dělí X-Y i Y, takže N.A dělí i jejich součet, což je X.
Jelikož N.A dělí Y a zároveň N.A dělí X, je N.A společným dělitelem X, Y, což je spor s tím,
že N=NSD(X,Y). Proto N=NSD(X-Y,Y).
6
3. Efektivita algoritmů
- nazýváme také složitost algoritmů
- časová
počet vykonaných operací
→ rychlost výpočtu programu
- prostorová (paměťová)
velikost datových struktur využívaných algoritmem
→ paměť potřebná na uložení dat při výpočtu programu
Časová a prostorová složitost slouží jako kritéria pro hodnocení kvality algoritmů a programů
(příp. praktické použitelnosti programů). Obě kritéria mohou mířit proti sobě, nelze současně
optimalizovat paměť i čas. Musíme tedy zvolit, čemu dáme přednost (dnes to obvykle bývá
čas, paměti je pro většinu aplikací relativní dostatek).
Složitost algoritmu je funkce vyjadřující závislost počtu vykonaných operací (resp. velikosti
potřebné paměti) na velikosti vstupních dat. Jako velikost vstupních dat obvykle stačí
uvažovat např. počet zpracovaných čísel, nikoliv konkrétní hodnoty (jedná-li se o hodnoty
„standardní“ velikosti). Obecně by se musela uvažovat velikost vstupních dat v bitech.
Funkce časové a prostorové složitosti jsou většinou rostoucí (výpočet s většími daty bývá
zpravidla delší a paměťově náročnější).
Pro jednodušší vyjadřování budeme nadále mluvit pouze o časové složitosti, všechna uvedená
tvrzení ovšem platí analogicky i pro složitost prostorovou.
Přesné vyjádření funkce časové složitosti (např. 3N 2 + 2N – 4) je jednak obtížné, jednak
většinou zbytečné. Podstatná je řádová rychlost růstu této funkce pro rostoucí N. Zanedbáme
pomaleji rostoucí členy a konstanty → asymptotická časová složitost O(N 2).
Při vyjadřování asymptotické složitosti algoritmu používáme symbol „velké O“. Toto
vyjádření má přesnou matematickou definici:
f = O(g) ⇔ ∃ c ∃ n0 ∀ n > n0 : f(n) < c.g(n)
tzn. funkce f se dá shora odhadnout funkcí g (až na multiplikativní konstantu a pro dostatečně
velká n).
Opačný odhad zdola vyjadřujeme symbolem „velké omega“:
f = Ω(g)
Oboustranný odhad, který přesně charakterizuje asymptotickou rychlost růstu funkce,
vyjadřuje symbol „velké theta“:
f = Θ(g) ⇔ f = O(g) & f = Ω(g)
Typické asymptotické časové složitosti algoritmů:
O(1), O(log N), O(N), O(N.log N), O(N 2), O(N 3), …, O(2N)
7
Při řešení problému hledáme obvykle algoritmus s co nejmenší asymptotickou časovou
složitostí, tedy co nejrychlejší pro velká N. Pro malá N může být takový algoritmus třeba i
horší než nějaký jiný postup, ale to nevadí, doba výpočtu je pro malá N dostatečně krátká.
Algoritmy dělíme podle jejich asymptotické časové složitosti na
- polynomiální – asymptotická časová složitost se u nich dá omezit polynomem v N,
jsou obvykle dobře použitelné i pro velké hodnoty N
- exponenciální – asymptotická časová složitost je exponenciální funkce vzhledem k N,
pro větší hodnoty N jsou časově nezvládnutelné,
jsou reálně použitelné jen v případě, že vstupní data budou vždy malá.
Příklad složitosti algoritmu s exponenciální časovou složitostí
Máme N-tici reálných čísel a1, a2, …, aN. Vyberte takovou podmnožinu ze zadané N-tice
čísel, jejíž součet je roven dané hodnotě C. (Lze interpretovat jako výběr skupiny předmětů
daných hmotností – tzv. problém batohu.)
Pokud by čísla a1, a2, …, aN byla celá z předem známého rozmezí přípustných hodnot, úlohu
bychom uměli řešit v polynomiálním čase metodou dynamického programování. V obecném
případě ale neznáme lepší algoritmus než postupně zkoušet všechny možnosti výběru. Ze
zadaných N čísel lze vybrat různé podmnožiny 2N způsoby, takže takové řešení má
exponenciální časovou složitost O(2N).
Provedeme orientační časový odhad doby výpočtu exponenciálního algoritmu.
Předpokládejme, že ke zpracování vstupních dat velikosti N algoritmus vykoná 2N operací.
Dále předpokládejme rychlost výpočtu počítače 109 operací za sekundu (procesory dnešních
osobních počítačů používají taktování řádově v GHz).
N
20
30
40
50
60
70
80
90
100
doba výpočtu
1 ms
1s
17 min
11 dní
31 let
3.104 let
3.107 let
3.1010 let
3.1013 let
Vidíme, že pro vyšší hodnoty N (cca nad 50) je algoritmus s exponenciální časovou složitostí
prakticky nepoužitelný. Nepomůže nám ani rychlejší počítač.
Příklady problémů s různými algoritmy polynomiální složitosti
Vyhledání údaje v seznamu
1. sekvenční průchod daty velikosti N → časová složitost O(N)
8
2. půlení intervalů (binární vyhledávání)
- data musí být uspořádaná
- vždy porovnat hledanou hodnotu s prostředním prvkem zkoumaného úseku, nepotřebnou
polovinu zkoumaného úseku „zahodit“
- postupně dostáváme úseky délky N, N/2, N/4, N/8, …, 1
- po K krocích zbývá úsek velikosti N/2K
- hledáme K takové, aby N/2K = 1
→ počet provedených půlení K = log2N , tedy časová složitost algoritmu je O(log N)
Příklad: pražský telefonní seznam bytových stanic
- cca 430 000 jmen (v době největšího rozmachu pevných linek v roce 1995)
- rychlost hledajícího člověka 1 jméno za sekundu
- sekvenční hledání: 5 dní a nocí x binární hledání: 20 sekund
Třídění dat (řazení) – seřadit N údajů podle velikosti
1. přímé metody, např. přímý výběr (opakovaný výběr minima)
→ časová složitost O(N 2)
2. lepší algoritmy, např. quicksort (metoda „rozděl a panuj“)
→ průměrná časová složitost O(N. log N)
… popis algoritmů i odvození jejich časové složitosti bude později
Příklad: při rychlost výpočtu 1 porovnání dat za 1 mikrosekundu
N
100
100 000
algoritmus O(N 2)
0.01 s
2.8 hod
algoritmus O(N. log N)
0.6 ms
1.7 s
Pozorování:
- pro malá N není rozdíl doby výpočtu obou algoritmů podstatný
- pro velká N může být zajímavý, i když O(N 2) je ještě vcelku příznivá složitost algoritmu.
Složitost algoritmu v různých případech
Pro každá vstupní data velikosti N nemusí trvat výpočet stejně dlouho. Rozdíl může být buď
jen v konstantě, nebo i v asymptotické časové složitosti.
Časová složitost algoritmu v nejhorším případě
= maximální počet operací vykonaných algoritmem pro nějaká data velikosti N
→ nejčastěji používaná pro hodnocení algoritmů
Časová složitost algoritmu v nejlepším případě
= minimální počet operací vykonaných algoritmem pro nějaká data velikosti N
→ prakticky se nepoužívá
Časová složitost algoritmu v průměrném případě
= průměrný (očekávaný) počet operací vykonaných algoritmem pro data velikosti N (průměr
pro všechna možná vstupní data velikosti N)
→ dobře charakterizuje kvalitu algoritmu, ale je obtížné odvodit ji
9
Příklady:
1. Nalézt maximum a druhé maximum z daného seznamu N různých čísel
- pokud nejprve najdeme maximum (k tomu je zapotřebí vykonat N-1 porovnání), ze seznamu
ho vyřadíme a poté najdeme maximum ve zbylém seznamu (N-2 porovnání), provedeme pro
každá vstupní data stejný počet porovnání 2N-3
- pokud seznam procházíme jen jednou a průběžně si udržujeme dosavadní nalezené
maximum a dosavadní druhé maximum, provedeme v nejhorším případě stejný počet 2N-3
porovnání (jedno porovnání na první dvě čísla a pak vždy dvě porovnání pro každé
z následujících N-2 čísel)
- pokud seznam procházíme jen jednou a průběžně si udržujeme dosavadní nalezené
maximum a dosavadní druhé maximum, provedeme v nejlepším případě pouze N-1 porovnání
(jedno porovnání na první dvě čísla a pak vždy stačí už jenom jediné porovnání pro každé
z následujících N-2 čísel, když je to pokaždé nové maximum)
- tento druhý algoritmus má tedy odlišnou časovou složitost v nejlepším a v nejhorším
případě, v všech případech má ovšem stejnou asymptotickou časovou složitost O(N)
2. Seřadit daných N čísel podle velikosti – algoritmus quicksort
- quicksort je nejrychlejší známý třídicí algoritmus, který úlohu řeší s průměrnou
asymptotickou časovou složitostí O(N. log N), rovněž složitost quicksortu v nejlepším případě
je O(N. log N)
- v nejhorším případě má quicksort asymptotickou časovou složitost O(N 2)
… algoritmus si ukážeme později
Složitost problému
- složitost nejlepšího algoritmu (z hlediska časové složitosti), kterým lze řešit daný problém
Nelze odvodit ze složitosti nějakého konkrétního algoritmu ani třeba všech běžně známých
algoritmů, charakterizuje problém obecně (jaký nejlepší algoritmus řešící problém může
v principu existovat)
→ odvození je obtížné, pro řadu problémů neznáme.
Příklady:
1. Nalézt maximum z daného seznamu N čísel → časová složitost problému O(N)
- existuje algoritmus s časovou složitostí O(N) … triviální
- nemůže existovat algoritmus s lepší časovou složitostí … maximem může být kterékoliv z N
čísel, takže na každé se musí algoritmus podívat
2. Seřadit daných N čísel podle velikosti (problém třídění)
→ časová složitost problému O(N. log N)
- existuje algoritmus, který úlohu řeší s časovou složitostí O(N. log N) … např. heapsort
- nemůže existovat algoritmus s lepší časovou složitostí
… oboje si ukážeme později
10
4. Struktura programu
Programovací jazyk
- norma
- implementace
Pascal (1974)
Turbo Pascal, Borland Pascal
FreePascal
Object Pascal (Delphi)
řada dalších implementací
Odlišnosti implementace od normy
- odchylky např. TP:
- nepovinná hlavička programu
- odlišná práce se soubory
- parametr for-cyklu, příkaz case
- rozšíření např. TP:
- standardní procedury a funkce
- znakové řetězce (typ string)
- modularita (unity)
- objekty
Syntaxe jazyka = pravidla zápisu korektních programů („gramatika“)
Sémantika jazyka = význam syntakticky správných konstrukcí, resp. programů („co zápis
znamená“)
Struktura programu v Pascalu
hlavička
- v některých implementacích (např. v TP) je nepovinná,
pokud ale je uvedena, kontroluje se její syntaktická správnost
program Soucet;
deklarace
- popis a pojmenování všech prostředků používaných dále v programu
= proměnné, konstanty, typy, návěstí, procedury a funkce
např. dvě celočíselné proměnné:
var A, B: integer;
tělo
- zápis algoritmu (= posloupnost příkazů)
begin
read(A); read(B);
write(A+B)
end.
Hlavička, jednotlivé deklarace i příkazy se oddělují středníkem (znakem ;).
Klíčová slova (v tisku zpravidla tučně, v rukopisu podtržená)
= speciální víceznakové symboly s vyhrazeným významem,
anglická slova nebo zkratky příslušného významu.
11
Proměnná
= paměťové místo pro uložení hodnoty
- jméno … jednoznačné pojmenování pomocí identifikátoru
- typ … jaké hodnoty může uchovávat (určuje velikost přidělené paměti)
Deklarace proměnných – v Pascalu povinná
(v některých jazycích ne – nebezpečné!)
syntaxe:
var Jméno: Typ;
Jm1, Jm2, Jm3: Typ;
… více proměnných téhož typu
Při deklaraci více proměnných v programu se nemusí (ale může) klíčové slovo var opakovat,
jdou-li deklarace proměnných hned po sobě. Pokud je mezi nimi deklarován nějaký jiný
prostředek (např. typ, konstanta, procedura), musí se var znovu uvést na začátku každého
úseku deklarací proměnných.
Identifikátor
= způsob pojmenování jakýchkoliv objektů používaných v programu
(název programu, jména proměnných i jiných deklarovaných prostředků)
- tvořen písmeny anglické abecedy a číslicemi
- nesmí začínat číslicí
např.: Soucet, x1, alfa
- v TP navíc znak _ („podtržítko“)
umožňuje používat „víceslovné názvy“, např.: Pocet_Prvku
- nerozlišuje malá a velká písmena
(v identifikátoru a = A, na rozdíl od jazyků C, Java apod., kde to jsou různé znaky)
tedy identifikátory alfa = ALFA = Alfa (lze v programu i střídat … nepřehledné!)
lze používat „velbloudí notaci“ PocetKamenuNaSachovnici
- implementací může být omezena maximální délka (je ale vždy dostatečně velká).
Doporučení:
- používat mnemotechnické identifikátory – název proměnné napovídá o jejím významu a
účelu
- zavést si pevný styl používání malých/velkých písmen
Typ
– určuje, kolik se pro proměnnou vyhradí místa v paměti
a jakým způsobem se proměnná může používat v programu
- jednoduchý – proměnná příslušného typu slouží k uložení jedné hodnoty
v Pascalu (resp. Turbo Pascalu) jsou připraveny standardní datové typy (a jejich alternativy
lišící se povoleným rozsahem hodnot)
celé číslo
integer (byte, word, shortint, longint)
desetinné číslo
real
(single, double, extended)
logická hodnota
boolean
znak
char
12
- strukturovaný – sestaven z více složek
nutno předem specifikovat počet a typ složek pomocí definice typu s využitím vyhrazených
klíčových slov
pole
array
záznam
record
znakový řetězec
string
množina
set
Celočíselné typy v TP
shortint
1B se znaménkem
integer
2B se znaménkem
longint
4B se znaménkem
byte
1B bez znaménka
word
2B bez znaménka
rozsah hodnot
rozsah hodnot
rozsah hodnot
rozsah hodnot
rozsah hodnot
-128..127
-32768..32767
-2147483648..2147483647
0..255
0..65535
Základní reálný typ v Pascalu
real
6B
11-12 platných cifer
rozsah hodnot E-39..E38
Dodatečné reálné typy v TP
single
4B
7-8 platných cifer
double
8B
15-16 platných cifer
extended
10B 19-20 platných cifer
rozsah hodnot E-48..E38
rozsah hodnot E-324..E308
rozsah hodnot E-4932..E4932
Poznámka: Jak vypadají čísla ve světě kolem nás
1 AU (astronomická jednotka)
= střední vzdálenost Země – Slunce
1,495 . 1011 m
1 l.y. (světelný rok)
9,46 . 1015 m
vzdálenost hvězd – cca 10-15 l.y. (Proxima Centauri 4,27 l.y.)
hmotnost Slunce
1,993 . 1020 kg
velikost atomu
hmotnost protonu
hmotnost elektronu
elementární náboj
řádově 10-10 m
1,672 . 10-27 kg
9,109 . 10-31 kg
1,602 . 10-19 C
Planckova konstanta (E=h.ν)
Avogadrova konstanta (počet částic v 1 molu)
h = 6,625 . 10-34 Js
NA = 6,022 . 1023 mol-1
→ přípustný rozsah hodnot standardního datového typu real plně postačuje k vyjádření všech
běžných hodnot popisujících náš reálný svět (mikrosvět i makrosvět) v obvyklých fyzikálních
jednotkách
13
Zápis programu v Pascalu
Fyzicky: textový soubor = posloupnost znaků (píšeme v textovém editoru)
Logicky: posloupnost lexikálních atomů (logických elementů, dále nedělitelných)
- konstanty
15
-2.97
3.456E-4
’Praha’
- identifikátory
A
Soucet
PocetCisel
x1
- klíčová slova
var
begin
program
array
- speciální znaky
+
:
<
;
- dvojznaky
:=
<=
<>
..
- komentáře
{libovolný text}
(*případně takto*)
Oddělení sousedních lexikálních atomů: mezera, „nový řádek“ (Enter)
- musí oddělit sousedící konstanty, identifikátory a klíčová slova
- nesmí být uvnitř lexikálního atomu (v komentáři ovšem ano)
- jinde být může a nemusí (lze psát „A+1“ i „A + 1“)
- kde smí být, může jich být libovolný počet (v libovolné kombinaci)
- kde smí být, může být komentář
- není pevná řádková struktura (neplatí princip „co příkaz, to řádek“)
Doporučení:
- jednotlivé deklarace a příkazy psát na samostatné řádky
- používat indentaci
(= odsazování řádků od levého okraje podle logického zanoření příkazových struktur)
- používat komentáře
(význam proměnných, co dělá která procedura a funkce, co dělá která část programu)
- zavést si vlastní styl zápisu programu a dodržovat ho
(umístění mezer, odřádkování, volné řádky, úprava komentářů, …)
Nic z toho není povinné, překladač úpravu programu ignoruje. Vede to ale k významnému
zvýšení čitelnosti zdrojového kódu pro programátora (pro autora programu samotného i pro
případné další „čtenáře“).
Příklad programu: spočítat plochu kruhu daného poloměru
program PlochaKruhu;
{program počítá plochu kruhu daného poloměru}
var R, P: real;
{R = poloměr kruhu, P = výsledná plocha}
begin
read(R);
P := 3.14159265 * R * R;
write(P)
end.
14
Definice konstanty
- pojmenování konstanty identifikátorem
- uvádí se v oblasti deklarací
- syntaxe:
const Jméno = Hodnota;
- typ konstanty je automaticky odvozen z uvedené hodnoty
- hodnotu konstanty nelze při výpočtu měnit (nelze do ní dosazovat)
Důvody použití:
- opakovaný výskyt téže „ošklivé“ hodnoty v programu
- možnost snadné budoucí změny na jediném místě v programu
Příklad: úprava programu na výpočet plochy kruhu
program PlochaKruhu;
{program počítá plochu kruhu daného poloměru}
const Pi = 3.14159265;
{DEFINICE KONSTANTY}
var R, P: real;
{R = poloměr kruhu, P = výsledná plocha}
begin
read(R);
P := Pi * R * R;
write(P)
end.
Předdefinované číselné konstanty
maxint
= nejvyšší možná hodnota proměnné typu integer
(v TP má hodnotu 32767, jinde může být jiná)
Pi
= Ludolfovo číslo π=3.14159265358979
(není v normě jazyka Pascal, je ve většině implementací, např. v TP)
15
5. Základní příkazy
Přehled příkazů jazyka Pascal
- jednoduché
- dosazovací příkaz (přiřazovací)
- volání procedury
- příkaz skoku (goto)
používá se jen výjimečně
- strukturované
- složený příkaz (begin – end)
- podmíněný příkaz (if, case)
- cyklus (while, repeat, for)
- vnoření do záznamu (with)
specialita Pascalu, příliš se nepoužívá
Strukturovaný příkaz je konstrukce, která v sobě obsahuje jeden nebo více dalších příkazů,
z nichž každý je buď jednoduchý, nebo opět strukturovaný → strukturované programování.
Dosazovací příkaz
Syntaxe:
Sémantika:
Proměnná := Výraz
vyhodnotí se výraz, hodnota se vloží do proměnné
(dosavadní hodnota proměnné se tím ztratí)
Použití:
A := 5;
A := A+1;
A := B;
{proměnná A nabude hodnoty 5}
{hodnota proměnné A se zvýší o 1}
{do A se zkopíruje hodnota proměnné B,
přitom hodnota proměnné B se nezmění}
Příklad: výměna hodnot dvou proměnných A, B
- k provedení výměny je nutno použít třetí pomocnou proměnnou C
C := A; A := B; B := C;
- pozor na správné pořadí uvedených příkazů
Výraz
- syntaxe i sémantika podobné jako v matematice
- obsahuje proměnné, konstanty, operátory, závorky, volání funkcí
- všechny operátory nutno zapisovat – nelze např. vynechat znak násobení
- argumenty funkcí vždy v závorce – nelze např. psát sin x, musí být sin(x)
- typ výsledné hodnoty je určen typem použitých proměnných, konstant, operátorů a funkcí
- závorky pouze kulaté ( ), libovolně hluboko vnořené do sebe
16
Vyhodnocování výrazu (pořadí provádění operátorů):
1. podle uzávorkování
2. podle priorit operátorů (násobení/dělení dříve než sčítání/odčítání)
3. operátory téže priority zleva doprava
Příklady
správný zápis výrazu:
(y + (sin(2*x) + 1)*2)/3
správný postup vyhodnocení: 1 + 3/2 * 5 = 8.5
(1+3)/2 * 5 = 10
1 + 3/(2 * 5) = 1.3
Celočíselný výraz
- konstanty a proměnné pouze typu integer (příp. jiných celočíselných typů)
- aritmetické operátory +, -, *, div, mod (celočíselné dělení a zbytek)
- standardní funkce
abs(x)
absolutní hodnota z x
sqr(x)
druhá mocnina x
Definice operátoru mod:
(X div Y) * Y + (X mod Y) = X
Pozor na záporné argumenty (způsob počítání může záviset na implementaci).
Příklad:
7 div 3 = 2
-7 div 3 = -2
7 div (-3) = -2
7 mod 3 = 1
-7 mod 3 = -1
7 mod (-3) = 1
Použití:
Y := X mod 10
→ do Y se vloží hodnota poslední cifry čísla X
X := X div 10
→ z čísla X se odebere jeho poslední cifra
test, zda platí X mod 3 = 0
→ test, zda hodnota X je dělitelná třemi
Příklad: Spočítejte ciferný součet zadaného kladného celého čísla
Zápis algoritmu zčásti slovně:
načti vstupní hodnotu do proměnné X;
Y := 0;
dokud X není rovno nule, opakovaně prováděj ( Y := Y + X mod 10; X := X div 10 );
vypiš jako výsledek hodnotu proměnné Y
Totéž jako program v Pascalu (ještě neznáme cyklus while):
program CifernySoucet;
var X, Y: integer;
begin
read(X);
Y := 0;
while X <> 0 do
begin Y := Y + X mod 10; X := X div 10 end;
writeln(Y)
end.
17
Výraz typu real
- konstanty a proměnné typu real (příp. i celočíselné – provádí se automatická konverze do
typu real)
- aritmetické operátory +, -, *, /
- standardní funkce
abs(x)
absolutní hodnota z x
sqr(x)
druhá mocnina x
sqrt(x)
druhá odmocnina z x
ln(x)
přirozený logaritmus z x
exp(x)
ex
sin(x) cos(x) arctan(x)
goniometrické funkce
Výraz typu integer lze dosadit do proměnné typu real (provádí se automatická konverze),
obráceně nikoliv.
Výraz 10/5 má sice hodnotu 2, ale je typu real (provádí se dělení v reálné aritmetice!).
Převod výrazu typu real na typ integer: konverzní funkce
round(x)
zaokrouhlení
round(3.8) = 4
trunc(x)
oříznutí desetinné části
trunc(3.8) = 3
Volání procedury
- má postavení jednoduchého příkazu
- lze volat standardní proceduru jazyka Pascal,
nebo proceduru vlastní, deklarovanou v programu
Syntaxe:
Sémantika:
JménoProcedury(Parametry)
vykoná se algoritmus popsaný v proceduře
Průběh výpočtu: v místě volání procedury se v přeloženém kódu programu vykoná odskok do
kódu procedury a po ukončení procedury návrat do programu za místo volání (návratová
adresa je vhodným způsobem uschována).
Prozatím známe standardní procedury pro vstup a výstup dat v podobě:
read(A);
přečte ze standardního vstupu (tj. z klávesnice) jednu hodnotu
a uloží ji do proměnné A
write(A);
vypíše na standardní výstup (tj. na obrazovku) hodnotu výrazu A
Příklad jiných standardních procedur:
procedury pro zvýšení / snížení hodnoty proměnné
inc(A)
znamená A:=A+1
dec(A)
znamená A:=A-1
inc(A, X)
znamená A:=A+X
dec(A, X)
znamená A:=A-X
V uvedených příkazech A je proměnná typu integer, X je výraz typu integer.
Procedury nejsou v normě jazyka Pascal, má je např. TP a jiné implementace.
18
Podmíněný příkaz
Používá se, když chceme některý příkaz provést pouze za předpokladu, že je splněná jistá
podmínka, nebo když chceme na základě vyhodnocení podmínky provést buď jeden, nebo
druhý příkaz. Má dvě základní podoby – neúplný a úplný podmíněný příkaz.
Syntaxe:
if Podmínka then Příkaz
if Podmínka then Příkaz1 else Příkaz2
Sémantika:
Je-li „Podmínka“ splněna, provede se „Příkaz“, není-li splněna, „Příkaz“ se neprovede.
Je-li „Podmínka“ splněna, provede se „Příkaz1“, není-li splněna, provede se „Příkaz2“.
Jednoduchá podmínka = relace:
Výraz1
relační operátor Výraz2
= < > <= >= <>
Příklad:
if A > 0 then A := A-1
if A > 0 then A := A-1 else A := A+1
Při volbě prováděného příkazu z více možností můžeme podmíněné příkazy řetězit
(příkaz uvedený za else je opět podmíněný):
if A=1 then …
else if A=2 then …
else if A=3 then …
else …
Sémantika vnořených podmíněných příkazů
- když příkaz uvedený za then je opět podmíněný
Pokud použijeme úplný podmíněný příkaz, žádný problém nevzniká.
Jestliže například zapíšeme:
if A > 0 then
if B = C then A := A-1 else A := 0
else A := 1
potom sémantiku tohoto příkazu můžeme schématicky vyjádřit pomocí uzávorkování
if A > 0 then (if B = C then A := A-1 else A := 0) else A := 1
Ty závorky se ovšem v Pascalu samozřejmě nepíšou!
Pokud použijeme neúplnÝ podmíněný příkaz, například:
if A > 0 then if B = C then A := A-1 else A := 0
může vniknout nejasnost v chápání jeho sémantiky – ke které ze dvou podmínek uvedených
v příkazu se váže závěrečná klauzule else?
Jsou teoreticky dvě možnosti, z nichž první je správná a druhá chybná:
if A > 0 then (if B = C then A := A-1 else A := 0)
SPRÁVNĚ
if A > 0 then (if B = C then A := A-1) else A := 0
ŠPATNĚ
Závorky opět do příkazů v Pascalu nepíšeme, jenom zde znázorňují chápání sémantiky!
19
Co když potřebujeme dosáhnout toho druhého významu?
Co když v podmínce potřebujeme provést více příkazů?
Použijeme složený příkaz.
Složený příkaz
= „příkazové závorky“
Složený příkaz spojuje několik příkazů (jednoduchých nebo strukturovaných) do jednoho
příkazu.
Syntaxe:
begin Příkaz1; Příkaz2; …; PříkazN end
Sémantika:
Příkazy se vykonávají postupně v tom pořadí, jak jsou uvedeny ve složeném příkazu.
Příklad:
if A > 0 then
begin A := A-1; B := 100 end
else
begin A := A+1; B := 200 end
Poznámka k syntaxi: před else není středník!
Řešení problému se sémantikou vnořených podmíněných příkazů: jak dosáhnout sémantiky
if A > 0 then (if B = C then A := A-1) else A := 0
Použijeme příkazové závorky begin – end, mezi které uzavřeme vnořený příkaz
(i když je jenom jeden):
if A > 0 then
begin if B = C then A := A-1 end
else A := 0
Cyklus
Konstrukce sloužící k opakovanému provádění uvedeného příkazu.
Programovací jazyk Pascal obsahuje tři typy cyklů – while, repeat, for.
Syntaxe cyklu while:
while Podmínka do Příkaz
Sémantika:
- dokud je podmínka splněna, příkaz v těle cyklu se opakovaně provádí
- cyklus s podmínkou na začátku, nejprve se vyhodnocuje podmínka
→ příkaz v těle cyklu se nemusí provést ani jednou
- pokud chceme provádět v těle cyklu více akcí, použijeme složený příkaz (velmi časté)
20
Syntaxe cyklu repeat:
repeat Příkaz1; Příkaz2; …; PříkazN until Podmínka
Sémantika:
- příkazy v těle cyklu se opakují až do splnění podmínky
(tzn. cyklus se provádí, dokud podmínka NENÍ splněna – opačně než u cyklu while!)
- cyklus s podmínkou na konci, nejprve se provádí příkaz v těle cyklu
→ příkaz v těle cyklu se vždy provede aspoň jednou
- pokud chceme provádět v těle cyklu více akcí, můžeme je zapsat přímo
(nepotřebujeme použít složený příkaz)
Příklady použití cyklu:
1. Ciferný součet daného celého čísla – postup byl vysvětlen dříve, program byl uveden
2. Eukleidův algoritmus – postup byl vysvětlen a dokázán dříve, nyní si ukážeme zápis tohoto
algoritmu v Pascalu. Při implementaci použijeme cyklus while:
program Eukleid1;
{určení největšího společného dělitele dvou kladných celých
čísel Eukleidovým algoritmem – verze s odčítáním}
var X, Y: integer;
begin
write('Zadejte dvě kladná celá čísla: ');
readln(X, Y);
while X <> Y do
if X > Y then
X:= X-Y
else
Y:= Y-X;
writeln('Největší společný dělitel: ', X)
end.
Uvedený algoritmus je založen postupném odčítání menšího z uvažovaných čísel od většího.
Je-li rozdíl mezi oběma čísly velký, můžeme výpočet urychlit tím, že místo opakovaného
odčítání použijeme operaci modulo (rozmyslete si!). To nás vede ke druhému způsobu řešení,
který dává shodné výsledky, ale pro většinu vstupních dat pracuje rychleji. Při implementaci
použijeme cyklus repeat:
program Eukleid2;
{určení největšího společného dělitele dvou kladných celých
čísel Eukleidovým algoritmem – verze s modulem}
var X, Y, Z: integer;
begin
write('Zadejte dvě kladná celá čísla: ');
readln(X, Y);
repeat
Z:=X mod Y;
X:=Y;
21
Y:=Z
until Y=0;
writeln('Největší společný dělitel: ', X)
end.
3. Prvočíselný rozklad – chceme určit prvočíselný rozklad zadaného kladného celého čísla.
Číslo postupně zkoušíme dělit 2, 3, 4, 5, … Každým dělitel použijeme tolikrát, dokud to jde,
tzn. dokud je číslo beze zbytku dělitelné. Všechny použité dělitele rovnou vypisujeme.
Výpočet skončí ve chvíli, když z čísla zbude jen poslední 1.
program Prvociselny_Rozklad;
{určení prvočíselného rozkladu}
var N: integer;
{zkoumané číslo}
D: integer;
{dělitel}
begin
write('Zkoumané kladné celé číslo větší než 1: ');
readln(N);
write('Prvočíselný rozklad: ');
while N mod 2 = 0 do
begin
N:=N div 2;
write(2, ' ')
end;
D:=3;
{první lichý dělitel}
while N > 1 do
begin
while N mod D = 0 do
begin
N:=N div D;
write(D, ' ')
end;
D:=D+2
{další možný dělitel}
end;
writeln
end.
Podmínka
- jednoduchá – relace < > = <= >= <> mezi dvěma výrazy
- složená – sestavená z více jednoduchých podmínek pomocí logických spojek
not
negace
and konjunkce
or
disjunkce (alternativa) … nevylučující
xor
vylučující disjunkce … eXclusive OR
(nonekvivalence, negace ekvivalence)
22
Příklady:
if (A>=0) and (A<10) then …
while not ((X=0) or (Y=0)) do …
while (X<>0) and (Y<>0) do …
{A je nezáporné jednociferné}
{oboje znamená totéž}
Jednotlivé relace obsažené ve složené podmínce musí být uzavřeny v závorkách (relační
operátory mají nižší prioritu než logické spojky)!
Další kulaté závorky (s libovolnou úrovní vnoření do sebe) určují pořadí vyhodnocování
složené podmínky.
Kde nejsou závorky, rozhodují priority logických spojek:
1. not
2. and
3. or, xor
Příklad:
while not (X=0) or (Y=0) do …
while (not (X=0)) or (Y=0) do …
{znamená totéž jako:}
Doporučení: raději psát více závorek, i tam, kde to není nezbytné (prevence chyb).
Příklad: Test prvočíselnosti – určit, zda je zkoumané číslo N prvočíslem
Možné postupy řešení:
1. zkusit všechny dělitele od 2 do N-1
→ časová složitost O(N) – cca N testů
2. stačí zkoušet všechny dělitele od 2 do N/2 (větší dělitel jistě neexistuje)
→ časová složitost opět O(N) – cca N/2 testů, tedy o něco lepší
3. stačí zkoušet všechny dělitele od 2 do √N
(má-li N vlastního dělitele, musí mít i dělitele z tohoto intervalu)
→ časová složitost O(√
√N) – cca √N testů, asymptoticky lepší
4. stačí zkoušet dělitele od 2 do √N, a to do nalezení prvního dělitele
→ asymptotická časová složitost opět O(√
√N),
většinou se ale vykoná o dost méně testů.
Zvolíme poslední uvedený algoritmus, který
- v nejhorším případě vykoná √N testů → časová složitost O(√
√N)
- v nejlepším případě stačí pouze jeden test → časová složitost O(1), tzn. konstantní
program Test_Prvociselnosti_1;
{test prvočíselnosti – první verze}
var N: integer;
{zkoumané číslo}
D: integer;
{dělitel}
Prv: byte;
{příznak, zda je N prvočíslo}
begin
read(N);
if N mod 2 = 1 then {liché N}
23
begin
Prv:=1;
{mohlo by být prvočíslo}
D:=3;
{první případný dělitel}
while (D*D <= N) and (Prv = 1) do
if N mod D = 0 then
Prv:=0
{našli jsme dělitele, není to prvočíslo}
else
D:= D+2
{zkusíme dalšího možného dělitele}
end
else {sudé N}
if N = 2 then Prv:=1 {jediné sudé prvočíslo}
else Prv:=0; {není prvočíslo}
if Prv=1 then
writeln('Je to prvočíslo.')
else
writeln('Není to prvočíslo.')
end.
Cyklus for
Syntaxe:
for Řídicí_Proměnná := Dolní_Mez to Horní_Mez do Příkaz
- řídicí proměnná musí být normálně deklarovaná proměnná celočíselného typu, dolní a horní
mez jsou celočíselné výrazy
Příklad: součet deseti čísel zadaných na vstupu
S:=0;
for I:=1 to 10 do
begin read(X); S:=S+X end;
writeln(S);
Sémantika:
- řídicí proměnná nabývá všech celočíselných hodnot počínaje dolní mezí a konče horní mezí
(včetně), pro každou z nich se vykoná příkaz v těle cyklu
- v příkazu lze využívat hodnoty řídicí proměnné (výhodné zejména pro indexování polí –
bude později)
- výrazy určující meze se vyhodnocují jen jednou při vstupu do cyklu → cyklus „s pevným
počtem opakování“ (případné změny horní meze v průběhu výpočtu cyklu již neovlivní počet
opakování)
- pokud je dolní mez větší než horní mez, příkaz se nevykoná ani jednou
- pokud se horní mez rovná dolní mezi, příkaz se vykoná právě jednou
- řídicí proměnná má po skončení cyklu poslední hodnotu, kterou nabyla, tzn. horní mez
(podle normy není její hodnota definována)
- změna řídicí proměnné uvnitř cyklu je možná a ovlivní počet opakování (tzn. je nebezpečná,
může vést i k zacyklení, podle normy nebyla vůbec povolena – raději nepoužívat)
24
Varianta for-cyklu pro opačný směr průchodu
for Řídicí_Proměnná := Horní_Mez downto Dolní_Mez do Příkaz
- hodnota řídicí proměnné klesá po 1 od horní meze dolů k dolní mezi (jinak totéž)
- použití není příliš časté, hodí se někdy při indexování polí
Předčasné ukončení cyklu
Občas se hodí mít možnost za určitých podmínek výpočet cyklu předčasně ukončit →
standardní procedura break použitá v těle cyklu (for, while, repeat), zpravidla v podmíněném
příkazu.
for I:=1 to N do
begin
…; …; …;
if PodmínkaPředčasnéhoUkončení then break;
…; …; …;
end;
Výpočet pokračuje příkazem následujícím bezprostředně za cyklem.
Alternativní řešení:
- ve for-cyklu dosadit do řídicí proměnné uměle hodnotu horní meze
- v cyklu while/repeat přidat podmínku ukončení do podmínky cyklu
V obou těchto případech se ještě dopočítá až do konce aktuální průchod tělem cyklu (na rozdíl
od použití příkazu break).
Vstup dat
– procedura read(A)
- A je proměnná typu číslo (integer, real, atd.), znak (char) nebo znakový řetězec (string)
- po vykonání příkazu je běžící program pozastaven a čeká na vstupní data
- uživatel zadává vstupní data na klávesnici, čísla odděluje mezerami nebo pomocí Enter,
zadávání dat musí ukončit klávesou Enter
- dosavadní hodnota proměnné A se ztratí, proměnná A nabude hodnoty čtené ze vstupu
- je-li A typu char: ze vstupu se do A přečte jeden znak
- je-li A typu string: ze vstupu se přečtou všechny znaky až do konce řádku (tzn. do Enter) a
uloží se do proměnné A
- je-li A číslo: ze vstupu se přečtou případné úvodní mezery nebo Enter, dále se čtou znaky až
do první mezery nebo do Enter, tato sekvence se zkonvertuje do požadované číselné hodnoty
(pokud to lze, jinak nastane běhová chyba!) a uloží do proměnné A
Je povolen tvar příkazu read(A, B, C) s libovolným počtem parametrů jakožto zkratka za
“read(A); read(B); read(C)”
25
readln → ignorovat znaky ze vstupu až do Enter (včetně Enter),
tzn. pokračovat ve čtení na začátku nového řádku
readln(A)
znamená totéž jako
read(A); readln
Výstup dat
– procedura write(A)
- A je výraz typu číslo (integer, real, atd.), znak (char) nebo znakový řetězec (string)
- výraz A je vyhodnocen a jeho hodnota vypsána na obrazovku
Je povolen tvar příkazu write(A, B, C) s libovolným počtem parametrů jakožto zkratka za
“write(A); write(B); write(C)”
writeln → přechod na nový řádek (vlastně vypsat Enter)
writeln(A) znamená totéž jako write(A); writeln
Příklad:
var A, B, C: integer;
…
A:=14; B:=7; C:=356;
write(A, B, C);
→ na výstupu se objeví: 147356
- všechny hodnoty splynou dohromady!
Je nutné zajistit oddělení hodnot na výstupu
1. použít pro každou hodnotu writeln
→ výstupy jednotlivých čísel na samostatné řádky
2. použít oddělující mezery
write(A, ’ ’, B, ’ ’, C);
na výstupu: 14 7 356
3. použít formátování výstupu
write(A, B:5, C:5);
na výstupu: 14 7 356
Formátování celočíselné hodnoty
write(A: N)
N je výraz typu integer, určuje počet znakových pozic na výstupu.
Je-li hodnota výrazu A kratší než N znaků, doplní se zleva mezerami, je-li delší, vypíše se
celá (na více pozic, tzn. nedodrží se předepsaný formát).
Formátování hodnoty typu real
write(R: N)
- exponenciální tvar na N výstupních pozic
-1.2E+01
(N = 8)
-1.2345678901E+01 (N = 17)
- pro N mezi 8 a 17 se patřičně doplňují desetinná místa
(poslední vypsaná cifra hodnoty je přitom korektně zaokrouhlena)
- pro N < 8 bude výpis stejný, jako pro N = 8
- pro N > 17 bude výpis stejný jako pro N = 17, navíc zleva doplněný mezerami na N pozic
26
write(R)
znamená totéž jako
write(R:17)
write(R: N: M)
- desetinné číslo na N výstupních pozic, z toho M desetinných míst
(poslední cifra hodnoty je korektně zaokrouhlena)
- podle potřeby zleva doplněno mezerami
- pokud hodnota nedovoluje dodržet předepsaný formát, nedodrží se
27
6. Další příkazy a datové typy
Inicializace proměnných
Proměnné hlavního programu mají v řadě implementací (např. v TP 7.0) automaticky
počáteční hodnotu 0.
Pozor - je to věc implementace, třeba ještě v TP 6.0 nebyly inicializovány nijak (měly
„náhodnou“ hodnotu – co zbylo v paměti počítače na příslušném místě), v jiném prostředí
také nemusí být → raději si zvyknout nespoléhat na to.
Navíc ostatní proměnné (deklarované v procedurách a funkcích, dynamicky alokované – bude
později) nejsou ani v běžných implementacích Pascalu nijak inicializovány.
Možnost použít v programu inicializované proměnné – požadovaná počáteční hodnota se
uvádí v místě deklarace.
Inicializované proměnné = „typované konstanty“
- deklarují se pomocí const jako konstanty, jsou to ale proměnné (tzn. jsou umístěny v paměti
a jejich hodnotu lze měnit dosazováním jako hodnotu každé jiné proměnné)
- syntakticky se odlišují od konstant uvedením typu v deklaraci
- syntaxe: const Jméno: Typ = Hodnota;
- lze použít i pro proměnné strukturovaného typu (např. pole)
… bude ukázáno později
Příklad:
const X = 10;
var
Y: integer;
const Z: integer = 10;
{konstanta}
{obyčejná proměnná}
{inicializovaná proměnná}
Aritmetické přetečení pro celá čísla
Do celočíselné proměnné se při výpočtu dosazuje hodnota výrazu přesahující povolený rozsah
→ aritmetické přetečení.
Možná řešení situace:
1. dosadí se „náhradní hodnota“ – počítání modulo rozsah
např. u dvoubytového typu integer: 32767 + 1 = -32768
u typu byte:
255 + 1 = 0
- v Turbo Pascalu je toto standardní chování
2. vyvolání běhové chyby
- v Turbo Pascalu lze tento režim práce zapnout pro typy integer, word, longint
- běhová chyba nemůže nastat při použití standardních procedur inc, dec
28
Přepínače režimu práce překladače
- buď v integrovaném prostředí
- nebo přímo ve zdrojovém kódu pomocí přepínače {$Q+}
… lze opět vypnout pomocí {$Q-}, střídavě měnit oba režimy podle potřeby
Vyhodnocování výrazů probíhá postupně podle typu operandů
→ pozor na skryté nebezpečí přetečení!
Příklad: Převeďte časový údaj zadaných v hodinách, minutách a sekundách (proměnné typu
integer) na sekundy.
Řešení 1 – první nápad:
var H, M, S: integer;
Vysledek: integer;
begin ... Vysledek := H*3600 + M*60 + S; ... end
→ už pro H=10 se výsledek nevejde do rozsahu typu integer (pro 2B integer)
Řešení 2 – spravíme to, výsledek bude tedy typu longint:
var H, M, S: integer;
Vysledek: longint;
begin ... Vysledek := H*3600 + M*60 + S; ... end
→ pro H=10 se H*3600 vyhodnocuje v typu integer a opět přeteče!
Řešení 3 – proměnné ve výrazu typu longint:
var H, M, S: longint;
Vysledek: longint;
begin ... Vysledek := H*3600 + M*60 + S; ... end
→ pro H=10 se už výraz vyhodnocuje v typu longint správně, zbytečně ale plýtváme místem
na proměnné H, M, S
Řešení 4 – přetypování:
var H, M, S: integer;
Vysledek: longint;
begin ... Vysledek := longint(H)*3600 + M*60 + S; ... end
→ výraz s integerovými proměnnými se vyhodnocuje v typu longint, tedy správně
Přetečení a zaokrouhlovací chyby v typu real
Do proměnné typu real se při výpočtu dosazuje hodnota výrazu přesahující povolený rozsah
→ aritmetické přetečení v pohyblivé řádové čárce → běhová chyba.
Hodnota výrazu typu real má více platných cifer, než se vejde do proměnné typu real (cca 1112) → dojde k zaokrouhlení (a při tom mohou vznikat zaokrouhlovací chyby).
29
Důsledky zaokrouhlovacích chyb:
- pro některé hodnoty proměnné X typu real může být X = X+1 (např. když X = 1E13)
- nemusí platit asociativita při sčítání A+B+C (např. pro hodnoty A=1, B=1E15, C=– 1E15)
- součet N hodnot 1/N se nemusí rovnat 1 (např. pro hodnoty N=7, 10, 12, 13, 14, 19, 20)
program Ntiny;
{součet N hodnot rovných 1/N je roven 1?}
var N, I: integer;
Ntina, Suma: real;
begin
for N:=1 to 20 do
begin
Ntina:= 1/N;
Suma:=0;
for I:=1 to N do
Suma:=Suma+Ntina;
write(N:2, Ntina, Suma);
if Suma = 1 then writeln(' ANO') else writeln('
end
end.
NE')
Příkaz case
= výběr z více variant podle hodnoty výrazu
Základní syntaxe:
case Výraz of
Hodnota1: Příkaz1;
Hodnota2: Příkaz2;
...
HodnotaN: PříkazN
end
Výraz uvedený za case může být libovolného celočíselného typu, hodnoty musí být konstanty
téhož typu..
Sémantika: Uvedený příkaz je funkčně rovnocenný příkazu
if Výraz = Hodnota1 then Příkaz1
else if Výraz = Hodnota2 then Příkaz2
...
else if Výraz = HodnotaN then PříkazN
Pokud se tedy Výraz nerovná žádné z uvedených hodnot, nevykoná se žádný z příkazů.
30
Rozšíření příkazu case
Možnost doplnit implicitní variantu → pokud se Výraz nerovná žádné z uvedených hodnot,
vykoná se Příkaz ze závěrečné větve else.
case Výraz of
Hodnota1: Příkaz1;
Hodnota2: Příkaz2;
...
HodnotaN: PříkazN;
else Příkaz
end
Přípustné tvary hodnot uváděných u jednotlivých variant:
- konstanta
20:
- několik konstant oddělených čárkami
20, 22, 24:
- interval hodnot
30..40:
- kombinace výše uvedených možností
1, 3..7, 9..15, 40:
Hodnoty uvedené u variant příkazu case nemusí být navzájem disjunktní → vykoná se příkaz
z první větve, u které dojde ke shodě hodnoty s výrazem.
Příklad:
case N of
{N je proměnná typu integer}
1: writeln(N);
{jedna akce}
2: begin inc(A); dec(B) end;
{více akcí – složený příkaz}
0..9:
{jiné jednociferné číslo – nedělej nic}
else writeln(‘CHYBA’)
{víceciferné číslo je chyba}
end.
Příklad praktického použití:
Program potřebuje reagovat podle toho, jaká klávesa byla stisknuta na klávesnici – rozhoduje
se podle hodnoty proměnné obsahující hodnotu stisknuté klávesy (každá klávesa má nějaký
celočíselný kód), je mnoho možností, pro některé klávesy bude stejná reakce.
case StisknutaKlavesa of
SipkaNahoru:
SipkaDolu:
SipkaVlevo, SipkaVpravo:
Cifra0..Cifra9:
else
end
akce
akce
akce
akce
akce
31
pro
pro
pro
pro
pro
šipku nahoru;
šipku dolů;
jinou šipku;
dekadickou číslici;
všechny ostatní klávesy;
Typ Boolean
var B: boolean;
- má pouze dvě možné hodnoty: false a true
- do proměnné typu boolean lze dosadit hodnotu výrazu typu boolean
- výrazy typu boolean = logické výrazy
* jednoduché: konstanty, proměnné, funkce typu boolean,
relace (vytvořené pomocí relačních operátorů)
* složené: vznikají z jednoduchých pomocí logických spojek a závorek ( )
- standardní funkce typu boolean
* odd(N) ⇔ N je liché (parametr N celočíselný)
* později se naučíme další funkce (např. eof, eoln u souborů)
- výraz typu boolean lze použít:
* dosadit jeho hodnotu do proměnné typu boolean
* na místě podmínky (v příkazech if, while, repeat-until)
Příklady:
B := Pocet = 100;
{vyhodnotí se podmínka „Počet = 100“ a výsledná logická hodnota
se dosadí do proměnné B typu Boolean}
if Pocet = 100 then B:=true else B:=false; {má stejný význam}
if B and (X > 0) then ...
{složený výraz použitý na místě podmínky}
while Pokracovat do begin ... end;
{Pokracovat je proměnná typu Boolean, v těle cyklu se za určitých
podmínek nastavuje na false, aby cyklus skončil}
while true do begin ... end;
{věčný cyklus, v těle cyklu musí být zajištěno ukončení výpočtu pomocí break}
Příklad: Test prvočíselnosti – určit, zda je zkoumané číslo N prvočíslem
(druhá verze s využitím datového typu boolean)
program Test_Prvociselnosti_2;
{test prvočíselnosti – druhá verze}
var N: integer;
{zkoumané číslo}
D: integer;
{dělitel}
Prv: boolean; {příznak, zda je N prvočíslo}
begin
read(N);
if odd(N) then
{liché N}
begin
Prv:=true;
{mohlo by být prvočíslo}
D:=3;
{první případný dělitel}
while (sqr(D) <= N) and Prv do
if N mod D = 0 then
Prv:=false {našli jsme dělitele, není to prvočíslo}
32
else
D:=D+2
{zkusíme dalšího možného dělitele}
end
else {sudé N}
Prv := N=2;
{jediné sudé prvočíslo}
if Prv then
writeln('Je to prvočíslo.')
else
writeln('Není to prvočíslo.')
end.
33
7. Procedury a funkce
Dekompozice problému
– rozdělení problému na logicky ucelené části, každé části odpovídá samostatná
procedura nebo funkce v programu.
Návrh rozhraní – jména procedur a funkcí, způsob jejich komunikace s okolím (= jaké mají
parametry).
Programujeme vždy proti rozhraní, bez znalosti (resp. bez využívání znalosti)
implementace.
Přístup k rozhraní shora: v zápisu programu voláme procedury a funkce, o nichž víme, jak se
volají a co dělají, ale nevíme, jak to dělají
… a pokud to náhodou víme, tak tuto znalost nevyužíváme
(v budoucnu je možná změna implementace těchto procedur a funkcí)
Přístup k rozhraní zdola: píšeme procedury a funkce, o nichž víme, jak se budou volat a co
mají dělat, ale nevíme, kdo a v jakém kontextu je bude používat
… a pokud to náhodou víme, tak tuto znalost nevyužíváme
(v budoucnu je možná bude chtít volat také někdo další)
Procedury
Deklarace procedury se zapisuje v oblasti deklarací programu a má tuto podobu:
procedure JménoProcedury;
<lokální deklarace>
… stejné jako oblast deklarací v programu
begin
… stejné jako tělo programu
<tělo = složený příkaz>
end;
Příklad:
procedure Cara;
{vypíše čáru z 50 hvězdiček}
const N=50;
var I: integer;
begin
for I:=1 to N do write(‘*’);
writeln
end;
34
Volání procedury: jednoduchý příkaz ve tvaru jména volané procedury
begin
...;
Cara;
...;
Cara;
...;
end
Sémantika příkazu volání procedury:
- odskok na provedení příkazů uvedených v těle procedury
- poté návrat za místo volání (podle uložené návratové adresy)
Použití procedury:
1. pokud se určitá činnost má vykonat v programu opakovaně vícekrát, zapíšeme ji
v programu jen jednou ve tvaru procedury a tuto proceduru pak opakovaně voláme
→ kratší a přehlednější kód, provádění budoucích oprav na jediném místě
2. dekompozice programu na menší logické celky
→ přehlednost a strukturovanost programu
(používáme, i když potom v programu voláme proceduru jen jednou)
Lokální deklarace
= uvnitř procedury deklarujeme všechny prostředky (proměnné, konstanty, typy, …), které
v této proceduře používáme
- v maximální míře využívat (jinak strukturování kódu do procedur ztrácí smysl)
- prostředky nejsou viditelné vně procedury (v hlavním programu ani třeba v jiné proceduře)
- procedura je samostatný prostor jmen (nevadí jiné použití stejného identifikátoru mimo
proceduru)
- zastiňuje stejnojmennou globální deklaraci (ta je pak v proceduře nedostupná)
- nezastíněné globální identifikátory lze v proceduře používat (ale děláme to jen tehdy, když k
tomu máme dobrý důvod)
- lokálně v proceduře lze deklarovat nejen proměnné, typy, konstanty a návěstí, ale také další
procedury a funkce (ty pak lze volat jen uvnitř této procedury)
- proměnné deklarované lokálně v proceduře nemají definovanou počáteční hodnotu (nejsou
automaticky vynulovány ani si nezachovají hodnotu z minulého volání téže procedury)
Parametry
- nástroj pro předávání vstupních hodnot do procedury a výstupních, tzn. výsledků, ven
z procedury (jinak by procedura dělala pořád úplně stejnou akci)
- deklarace procedury: v hlavičce uvedeme seznam formálních parametrů
- parametry mohou být libovolného typu (i strukturovaného)
- volání procedury: v hlavičce uvedeme seznam skutečných parametrů
→ musí být stejný počet a stejného typu (ve stejném pořadí) jako formální parametry
35
procedure Cara(N: byte; Z: char);
{vypíše čáru z N znaků Z}
var I: integer;
begin
for I:=1 to N do write(Z);
writeln
end;
Volání:
Cara(40, ’=’);
Cara(60, ’.’);
Upřesnění syntaxe:
- formální parametry se oddělují středníkem
- více formálních parametrů téhož typu lze oddělit čárkami a typ zapsat jen jednou (podobně
jako v deklaracích proměnných), např.:
procedure P(A, B, C: real; M, N: integer);
- je nutné uvést vždy jméno typu (identifikátor), nikoli jeho definici
→ je-li parametrem např. pole, musí být příslušný typ předem definován
a pojmenován pomocí type
NELZE psát např.:
procedure P(X: array[1..10] of integer);
- skutečné parametry se oddělují čárkami
- na místě skutečných parametrů nemusí být jen konstanty, ale mohou to být jakékoliv výrazy
příslušného typu
Upřesnění sémantiky:
- výrazy zapsané na místě skutečných parametrů se vyhodnotí a jejich hodnota se dosadí do
odpovídajících formálních parametrů
- formální parametry jsou tedy vlastně další lokální proměnné, jejichž počáteční hodnota je
stanovena v okamžiku volání. Dále se mohou v proceduře libovolně měnit, navenek se to
nijak neprojeví, po skončení výpočtu procedury zaniknou
→ předávání parametrů HODNOTOU - pouze vstupní!
Ještě potřebujeme nějaký mechanismus, jak předávat výsledky výpočtu z procedury ven
→ předávání parametrů ODKAZEM - vstupní i výstupní
Syntaxe:
- v deklaraci procedury jsou formální parametry předávané odkazem označeny klíčovým
slovem var (má platnost vždy do nejbližšího středníku), např.:
procedure P(A: real; var B, C: real; M: integer;
var N: integer);
{parametry A, M jsou zde předávány hodnotou, parametry B, C, N odkazem}
- při volání procedury na místě skutečných parametrů předávaných odkazem musí stát
proměnné.
36
Sémantika:
- vyhodnotí se adresy skutečných parametrů a předají se do odpovídajících formálních
parametrů
- formální parametry jsou tedy vlastně dočasné lokální odkazy na globálně existující
proměnné
- jakékoliv manipulace s formálním parametrem v těle procedury se prostřednictvím odkazu
fakticky provádějí s příslušnou globální proměnnou → procedura v parametru dostane vstupní
hodnotu, může ho měnit a může v něm zanechat výstupní hodnotu.
Po skončení výpočtu procedury sice formální parametr zanikne – ale to je jen ten lokální
odkaz, nikoli vlastní proměnná!
Použití parametrů předávaných odkazem:
- má-li parametr sloužit jako výstupní (nebo vstupní i výstupní)
- je-li parametr rozsáhlou strukturou (vytváření lokální kopie při předávání parametru
hodnotou by bylo náročné paměťově i časově)
Funkce
Deklarace funkce se zapisuje v oblasti deklarací programu a má tuto podobu:
function JménoFunkce (formální parametry): TypVýsledku;
<lokální deklarace>
… stejné jako oblast deklarací v programu
begin
<tělo = složený příkaz>
… stejné jako tělo programu
end;
- mezi příkazy v těle funkce musí být definována návratová hodnota ve tvaru:
JménoFunkce := Výraz
- JménoFunkce se v těle funkce jeví jako lokální proměnná typu TypVýsledku, do níž lze
pouze dosazovat a tím se definuje návratová hodnota (výsledek)
- dosazovat lze i opakovaně - platí poslední dosazená hodnota.
- povolený TypVýsledku může být omezen – to závisí na implementaci (například podle
normy jazyka a také třeba v Turbo Pascalu může být pouze číselný, znakový, string, boolean
nebo ukazatel, nesmí být strukturovaný, naproti tomu ve FreePascalu může být i
strukturovaný)
Jinak pro funkce platí vše jako pro procedury – lokalita identifikátorů, viditelnost, způsoby
předávání parametrů.
Je poměrně obvyklé, že funkce nepoužívají parametry předávané odkazem – výsledek práce
se předává ven jako funkční hodnota.
Volání funkce: JménoFunkce (skutečné parametry)
- volání funkce má podobu výrazu – na rozdíl od volání procedury, což byl příkaz
- vrací návratovou hodnotu, může být i součástí většího výrazu
37
Příklad:
function Max3 (A, B, C: integer): integer;
{vybírá maximum ze tří zadaných celých čísel}
var D: integer;
begin
if A > B then D:=A else D:=B;
if C > D then D:=C;
Max3:=D
end;
Pozor na chybu:
function Max3 (A, B, C: integer): integer;
{vybírá maximum ze tří zadaných celých čísel}
begin
if A > B then Max3:=A else Max3:=B;
if C > Max3 then Max3:=C;
end;
Opakované dosazení hodnoty do identifikátoru Max3 je v pořádku (lze dosazovat opakovaně).
Chybou ale je porovnání hodnoty uložené v proměnné Max3 – to překladač chápe jako
rekurzivní volání funkce (s chybným počtem parametrů)!
Příklad: přestupný rok
function Prestupny (Rok: integer): boolean;
{zjištění, zda je rok přestupný
– podle Gregoriánského kalendáře platného od roku 1582}
begin
Prestupny := (Rok mod 4 = 0) and (Rok mod 100 <> 0)
or (Rok mod 400 = 0)
end;
var R: integer;
...
if Prestupny(R) then ...
Způsoby komunikace podprogramu s okolím
1. parametry předávané hodnotou – pouze vstupní
2. parametry předávané odkazem – vstupní i výstupní
3. návratová hodnota funkce – pouze výstupní
(jen jedna hodnota, navíc někdy pouze jednoduchého typu)
4. globální proměnné – vstupní i výstupní
(používat jen ve výjimečných a odůvodněných případech)
38
Příklad: určení NSD Eukleidovým algoritmem
procedure NSD (A, B: integer; var C: integer);
begin
while A <> B do
if A > B then A:=A-B else B:=B-A;
C:=A
end;
Volání: NSD(33,15,X);
function NSD (A, B: integer): integer;
begin
while A <> B do
if A > B then A:=A-B else B:=B-A;
NSD:=A
end;
Volání: X:=NSD(33,15);
procedure NSD (A, B: integer);
begin
while A <> B do
if A > B then A:=A-B else B:=B-A;
X:=A
end;
Volání: NSD(33,15);
Poslední uvedený případ nepoužívat! – procedura vkládá výsledek výpočtu do pevně zvolené
globální proměnné.
Inicializované proměnné deklarované v proceduře
- jsou to lokální identifikátory viditelné pouze v rámci procedury
- alokují se však staticky → nezanikají po skončení výpočtu procedury, udržují si svou
poslední hodnotu do příštího volání
- inicializace se provádí jen jednou na začátku výpočtu programu
program P;
procedure S;
const I: byte = 1;
begin inc(I); write(I) end;
begin
S; S; S
end.
Co program vypíše?
234
39
8. Pole a jejich použití
- pole je datová struktura tvořená více složkami téhož typu
- přístup ke složkám pomocí identifikátoru pole + indexu
type JménoTypu = array [DolníMez .. HorníMez] of TypPoložek
- dolní mez a horní mez jsou celočíselné konstanty
- typ složek pole může být libovolný – jednoduchý i strukturovaný, ale všechny složky jsou
vždy stejného typu
Příklady:
const Max = 10;
type T = array [1..Max] of integer;
var
P: T;
type
var
T1 = array [-10..10] of real;
P1, Q1: T1;
{dvě pole stejného typu}
Obvykle užívaná zkratka zápisu – deklarace proměnné bez pojmenování typu, definice
nového typu je součástí deklarace proměnných:
var
P1, Q1: array [-10..10] of real;
Indexování
P[3] := 17;
read(P1[-4]);
S proměnnou typu pole lze bez indexování provádět jedinou operaci, a to dosazení mezi
dvěma proměnnými téhož typu: Q1:=P1;
Pole se může indexovat proměnnou (obecně dokonce libovolným celočíselným výrazem) →
možnost v cyklu vykonat jistou akci se všemi složkami pole.
.
Typicky se využívá for-cyklus a indexování prvků pole jeho řídicí proměnnou:
for I:=1 to Max do read(P[I]);
{načtení pole po složkách}
...
S:=0;
for I:=1 to Max do S:=S+P[I];
{součet všech prvků pole}
Pozor na hodnotu indexu mimo deklarovaný rozsah – reakce podle nastavení přepínače $R:
{$R+} provádí se kontrola při výpočtu → běhová chyba
přetečení indexu (Range check error)
{$R-} kontrola se neprovádí → kratší a rychlejší přeložený kód, ale logická chyba
(chybný výpočet bez upozornění, může třeba dojít ke změně jiné proměnné)
Standardní výchozí nastavení: bez kontrol
Doporučení: dokud není program odladěn, vždy zapínat!
Nejčastější příčina problémů, pokud se program chová zdánlivě nesmyslně.
40
Vyhodnocení polynomu v bodě
p(x) = anxn + an-1xn-1 + an-2xn-2… + a1x + a0
n – stupeň polynomu
a0, …, an – koeficienty (reálné konstanty)
x – proměnná, za niž dosazujeme různé hodnoty
Přímý výpočet podle uvedeného předpisu
počet násobení: n + (n-1) + (n-2) + … + 1 = n.(n+1)/2
počet sčítání: n
časová složitost algoritmu: O(n2)
Hornerovo schéma
p(x) = (…((anx + an-1).x + an-2).x + … +a1).x + a0
počet násobení: n
počet sčítání: n
časová složitost algoritmu: O(n)
program Horner;
const MaxN = 20; {maximální stupeň polynomu}
var A: array[0..MaxN] of real; {koeficienty polynomu}
N: integer;
{stupeň polynomu}
X: real;
{zkoumaný bod}
H: real;
{výsledná hodnota}
I: integer;
begin
write('Stupeň polynomu: ');
read(N);
write('Koeficienty v pořadí od A[N] do A[0]: ');
for I:=N downto 0 do read(A[I]);
write('Bod, v němž počítáme hodnotu: ');
read(X);
H:=A[N];
for I:=N-1 downto 0 do H:=H*X+A[I];
writeln('Výsledná hodnota: ', H)
end.
Nalezení všech prvočísel od 2 do N
– Eratosthenovo síto
Princip: v řadě čísel od 2 do N postupně vyškrtáváme všechny násobky jednotlivých
prvočísel; co nebude vyškrtnuto, je prvočíslo.
Realizace: Síto v programu reprezentujeme polem prvků typu Boolean, index pole určuje
číslo od 2 do N, hodnota prvku síta říká, zda je prvočíslem.
41
program Eratosthenovo_Sito;
const Max = 10000; {maximální přípustná hodnota B}
var A, B: integer; {dolní a horní mez}
Sito: array[2..Max] of boolean;
Pocet: integer; {počet prvočísel na <A,B>}
I, J: integer;
begin
write('Zkoumaný interval: ');
readln(A, B);
{horní mez prvočísel je B}
for I:=2 to B do Sito[I]:=true;
for I:=2 to B do
{zkoumáme číslo I}
if Sito[I] then {je to prvočíslo}
begin
J:=I*2;
{zrušíme jeho násobky}
while J <= B do
begin
Sito[J]:=false; {J je násobkem I -> není prvočíslo}
J:=J+I
{další násobek}
end;
end;
Pocet:=0;
for I:=A to B do
if Sito[I] then
begin Pocet:=Pocet+1; write(I:8) end;
writeln;
writeln('Počet prvočísel v intervalu <',A,',',B,'>: ', Pocet)
end.
Vyhledávání v poli
Úkol: zjistit, zda se v poli nachází daná hodnota a kde
(pokud je tam vícekrát, chceme první výskyt)
Algoritmus: jeden sekvenční průchod polem – časová složitost O(N)
var A: array [1..N] of T;
X: T; {hledaná hodnota}
1. for-cyklus
J := 0;
for I := 1 to
if A[I] = X
if J = 0 then
else
N do
then J := I;
…
{ hodnota X v poli A není }
…
{ hodnota X nalezena – je to prvek A[J] }
Jednoduché, ale nešikovné (cyklus zbytečně pokračuje i po nalezení hodnoty X)
42
2. for-cyklus s výskokem
J := 0;
for I := 1 to
if A[I] = X
if J = 0 then
else
N do
then begin J := I; break end;
…
{ hodnota X v poli A není }
…
{ hodnota X nalezena – je to prvek A[J] }
Obdobné řešení, ale cyklus zbytečně nepokračuje po nalezení X.
Použitelné jen v implementacích, které mají příkaz break (v normě jazyka není obsažen).
3. while-cyklus
I := 1;
while (I <= N) and (A[I] <> X) do inc(I);
if I > N then …
{ hodnota X v poli A není }
else …
{ hodnota X nalezena – je to prvek A[I] }
Vše řeší vhodně zvolená složená podmínka, ale POZOR!
Není-li prvek X v poli A obsažen, může nastat běhová chyba přetečení indexu, neboť
v podmínce se testuje A[I] pro I=N+1.
Korektní je toto řešení v případě zkráceného vyhodnocování logických výrazů {$B-}.
Dva způsoby vyhodnocování logických výrazů
- volba režimu překladu pomocí přepínače $B nebo v nastavení vývojového prostředí:
{$B+} úplné vyhodnocování – nejprve se vyhodnotí všechny dílčí podvýrazy a jejich hodnoty
se následně kombinují pomocí logických spojek (norma jazyka)
{$B-} zkrácené vyhodnocování – logický výraz se vyhodnocuje postupně zleva doprava,
dokud není rozhodnuto o výsledku (implicitní nastavení v implementacích, např. v TP)
4. cyklus řízený proměnou typu boolean
var Dalsi: boolean; {zda zpracovávat další prvek}
…
I := 1;
Dalsi := true;
while Dalsi do
if A[I] = X then
begin Dalsi := false;
…
{ hodnota X nalezena – je to prvek A[I] }
end
else if I = N then
begin Dalsi := false;
…
{ hodnota X v poli A není }
end
else inc(I);
43
5. vyhledávání pomocí zarážky
→ zjednodušení podmínky ve while-cyklu
var A: array [1..N+1] of T;
{přidaný prvek A[N+1] navíc pro uložení zarážky}
X: T; {hledaná hodnota}
A[N+1] := X;
{vložení zarážky}
I := 1;
while A[I] <> X do inc(I);
if I > N then …
{ hodnota X v poli A není }
else …
{ hodnota X nalezena – je to prvek A[I] }
Hodnota X je v poli A vždy nalezena – pokud ale po skončení cyklu platí I > N, tak se našla
až na místě zarážky, tzn. původně v poli A[1..N] nebyla.
Binární vyhledávání
- vyhledávání v uspořádaném poli
Algoritmus: metoda půlení intervalů (byl vysvětlen dříve)
→ časová složitost O(log N)
var A: array [1..N] of T;
{A[1] < A[2] < … <A[N]}
X: T;
{hledaná hodnota}
i, j, k: integer;
{pomocné indexy}
…
i := 1; j := N;
{meze zkoumaného úseku}
repeat
k := (i+j) div 2; {index prostředního prvku}
if X > A[k] then i := k+1
else j := k-1
until (A[k] = X) or (i > j);
if X = A[k] then … { hodnota X nalezena – je to prvek A[k] }
else … { hodnota X v poli A není }
Třídění čísel v poli
= vnitřní třídění (řazení)
Úkol: uspořádat prvky pole podle velikosti (od nejmenšího po největší).
Přímé metody
- jednoduchý zápis programu
- časová složitost O(N 2) → vhodné jen pro malá data
- třídí „na místě“ (tzn. nepotřebují další datovou strukturu velikosti N)
44
Další metody budou později
- rekurzivní quicksort a mergesort, třídění haldou (heapsort)
- časová složitost O(N log N)
Přímý výběr
Algoritmus:
Pole se dělí na setříděný úsek (vlevo) a nesetříděný úsek (vpravo). Na začátku výpočtu tvoří
všechny prvky nesetříděný úsek.
V nesetříděném úseku pole se vždy najde nejmenší prvek a vymění se s prvním prvkem
tohoto úseku. Tím se nesetříděný úsek zleva zkrátí o jeden prvek a zároveň se úsek setříděný
o tento jeden prvek prodlouží.
Realizace: na místě v jediném poli – vybíraná minima se postupně ukládají do pole zleva,
vždy výměnou s původními hodnotami.
const N = 1000;
type Pole = array [1..N] of integer;
var A: Pole;
{tříděné pole}
i,j,k: integer;
{indexy prvků}
X: integer;
{pro výměnu prvků}
...
for i:=1 to N-1 do
begin {umístit číslo na pozici i v poli A}
k:=i;
for j:=i+1 to N do
{vyhledání minima v úseku A[i..N]}
if A[j] < A[k] then k:=j;
if k > i then {výměna prvků s indexy i, k}
begin X:=A[k]; A[k]:=A[i]; A[i]:=X end
end
Totéž ve tvaru procedury:
procedure PrimyVyber(var A: Pole);
var i,j,k: integer;
{indexy prvků}
X: integer;
{pro výměnu prvků}
Begin
for i:=1 to N-1 do {umístit číslo na pozici i}
begin
k:=i;
for j:=i+1 to N do
{vyhledání minima}
if A[j] < A[k] then k:=j;
if k > i then
{výměna prvků s indexy i, k}
begin X:=A[k]; A[k]:=A[i]; A[i]:=X end
end
end; {procedure PrimyVyber}
45
Přímé vkládání (přímé zatřiďování)
Algoritmus:
Pole se dělí na setříděný úsek (vlevo) a nesetříděný úsek (vpravo). Na začátku výpočtu je
setříděný úsek tvořen pouze prvním prvkem pole.
První prvek nesetříděného úseku se vždy zařadí podle velikosti do setříděného úseku. Tím se
setříděný úsek prodlouží o jeden prvek a nesetříděný úsek se zleva zkrátí o jeden prvek.
Realizace: na místě v jediném poli – prvky setříděného úseku se posouvají o jednu pozici
doprava, dokud je třeba.
procedure PrimeVkladani(var A: Pole);
var i,j: integer;
{indexy prvků}
X: integer;
{pro výměnu prvků}
Hledat:Boolean;
begin
for i:=2 to N do
{zatřiďujeme číslo z pozice i}
begin
X:=A[i];
j:=i-1;
Hledat:=X < A[j];
while Hledat do
{hledání správné pozice}
begin
A[j+1]:=A[j];
j:=j-1;
if j=0 then Hledat:=false else Hledat:=X < A[j]
end;
A[j+1]:=X
end
end; {procedure PrimeVkladani}
3. Bublinkové třídění (třídění záměnami)
Pozorování:
ve vzestupně setříděném poli stojí vždy menší prvek před větším
Algoritmus:
Opakovaně se prochází pole a porovnávají se dvojice sousedních prvků, v případě špatného
uspořádání (větší prvek před menším) se tyto prvky spolu vymění – tím se v poli vytváří
setříděný úsek.
Možnosti realizace:
průchody polem zleva doprava → setříděný úsek vzniká odzadu (od největších prvků)
průchody polem zprava doleva → setříděný úsek vzniká odpředu (od nejmenších prvků)
každý průchod může být vždy o jeden krok kratší než předchozí
46
procedure BublinkoveTrideni(var A: Pole);
var i,j: integer;
{indexy prvků}
X: integer;
{pro výměnu prvků}
begin
for i:=2 to N do
for j:=N downto i do
{průchod zprava doleva}
if A[j-1] > A[j] then {vyměnit sousední prvky}
begin X:=A[j-1]; A[j-1]:=A[j]; A[j]:=X end
end; {procedure BublinkoveTrideni}
Možnosti zrychlení:
- při příštím průchodu polem stačí jít jen do místa poslední uskutečněné výměny
→ rychlejší zkracování průchodů, méně průchodů
- třídění přetřásáním – pole se prochází střídavě zleva a zprava
Zásobník (LIFO = last in, first out)
– realizace v poli
- zásobník je reprezentován polem Z: array [1..N] of T
- N je kapacita zásobníku (kolik prvků může obsahovat najednou)
- dno zásobníku: Z[1]
- vrchol zásobníku = místo, kde se přidávají a odebírají prvky: Z[V]
- prázdný zásobník (také inicializace nového zásobníku): V=0
Vložení hodnoty X do zásobníku
předpokládáme, že je tam na ni místo, tzn. že V < N, jinak by bylo třeba přidat příslušný test:
inc(V);
Z[V]:=X;
Odebrání hodnoty ze zásobníku a vložení do proměnné X:
X:=Z[V];
dec(V);
Obě operace mají konstantní časovou složitost.
Fronta (FIFO = first in, first out)
– realizace v poli
- fronta je reprezentována polem F: array [1..N] of T
- N je kapacita fronty (kolik prvků může obsahovat najednou)
- konec fronty = místo příchodu do fronty: F[Prich]
- začátek fronty = místo odchodu z fronty: F[Odch]
- prázdná fronta (také inicializace nové fronty): Prich=0
47
Vložení hodnoty X do fronty
předpokládáme, že je tam na ni místo, tzn. že Prich < N (jinak by bylo třeba přidat test):
inc(Prich);
F[Prich]:=X;
Odebrání hodnoty z fronty a vložení do proměnné X:
X:=F[Odch];
inc(Odch);
Problém: Obsazená část pole F se posouvá k vyšším indexům, časem není kam přidat další
přicházející prvek, i když fronta není moc dlouhá a v poli F jsou volná místa po odebraných
prvcích.
Řešení:
1. Při každém odebrání prvku z fronty se obsazená část pole F posune o 1 místo doleva (tzn.
stále platí Odch=1, proměnou Odch tedy ani nepotřebujeme) → časová složitost odebrání
bude O(N):
X:=F[1];
for I:=2 to Prich do F[I-1]:=F[I];
dec(Prich);
2. Posunutí obsazené části pole F se uskuteční jen když je to nutné, tzn. není-li místo na
vkládaný prvek → posunuje se méně často a na větší vzdálenost (vždy až do pozice Odch=1).
Časová složitost odebrání prvku z fronty zůstane tedy konstantní, časová složitost vkládání
bude v nejhorším případě lineární (ale velmi často se provede vložení prvku v konstantním
čase).
if Prich = N then {je tam plno, nejdřív posunout}
begin
for I:= Odch to Prich do F[I-Odch+1]:=F[I];
Prich:=Prich-Odch+1;
Odch:=1
end;
inc(Prich);
F[Prich]:=X;
3. Pole F se chápe cyklicky, za F[N] následuje opět prvek F[1], obsazená část pole se nikdy
neposouvá → časová složitost obou operací zůstává konstantní.
Vložení hodnoty X do fronty (předpokládáme, že je tam na ni místo):
if Prich < N then inc(Prich) else Prich:=1;
F[Prich]:=X;
Odebrání hodnoty z fronty a vložení do proměnné X:
X:=F[Odch];
if Odch < N then inc(Odch) else Odch:=1;
48
Dlouhá čísla
Chceme například počítat s kladnými celými čísly s max. 100 ciframi
(podobně pro čísla se znaménkem, čísla desetinná apod.)
Reprezentace: číslo uložíme po cifrách do prvků pole
type Cislo = array [1..100] of byte;
var A, B, C: Cislo;
PA, PB, PC: byte;
{počet cifer}
Je nutno zvolit, kam dáme kterou cifru – je to jedno, ale potom musíme naši volbu důsledně
dodržovat v celém programu!
Např.: A[1] – jednotky, A[2] – desítky, A[3] – stovky, …,
A[PA] – cifra nejvyššího řádu
(příjemnější počítání)
nebo obráceně:
A[1] – cifra nejvyššího řádu, …, A[PA] – jednotky
(snadnější načítání ze vstupu)
Operace:
- po cifrách – jako sčítání, odčítání, násobení či dělení víceciferných čísel na základní škole
- počítání modulo 10, přenosy do vyšších řádů
Modifikace:
číslo uložíme po dvojicích cifer do pole prvků typu byte, nebo po čtveřicích do prvků pole
typu word, nebo dokonce po devíti cifrách do prvků pole typu longint
→ úspora paměti, rychlejší výpočet (počítání modulo 100, nebo 10000, apod.)
Desetinné číslo:
- stačí doplnit evidenci polohy desetinné čárky
- buď speciální hodnota v příslušném prvku pole, nebo speciální proměnná s indexem
nulového řádu, nebo použijeme dvě pole – pro uložení celé a desetinné části čísla
Příklad:
součet kladných celých čísel A, B vložíme do proměnné C
zvolená reprezentace čísla: A[1] = cifra jednotek
if PA < PB then M:=PA
else M:=PB; {M – délka kratšího čísla}
Prenos:=0;
for I:=1 to M do
begin
X := A[I] + B[I] + Prenos;
C[I] := X mod 10;
Prenos := X div 10
end;
{dále podobně ošetříme „přečnívající“ část delšího čísla a nakonec ještě případný nenulový
přenos}
49
Vícerozměrné pole
type Obdelnik = array [1..3, 1..4] of integer;
var M: Obdelnik;
...
M[2,3] := 3145;
- počet indexů není omezen (v praxi se zpravidla používají nejvýše.3)
- více indexů → pomalejší přístup k prvku (počítá se adresa prvku)
- zkratka za „pole polí“
type Obdelnik = array [1..3] of
array [1..4] of integer;
...
M[2][3] := 3145;
{toto je rovněž povolený korektní zápis, ekvivalentní význam}
Příklad: součin dvou čtvercových matic
const N = 10;
type Matice = array [1..N, 1..N] of real;
var A, B, C: Matice;
...
{počítáme součin A*B, výsledek uložit do C}
for I:=1 to N do
for J:=1 to N do
begin
X:=0;
for K:=1 to N do X:=X+A[I,K]*B[K,J];
C[I,J]:=X
end;
Inicializované pole
- inicializovaná proměnná může být typu pole
- hodnoty prvků se vypisují do závorek, oddělené čárkami
- u vícerozměrných polí více úrovní závorek
const Mesice: array[1..12] of byte =
(31,28,31,30,31,30,31,31,30,31,30,31);
const C: Obdelnik = ( (1,2,3,4),
(0,1,1,0),
(9,8,7,6) );
50
Příklad použití pole – následující permutace
Uvažujme všechny permutace N čísel {1, 2, 3, …, N}. Mezi těmito permutacemi je
definováno tzv. lexikografické uspořádání, tedy seřazení stejným způsobem, jako se řadí hesla
ve slovníku. Vzájemné pořadí dvou permutací je tedy určeno jejich prvním číslem, v případě
shody prvního čísla jejich druhým číslem, v případě shody i na druhém místě třetím číslem,
atd. Pro zadanou hodnotu N a danou permutaci N čísel určete permutaci bezprostředně
následující v lexikografickém uspořádání.
Řešení úlohy předvádí následující program. Využívá pomocnou proceduru Prohod, která
provádí vzájemnou záměnu dvou prvků v poli, a pomocnou proceduru Prevrat, která určený
úsek v poli zrcadlově převrátí. Funkce Naslednik pak řeší celou naši úlohu
program NaslPerm;
{následující permutace v lexikografickém uspořádání}
const Max = 10;
type Pole = array[1..Max] of byte;
var P: Pole;
i, N: byte;
procedure Prohod(var P: Pole; x, y: byte);
{vzájemná záměna dvou prvků v poli P}
var z: byte;
begin z:=P[x]; P[x]:=P[y]; P[y]:=z end;
procedure Prevrat(var P: Pole; x, y: byte);
{zrcadlově převrátí úsek pole P mezi indexy x, y včetně}
var z: byte;
begin
while x < y do
begin Prohod(P, x, y); inc(x); dec(y) end;
end;
function Naslednik(var A: Pole; N: byte): boolean;
{najde lexikograficky následující permutaci N čísel
k permutaci uložené v poli A;
funkční hodnota = zda existuje}
var i, j: byte;
begin
i:=N;
while (i > 1) and (A[i-1] > A[i]) do dec(i);
if i = 1 then
begin Naslednik:=false; exit end;
j:=i;
while (j <= N) and (A[j] > A[i-1]) do inc(j);
Prohod(A, i-1, j-1);
Prevrat(A, i, N);
end;
51
begin
write('Zadej počet čísel: ');
readln(N);
write('Zadej permutaci: ');
for i:= 1 to N do read(P[i]);
writeln;
if Naslednik(P, N) then
begin
write('Následující permutace: ');
for i:=1 to N do write(P[i]:2)
end
else
write('Následující permutace neexistuje');
writeln
end.
52
9. Znaky a znakové řetězce
Znaky
- standardní typ char
var Z, W: char;
- znakové konstanty se zapisují v apostrofech, např. ‘a’, ‘+’, ‘ ’ (znak mezera)
- proměnná zabírá 1 byte, obsahuje kód příslušného znaku
- v implementacích se obvykle používá kódová tabulka ASCII
0-31
speciální řídicí znaky
32-127
základní část znakové sady
128-255
národní abecedy resp. semigrafika
- dekadické číslice – souvislá řada v pořadí od ‘0’ do ‘9’
- velká písmena anglické abecedy – souvislá řada od ‘A’ do ‘Z’
- malá písmena anglické abecedy – souvislá řada od ‘a’ do ‘z’
- znakové konstanty lze zapisovat i kódem, např. #65 (znamená totéž co ‘A’)
nebo #27 (klávesa Esc)
- lze používat v procedurách read, write
např. read(Z); write(‘Z’);
POZOR – v příkladu výše rozlišovat Z a ‘Z’ !
- do proměnné typu char lze dosazovat, např. W:=‘?’; Z:=W;
- na typu char je definováno uspořádání (podle kódů),
je možné používat relační operátory =, <, >, <=, >=, <>
if (Z>=‘A’) and (Z<=‘Z’) then …
{hodnotou proměnné Z je velké písmeno anglické abecedy}
while Z <> W do ...
{dokud mají proměnné Z a W různou hodnotu …}
Standardní funkce
předpokládejme deklaraci
B := ord(Z);
Z := chr(B);
var Z, Z1: char; B: byte;
vrací kód znaku Z v ASCII-tabulce (ordinální hodnotu)
k zadanému ASCII-kódu vrací příslušný znak
- funkce navzájem inverzní – tedy chr(ord(Z)) = Z
- z hlediska syntaxe jazyka jde o přetypování
- v kódu se „nic neděje“ (znak je v programu reprezentován svým kódem)
Použití:
B:=ord(Z) – ord(‘0’);
Z:=chr(B + ord(‘0’));
{cifra → její hodnota}
{hodnota 0..9 → cifra}
53
Z1 := UpCase(Z)
malá písmena anglické abecedy změní na velká, ostatní znaky ponechá beze změny
Použití:
if UpCase(Z) = ‘A’ then …
místo delšího zápisu
if (Z=‘A’) or (Z=‘a’) then …
Příklad: vstup čísla po znacích
- co přibližně dělá procedura read při čtení celého čísla ze vstupu
- algoritmus: Hornerovo schéma
- pro jednoduchost předpokládáme korektní vstup, bez vedoucích mezer
var Zn: char;
{čtené znaky}
Hodn: integer; {číselná hodnota}
...
Hodn:=0;
read(Zn);
while (Zn >= ‘0’) and (Zn <= ‘9’) do
begin
Hodn := Hodn*10 + ord(Zn) – ord(‘0’);
read(Zn)
end;
{výsledná hodnota je uložena v proměnné Hodn}
Znakové řetězce
- standardní typ string
type JmenoTypu = string [N];
N – celočíselná konstanta udávající maximální délku stringu
N je nejvýše rovno 255
pokud N neuvedeme, implicitní hodnota je 255
Příklad:
type JmenoMesice = string[8];
var Mesic: JmenoMesice; {proměnná pro řetězce max. 8 znaků}
S: string;
{proměnná pro řetězce max. 255 znaků}
Reprezentace proměnné:
- jednorozměrné pole znaků indexované od 1 do N
- vlastní evidence aktuální délky uloženého řetězce
(v bytu s indexem 0 – pozor při manipulaci, formálně je typu char)
Konstanty:
‘duben’
‘?’
‘’
řetězec délky 5 znaků
řetězec délky 1 znak (jako char)
prázdný řetězec (žádný znak)
54
Operace se stringy:
- do proměnné lze dosazovat, např. Mesic := ‘duben’;
→ nastaví se tím aktuální délka (zde na 5)
- jediný operátor „+“ znamená zřetězení, např. po provedení
S := ‘12. ’ + Mesic;
bude mít proměnná S hodnotu ‘12. duben’ a aktuální délku 9
- lze používat v procedurách read, write
read(S);
- načte tolik znaků, kolik je maximální délka S,
nejvýše však do konce řádku na vstupu
write(S);
- vypíše tolik znaků, kolik je aktuální délka S
Doporučení: Při čtení používat raději readln(S) – přijdeme sice případně o znaky, které se
nevešly do maximální délky S, zato při následujícím čtení budeme číst od začátku dalšího
řádku. Jinak při čtení dalšího stringu ze vstupu načteme prázdný řetězec!
Standardní procedury a funkce se znakovými řetězci
Length(S) → aktuální délka řetězce
Concat(S1, S2, …, Sn) → spojení řetězců za sebe
totéž se snáze zapíše operátorem “+”:
S1 + S2 + … + Sn
Copy(S, Index, Pocet) → vykopírování podřetězce dané délky počínaje od daného indexu
Delete(S, Index, Pocet) … v řetězci S zruší podřetězec dané délky počínaje od daného indexu
Insert(Co, Kam, Index) … do řetězce Kam vloží Co na pozici daného indexu
Pos(Co, Kde) → pozice prvního výskytu podřetězce Co v řetězci Kde
(vrací 0, když tam podřetězec není obsažen)
Indexování:
S[i] = i-tý znak řetězce S, je typu char
např. S[2] := ‘5’;
for I:=1 to length(S) do
if S[I] = ‘?’ then S[I] := ‘!’;
{v řetězci S nahradí všechny otazníky vykřičníkem}
POZOR – při indexování stringu změny neovlivňují aktuální délku:
S:=‘ABC’; {aktuální délka S je 3}
for I:= 1 to 10 do S[I]:=‘Z’;
{do S se sice vloží 10 znaků,
ale aktuální délka S zůstává nastavena na 3}
write(S);
{vypíše ‘ZZZ’}
55
Uspořádání stringů
- lexikografické, indukované uspořádáním na typu char
‘4’ < ‘Z’ < ‘f’ < ‘fa’ < ‘fb’ < ‘g’ < ‘č’ < ‘á’
- je možné používat relační operátory = < > <= >= <>
Příklad: načtení dlouhého čísla (kladné celé, max. 100 cifer)
type Cislo = array [1..100] of byte;
var A: Cislo;
{A[1]…cifra v řádu jednotek}
PA: byte;
{počet cifer}
S: string[100];
I: integer;
readln(S);
PA := 0;
for I:=length(S) downto 1 do
begin
inc(PA);
A[PA] := ord(S[I])-ord(‘0’)
end;
Příklad: číselné soustavy
- převod z dvojkové soustavy na číselnou hodnotu
- algoritmus: Hornerovo schéma
110010 ≈ 1.25 + 1.24 + 0.23 + 0.22 + 1.21 + 0.20 =
= ((((1.2 + 1).2 + 0).2 + 0).2 + 1).2 + 0 = 50
program Bin_Dec;
{převod čísla z dvojkové soustavy - Hornerovo schéma}
var S: string[15]; {dvojkový zápis čísla}
N: integer;
{jeho hodnota}
I: integer;
begin
read(S);
N:=0;
for I:= 1 to length(S) do
N:=N*2 + ord(S[I])-ord('0');
writeln('Hodnota: ', N)
end.
- převod číselné hodnoty do dvojkové soustavy
- algoritmus: Hornerovo schéma využité v opačném směru
posloupnost zbytků při celočíselném dělení dvěma tvoří odzadu dvojkový zápis čísla
→ připojování dvojkových cifer do stringu zleva
56
50 : 2 = 25, zb. 0
6 : 2 = 3, zb. 0
25 : 2 = 12, zb. 1
3 : 2 = 1, zb. 1
12 : 2 = 6, zb. 0
1 : 2 = 0, zb. 1
program Dec_Bin;
{převod čísla do dvojkové soustavy
- obrácené Hornerovo schéma}
var S: string[15]; {dvojkový zápis čísla}
N: integer;
{jeho hodnota}
begin
read(N);
S:='';
{prázdný řetězec}
while N > 0 do
begin
if odd(N) then S:='1'+S
else S:='0'+S;
N:=N div 2
end;
writeln('Dvojkový zápis čísla: ', S)
end.
Příklad: převod do jiné poziční číselné soustavy a zpět – provádí se analogicky
program Hex_Dec;
{převod čísla z šestnáctkové soustavy - Hornerovo schéma}
var S: string[15]; {šestnáctkový zápis čísla}
N: integer;
{jeho hodnota}
I: integer;
begin
read(S);
N:=0;
for I:= 1 to length(S) do
begin
if (S[I] >= '0') and (S[I] <= '9') then
N:=N*16 + ord(S[I])-ord('0')
else
N:=N*16 + ord(S[I])-ord('A') + 10;
end;
writeln('Hodnota: ', N)
end.
program Dec_Hex;
{převod čísla do šestnáctkové soustavy
- obrácené Hornerovo schéma}
var S: string[15]; {šestnáctkový zápis čísla}
N, Z: integer; {N - jeho hodnota}
begin
read(N);
S:='';
{prázdný řetězec}
while N>0 do
57
begin
Z:=N mod 16;
if (Z > 9) then S:=chr(Z-10+ord('A')) + S
else S:=chr(Z+ord('0')) + S;
N:=N div 16;
end;
writeln('Hodnota: ', S)
end.
Konverzní procedury
Str(V, S)
- konverze číselná hodnota V → string S
- V může být výraz typu integer nebo real
- součástí V může být formátování V:n resp. V:n:m jako u write
- volání Str se implicitně provádí v proceduře write (zápis čísla)
Val(S, V, ErrCode)
- konverze string S → číselná hodnota V
- V může být proměnná typu integer nebo real
- ErrCode=0 … převod se povedl bez chyby
- ErrCode>0 … pozice výskytu chyby (index v S)
- volání Val se implicitně provádí v proceduře read (čtení čísla)
58
10. Záznamy a soubory
Textový soubor
- data uložena jako posloupnost ASCII-kódů jednotlivých znaků
- lze číst a vytvářet v textovém editoru, čitelné pro člověka
(na rozdíl od binárních souborů – budou později)
- při čtení (zápisu) čísel se automaticky provádí konverze z (do) textové podoby
do (z) vnitřního tvaru – jako implicitní volání konverzních procedur Val a Str
- soubor je vždy otevřen jen pro čtení nebo jen pro zápis
- výhradně sekvenční přístup – čte (zapisuje) se postupně od začátku
- standardní vstup a výstup dat (z klávesnice, na obrazovku) jsou jen zvláštním případem
textových souborů (tzv. pseudosoubory)
1. deklarace
var T: text;
2. přiřazení assign(T, S);
- S je výraz typu string (často konstanta nebo proměnná)
- určuje fyzickou adresu souboru na disku, např. assign(T, ‘C:\Data\Vstupni1.txt’);
3. otevření
reset(T);
rewrite(T);
append(T);
- pro čtení – soubor musí existovat!
- pro zápis – vytváření nového
- pro zápis – připsání na konec existujícího souboru
4. operace vstupu a výstupu
read(T, …); readln(T); write(T, …); writeln(T); write(T, A:n, R:n:m);
- již známe pro standardní vstup a výstup,
jenom navíc jako první parametr se uvede jméno souboru
funkce typu boolean
eof(T) – test na konec souboru
eoln(T) – test na konec řádku
seekeof(T) – test na konec souboru až na „bílé znaky“,
které při testování přeskočí
seekeoln(T) – test na konec řádku až na „bílé znaky“
které při testování přeskočí
5. zavření
close(T);
Poznámky:
- jeden soubor lze v programu otevřít postupně vícekrát (několikrát za sebou ho číst nebo
třeba nejdříve ho vytvořit a pak po sobě číst)
- pokud soubor existuje, provedením rewrite je nemilosrdně smazán (bez ověření dotazem)
- při čtení čísel používat seekeof, seekeoln namísto běžných funkcí eof, eoln (pozor na
případné „bílé znaky“ za posledním číslem; typicky za posledním číslem v souboru bývá ještě
konec řádku)
- soubory vždy zavírat (uvolnění systémových prostředků, jistota zápisu dat z vyrovnávací
paměti na disk)
- předdefinované proměnné input a output typu text spojené s klávesnicí a obrazovkou se
automaticky doplňují do všech příkazů, v nichž není uvedeno jméno souboru
59
- funkci eof lze použít i pro vstup dat z klávesnice (tzn. pro input, bez parametru), zadávání
dat z klávesnice pak ale musí uživatel explicitně ukončit znakem EOF = #26 (pomocí Ctrl+Z)
- pozor na čtení dat, když už eof(T) = true
Chyby při I/O operacích
= chyby při provádění operací se soubory, např. pokus o otevření neexistujícího souboru pro
čtení nebo při pokusu o vstup čísla se ze souboru přečtou jiné znaky než číslice
- reakce podle nastavení přepínače $I:
{$I+} provádí se kontrola při výpočtu → běhová chyba
(standardní výchozí nastavení)
{$I-} úspěšnost poslední I/O operace je programu pouze oznámena
→ funkce IOResult typu integer:
0 = výsledek bez chyby
nenulová hodnota = vrací kód chyby
Doporučení:
- automatickou detekci I/O chyb vypínat jen pro mimořádné účely
- při vypnuté kontrole {$I-} volat po každé I/O operaci IOResult (nastala-li chyba, všechny
další I/O operace se ignorují až do zavolání funkce IOResult)
Příklad využití přepínače {$I-}
...
var Soubor: Text;
Jmeno: string[50];
...
begin
write(‘Zadej jméno souboru:’);
readln(Jmeno);
assign(Soubor, Jmeno);
{$I-} reset(Soubor); {$I+}
while IOResult <> 0 do
begin
writeln(‘Soubor ’, Jmeno, ‘ neexistuje!’);
write(‘Zadej nové jméno souboru:’);
readln(Jmeno);
assign(Soubor, Jmeno);
{$I-} reset(Soubor); {$I+}
end;
Záznam
- strukturovaný datový typ
- co patří logicky k sobě, ať je u sebe i deklarováno
- jednotlivé položky záznamu mohou být různých typů
(libovolných, opět třeba i strukturovaných)
- položky záznamu se nedají indexovat jako v poli, mají svá vlastní jména (identifikátory)
- jména jednoznačná v rámci záznamu, ale ne vůči „okolnímu světu“
- popis položek se řídí stejnými syntaktickými pravidly jako deklarace proměnných
60
type JménoTypu = record
Položka1: TypPoložky1;
Položka2: TypPoložky2;
…
PoložkaN: TypPoložkyN
end;
Příklady použití:
type Datum = record
Den, Mesic, Rok: word
end;
var Dnes, Zitra: Datum;
type Zamestnanec = record
Jmeno: string[20];
Plat: word;
Narozen: Datum;
Deti: array[1..10] of string[20];
end;
var Alois: Zamestnanec;
Z: array[1..1000] of Zamestnanec;
Operace
S proměnnou typu záznam lze jako s celkem provádět jedinou operaci, a to dosazení mezi
dvěma proměnnými téhož typu:
Dnes:=Zitra;
Z[3]:=Alois;
Přístup ke složkám pomocí tečkové notace:
JménoZáznamu.JménoPoložky
Se složkou záznamu se pak manipuluje stejně jako s každou jinou proměnnou příslušného
typu.
Dnes.Den:=31;
Dnes.Mesic:=12;
read(Alois.Jmeno);
Suma:=Suma + Alois.Plat*2;
Z[3].Narozen.Rok:=1945;
Z[3].Deti[1]:=‘Pepicek’;
Příklad: reprezentace polynomu
an xn + an-1 xn-1 + an-2 xn-2… + a1 x + a0
Dvě varianty:
1. ukládáme všechny členy polynomu včetně nulových, exponent slouží jako index v poli
(→ snadná manipulace)
61
2.
ukládáme
pouze
nenulové
členy,
exponent
se
ukládá
do
pole
společně s koeficientem (vhodné pro „řídké“ polynomy, tj. polynomy vysokého stupně
s malým počtem nenulových členů)
type Polynom1 = record
Stupen: word; {stupeň polynomu}
Koeficient: array[0..MaxStupen] of real
end;
type Polynom2 = record
Pocet: word; {počet nenulových členů}
Clen: array[0..MaxPocet] of
record Koef: real; Exp: word end;
end;
Inicializovaná proměnná typu záznam
const LetosniPrvniMaj: Datum = (Den: 1; Mesic: 5; Rok: 2004);
type Complex = record
X, Y: real
end;
const Z: Complex = (X: 2.0; Y: 3.5);
Příkaz with
- použití: pro snadnější přístup k více položkám téhož záznamu
- syntaxe: with JménoZáznamu do Příkaz
- sémantika: v rámci Příkazu se před každý identifikátor, kde to má syntaktický smysl, jakoby
přidá na začátek tečkou oddělené JménoZáznamu
with Z[1] do read(Jmeno, Plat, Narozen.Den,
Narozen.Mesic, Narozen.Rok);
with Alois do begin
Jmeno:=‘Alois Jirasek’;
Plat:= 10000;
Deti[1]:=‘Kaspar’;
Deti[2]:=‘Melichar’;
Deti[3]:=‘Baltazar’
end;
62
Binární soubor (datový, typovaný)
- na rozdíl od textových souborů jsou data uložena binárně (ve vnitřním tvaru jako
v proměnných programu) → není čitelný pro člověka
- všechny položky souboru musí být téhož typu (typ položek může být i strukturovaný, často
záznam)
- vedle sekvenčního přístupu je možný i přímý přístup (přístup ke konkrétnímu záznamu
podle pořadového čísla – jako „indexování“)
- možnost provádět změny v souboru (operace „update“)
- není řádková struktura (neexistuje readln, writeln, eoln, …)
1. deklarace var F: file of T;
T je libovolný typ = typ ukládaných položek (záznamů)
2. přiřazení assign(F, S);
stejné jako u textových souborů
- soubor musí existovat, hlava nastavena na první záznam
3. otevření reset(F);
rewrite(F);
- vytváření nového souboru (případný starý soubor smazán)
v obou případech je soubor otevřen pro čtení i pro zápis
4. operace vstupu a výstupu
read(F, X); write(F, X) X je proměnná odpovídajícího typu T
- procedury read, write mají vždy právě dva parametry
- po provedení se posune čtecí hlava (default sekvenční přístup)
funkce typu boolean
eof(F) → test, zda je konec souboru
přímý přístup:
seek(F, n) – nastavení hlavy na záznam číslo n (záznamy souboru se číslují od 0)
FilePos(F) → aktuální číslo záznamu (kde je právě čtecí hlava)
FileSize(F) → počet záznamů v souboru
5. zavření
close(T);
stejné jako u textových souborů
Příklady využití přímého přístupu
Změna záznamu číslo N v souboru F:
seek(F, N);
read(F, X);
úprava hodnoty proměnné X
seek(F, N);
- nutno vrátit čtecí hlavu na její původní místo !!!
write(F, X);
63
Přidání nového záznamu X na konec souboru:
seek(F, FileSize(F));
write(F, X);
- záznamy se číslují od 0, takže FileSize(F) je číslo prvního volného místa za posledním
platným záznamem v souboru F
- je to zároveň nejvyšší povolená hodnota druhého parametru procedury seek
Vnější třídění = třídění souborů
Úloha: setřídit rozsáhlá data uložená v souboru, která se nevejdou do pole a nelze tedy pro
jejich uspořádání použít některý z algoritmů vnitřního třídění.
Základní algoritmus: slévání (merge)
- ze dvou setříděných souborů vytvoří jeden setříděný soubor v čase lineárně závislém na
počtu všech slévaných čísel
12 16 20 21 28 37 50
13 15 25 32 40 42 48
→ 12 13 15 16 20 21 25 28 32 37 40 42 48 50
Princip vnějšího třídění: setříděné úseky uložené v souborech se postupně slévají do větších a
větších úseků, až vnikne jediný setříděný soubor obsahující všechna data
Výchozí úseky:
- délky 1 (přímé slučování)
v jednotlivých krocích výpočtu z nich postupně vznikají uspořádané dvojice, čtveřice, osmice,
… atd., v K-tém kroku výpočtu mají uspořádané úseky délku 2K
- přirozeně existující (přirozené slučování)
v posloupnosti
4 7 20 15 18 10 6 14 20 27 22 24 17 3 8
existují přirozené rostoucí sekvence
4 7 20
15 18
10
6 14 20 27
22 24
17
3 8
- předtřídit úseky v poli některým algoritmem vnitřního třídění
→ zrychlení výpočtu (odpadne několik prvních kroků vnějšího třídění)
Organizace práce:
- teoreticky by mohl být každý úsek uložen v jednom v souboru
→ existuje pak ale mnoho souborů, proto nevhodné!!!
- všechny úseky za sebou v jednom souboru
fáze rozdělovací – úseky se rozdělí střídavě do dvou souborů
fáze slučovací – úseky se po dvou slévají a ukládají se do jednoho výsledného souboru
→ dvoufázové třídění – v každém kroku výpočtu je každé číslo dvakrát čteno
a dvakrát zapisováno do souboru
64
- zrychlení výpočtu: jednofázové třídění
– při slučování jsou setříděné úseky rovnou ukládány střídavě do dvou souborů
(odpadne tedy samostatná rozdělovací fáze, každé číslo je v každém kroku výpočtu
čteno a zapisováno jen jednou)
Časová složitost:
- třídíme N záznamů
- podstatný je počet provedených vstupních a výstupních operací (tj. čtení ze souboru a zápis
do souboru), porovnávací operace vykonávané ve vnitřní paměti jsou řádově rychlejší
- v každém kroku výpočtu je každý záznam jednu nebo dvakrát čten a zapisován
→ jeden krok má vždy časovou složitost O(N)
- přímé slučování: po K-tém kroku výpočtu mají úseky délku 2K,
rovnost 2K=N nastane pro K=log2N, tedy potřebný počet kroků výpočtu je O(log N)
→ časová složitost celého algoritmu O(N.log N)
- přirozené slučování je v průměru o něco rychlejší, ale v nejhorším případě stejné jako přímé
slučování (vstupní data mohou být uspořádána sestupně)
Možnosti zrychlení:
- předtřídění počátečních úseků v poli
* je s ním spojena zároveň rozdělovací fáze 1. kroku jednofázového třídění
* co největší délka úseků, kolik nám dovolí vnitřní paměť
* lze vytvářet i delší úseky – heapsort s postupným doplňováním haldy,
resp. se dvěma haldami umístěnými v poli proti sobě
→ časová složitost N.log2X, kde X je výchozí počet úseků, tj. stále O(N.log N)
- jednofázové třídění namísto dvoufázového
→ poloviční počet vstupních a výstupních operací
- vyšší stupeň slučování K
* tzn. při jednofázovém třídění sléváme z K vstupních do K výstupních souborů
→ časová složitost N.logKN, tj. stále O(N.log N)
Implementace jádra vnějšího třídění – slévání dvou setříděných souborů
Ukázkové programy pracují s textovými soubory, stejný postup samozřejmě funguje i
v případě použití datových souborů.
Dvě verze řešení: První verze má delší zápis a je zcela obecná, druhé verze má kratší zápis za
cenu toho, že hodnotu maxint využívá jako technickou (nesmí být obsažena mezi tříděnými
daty v souborech).
65
program Merge_1;
{Spojení dvou setříděných souborů do jednoho setříděného
souboru.
Vstup: dva vzestupně uspořádané textové soubory čísel typu
integer, čísla jsou v souboru oddělena mezerami nebo konci
řádku.
Výstup: jeden vzestupně uspořádaný textový soubor čísel typu
integer, čísla jsou v souboru oddělena mezerami.}
var A1, A2, B: text;
C1, C2: integer;
E1, E2: boolean;
{dva vstupní a jeden výstupní soubor}
{čísla načtená ze vstupních souborů}
{příznak, zda všechna čísla ze souboru
byla již zapsána do výstupního souboru}
begin
assign(A1,'A1.txt'); reset(A1);
assign(A2,'A2.txt'); reset(A2);
assign(B,'B.txt'); rewrite(B);
E1 := seekeof(A1);
E2 := seekeof(A2);
read(A1, C1);
{načteme první číslo z každého souboru}
read(A2, C2);
while not (E1 or E2) do {ještě je třeba slévat oba soubory}
if C1 < C2 then
begin
write(B, C1, ' ');
if seekeof(A1) then E1 := true else read(A1, C1);
end
else
begin
write(B, C2, ' ');
if seekeof(A2) then E2 := true else read(A2, C2);
end;
while not E1 do
{v souboru A1 ještě zbývají čísla}
begin
write(B, C1, ' ');
if seekeof(A1) then E1 := true else read(A1, C1);
end;
while not E2 do
{v souboru A2 ještě zbývají čísla}
begin
write(B, C2, ' ');
if seekeof(A2) then E2 := true else read(A2, C2);
end;
close(A1);
close(A2);
close(B);
end.
66
program Merge_2;
{Spojení dvou setříděných souborů do jednoho setříděného
souboru.
Vstup: dva vzestupně uspořádané textové soubory čísel typu
integer, čísla jsou v souboru oddělena mezerami nebo konci
řádku.
Výstup: jeden vzestupně uspořádaný textový soubor čísel typu
integer, čísla jsou v souboru oddělena mezerami.}
var A1, A2, B: text; {dva vstupní a jeden výstupní soubor}
C1, C2: integer; {čísla načtená ze vstupních souborů}
begin
assign(A1,'A1.txt'); reset(A1);
assign(A2,'A2.txt'); reset(A2);
assign(B,'B.txt'); rewrite(B);
if seekeof(A1) then C1:=maxint else read(A1, C1);
if seekeof(A2) then C2:=maxint else read(A2, C2);
while (C1 <> maxint) or (C2 <> maxint) do
if C1 < C2 then
begin
write(B, C1, ' ');
if seekeof(A1) then C1 := maxint else read(A1, C1);
end
else
begin
write(B, C2, ' ');
if seekeof(A2) then C2 := maxint else read(A2, C2);
end;
close(A1);
close(A2);
close(B);
end.
67
11. Halda a heapsort
Halda (heap)
- datová struktura pro uložení datových záznamů podle svých klíčů
- binární strom
- zcela zaplněné hladiny až do předposlední, poslední hladina zaplněná souvisle zleva
- uspořádání hodnot (klíčů) ve všech uzlech: otec < syn
(důsledek: v kořeni uložena nejmenší hodnota ze všech)
Použití
pokud s uloženými záznamy potřebujeme provádět operace:
- určení minima (záznamu s nejmenším klíčem)
- přidání nového prvku (datového záznamu)
- odebrání minima (záznamu s nejmenším klíčem)
→ haldové operace
Efektivita operací
- určení minima: konstantní časová složitost
- přidání a odebrání prvku: logaritmická časová složitost O(log N)
počet kroků = výška stromu
Operace
Přidání prvku:
- nový uzel přidat do haldy na poslední hladinu co nejvíce vlevo
- do nového uzlu vložit přidávanou hodnotu
- novou hodnotu postupně zaměňovat vždy s hodnotou uloženou v jejím otci, dokud je třeba
(tzn. dokud je otec větší)
Odebrání minima:
- odebrat minimum z kořenu haldy
- do kořenu vložit hodnotu z posledního uzlu haldy (uzel v poslední hladině co nejvíce
vpravo), tento uzel zrušit
- přesunutou hodnotu postupně zaměňovat vždy s hodnotou uloženou v jejím synovi, dokud je
třeba (tzn. dokud je syn menší; mají-li menší hodnotu oba synové, tak zaměnit s menším
z obou synů)
Realizace haldy v poli
- jednorozměrné pole ukládaných záznamů, indexované od 1
- obsah haldy je v poli uložen po vrstvách vždy zleva doprava
(tedy kořen haldy má index 1)
- uzel s indexem i má syny uložené v poli na indexech 2i, 2i+1
(tedy uzel s indexem i má otce uloženého v poli na indexu i div 2)
type Halda = record
Data: array[1..Max] of integer;
{pro jednoduchost halda čísel}
Pocet: 0..Max
end;
68
procedure Pridej (var H: Halda; X: integer);
{Přidání hodnoty X do haldy H}
var j,p,d: integer;
Pokracovat: boolean;
begin
with H do
if Pocet = Max then
Error
else
begin
Pocet := Pocet+1;
Data[Pocet] := X;
j := Pocet;
Pokracovat := j > 1;
while Pokracovat do
begin
p := j div 2;
if Data[j] < Data[p] then
begin
d := Data[j];
Data[j] := Data[p];
Data[p] := d;
j := p;
Pokracovat := j > 1
end
else
Pokracovat := false
end
end
end; {Pridej}
procedure ZrusMin (var H: Halda);
{Vypuštění minimální hodnoty z haldy H}
var j,n,d: integer;
Pokracovat: boolean;
begin
with H do
if Pocet = 0 then
Error
else
begin
Data[1] := Data[Pocet];
Pocet := Pocet-1;
j := 1;
Pokracovat := 2 <= Pocet;
while Pokracovat do
begin
n := 2*j;
if n < Pocet then
if Data[n+1] < Data[n] then n:=n+1;
69
if Data[j] > Data[n] then
begin
d := Data[j];
Data[j] := Data[n];
Data[n] := d;
j := n;
Pokracovat := 2*j <= Počet
end
else
Pokracovat := false
end
end
end; {ZrusMin}
Postavení haldy
- začneme s prázdnou haldou
- N-krát zopakujeme operaci „přidej prvek do haldy“
→ celková časová složitost sestrojení haldy O(N.log N).
- hodně uzlů (alespoň celá druhá polovina) může absolvovat maximální možný počet
výměn log N, jenom menší počet uzlů (ze začátku) má méně porovnání
Postavení haldy zdola (v lineárním čase)
- výchozí rozložení dat představuje úplný binární strom hloubky d
(bez uspořádání hodnot do haldy)
- nejprve postavíme „haldy“ z podstromů, jejichž kořeny mají hloubku d-1, potom pro d-2, …
atd., až do kořene celé haldy
- stavění hald se provádí záměnami hodnot od kořene k listům (výměna s menším z obou
synů)
hloubka
0
1
…
j
…
d-1
počet uzlů
20
21
…
2j
…
2d-1
max. počet výměn
pro každý z nich
d
d-1
…
d-j
…
1
Při tomto postupu konstrukce haldy má hodně uzlů malý maximální počet výměn a jen málo
z nich může absolvovat výměn hodně → celková časová složitost sestrojení haldy je O(N).
70
Heapsort (třídění haldou, haldové třídění)
- z prvků postavit haldu (N x přidání prvku do haldy)
→ časová složitost O(N.log N) nebo zdola v lineárním čase O(N)
- haldu postupně rozebrat (N x odebrat minimum z haldy)
→ časová složitost O(N.log N)
→ tedy celková časová složitost O(N.log N) i v nejhorším případě
Třídí „na místě“ (tzn. nepotřebuje další datovou strukturu velikosti N):
- prvky uložené v poli postupně řadí do haldy, přičemž haldu staví v levé části téhož pole
- pak rozebírá postupně haldu a vyřazované prvky ukládá postupně do pravé části téhož pole,
kde se uvolňuje místo po zkracující se haldě
71
12. Dodatky
Pseudonáhodná čísla
= algoritmicky generovaná náhrada za náhodná čísla
Použití:
- náhodnost při rozhodování např. ve hrách (výběr z více možných stejně dobrých tahů v dané
pozici, házecí kostka)
- generování rozsáhlých testovacích dat
- výpočetní metody typu Monte Carlo
Generátor pseudonáhodných čísel
- algoritmus, který na základě předchozí hodnoty určí další náhodné číslo v posloupnosti
- existuje teorie, jak je vytvářet, my využijeme standardní generátor
- při volání generátoru lze zvolit, zda chceme číslo celé či reálné a z jakého rozmezí hodnot
Generátor pseudonáhodných čísel (např. v Turbo Pascalu)
RandSeed – standardní proměnná typu longint
= „semínko“ generátoru, výchozí hodnota pro algoritmus
Random – funkce volání generátoru
- spočítá výslednou hodnotu na základě RandSeed, zároveň nadefinuje novu hodnotu
proměnné RandSeed pro další volání.
Dvě možnosti volání:
- volání bez parametru → hodnota typu real z intervalu <0,1)
- volání Random(N) → hodnota typu word z intervalu <0,N-1>
Randomize – procedura pro inicializaci hodnoty RandSeed na základě aktuální hodnoty
systémového času
Inicializace generátoru
- provádí se jen jednou na začátku programu.
Dvě možnosti:
1. Randomize;
→ při každém běhu programu jiná série náhodných čísel (většinou požadovaný cílový stav)
2. RandSeed := VýchozíHodnota;
→ pokaždé stejná série náhodných čísel
použití: dočasně při ladění programu, trvale při šifrování dat apod.
Pseudonáhodná čísla z jiného rozmezí
- vynásobením změnit rozsah u typu real, přičtením posunout rozsah
Příklady:
Random(6)+1
Random*20 - 10
běžná házecí kostka
reálná čísla z rozmezí od -10 do 10
72
Návrh a vytváření programu
- shora:
Začínáme „kostrou“ programu, píšeme jenom to podstatné, nerozptylujeme se zbytečnými
detaily.
Pomocné dílčí akce zatím odbudeme voláním procedury, která vykoná požadovanou činnost –
ještě ji nemáme, víme jen co by měla dělat, ale nevíme, jak to bude dělat (ale to nevadí, však
on ji pak někdo dopíše, v nejhorším my sami).
Program postupně zjemňujeme, doplňujeme do něj dříve vynechané procedury.
- zdola:
Nejprve si napíšeme procedury realizující dílčí akce, které budou v budoucím programu
zapotřebí. S jejich pomocí naprogramujeme procedury realizující větší celky atd., až budeme
mít celý program.
Ladění programu
- shora:
Nečekáme na celý program, ladíme ho průběžně během vytváření (tzn. nejdříve jeho kostru).
Zatím chybějící procedury nahradíme provizorními procedurami, které sice nevykonávají
potřebnou akci, ale dávají nějaký triviální výstup (třeba pevně zvolenou hodnotu)
v požadovaném tvaru.
- zdola:
Nečekáme na celý program, ladíme ho průběžně během vytváření (tzn. nejdříve dílčí
procedury). Pro otestování správné funkce jednotlivých procedur si vytváříme pomocné
testovací programy, které procedury volají se zvolenými parametry a vypisují (případně i
testují) jejich výstupy.
73
Download

studijní text k přednáškám