Algoritmus
Definice
· matematika - základní pojem, nedefinuje se
· jednoznačně stanovená posloupnost operací, které řeší daný problém
· obecná pravidla určující postupnou transformaci vstupních údajů na výstupní
Specifikace algoritmické úlohy
Vstupní údaje - informace, ze kterých při řešení úlohy vycházíme, musí splňovat vstupní podmínku
Výstupní údaje - nově získané informace, které jsou výsledkem realizace algoritmu, musí splňovat výstupní podmínku
Vlastnosti algoritmu
· DETERMINOVANOST - v každém kroku musí být jednoznačně určeno, co se má provést (přesnost, srozumitelnost)
· HROMADNOST - algoritmus řeší skupinu úloh pro různé vstupní údaje
· REZULTATIVNOST - proces je konečný a vede k získání správného výsledku
Správnost algoritmu
Algoritmus je správný tehdy, když pro všechny údaje splňující vstupní podmínku se proces zastaví a výstupní údaje splňují výstupní podmínku.
Ověření správnosti
· důkazové metody
· testování - testovací tabulky - ručně, trasování na počítači
· praxe u komerčních programů - souběžný ruční a strojový provoz po určitou dobu, beta verze programů
TESTOVACÍ (TRASOVACÍ, SLEDOVACÍ, SIMULAČNÍ) TABULKY
zachycují transformaci hodnot proměnných v průběhu realizace algoritmu, nejedná se o důkaz algoritmu
Efektivnost algoritmu
Ekvivalentní algoritmy
řeší tutéž úlohu, vybíráme efektivnější, nelze stanovit jednoznačně jeden nejlepší
Efektivita
časová - spotřeba času, důležitější
paměťová - spotřeba paměti
přehlednost a srozumitelnost
Způsoby zápisu algoritmu
· slovní
· grafický (VD, struktogram, kopenogram, ...)
· program
Vývojové diagramy
spojka
spojnice, šipky
Etapy řešení algoritmické úlohy
odlišnost pro malé a velké programy, začátečníky a profesionály
1. Zadání
2. Rozbor, analýza
specifikace
vstupy - identifikátor, popis, typ proměnné, vstupní podmínky
výstupy - identifikátor, popis, typ proměnné
(další proměnné)
3. Algoritmus
výv. diagram
4. Testování
5. Přepis do progr. jazyka (kódování)
6. Ladění
chyby syntaktické a logické
7. Optimalizace
efektivita - paměťová a časová, přehlednost
uživatelská úprava - testování vstupů, vzhled programu
8. Dokumentace
programátorská a uživatelská (manuály, ref. příručky, učebnice - tištěné a elektronické, helpy, ...)
Program Čtverec
Sestavte program pro výpočet obvodu a obsahu čtverce o straně a.
Specifikace:
Vstupy:
A velikost strany čtverce real, A>0
Výstupy:
OBVOD obvod čtverce real
OBSAH obsah čtverce real
Pom. proměnné: 0
Vývojový diagram
Testování algoritmu
připravený příklad (příklady)
3®12,9
Program
přepis do programovacího jazyka - ano
DÚ - obdélník (obsah)
Sestavte program pro výpočet obsahu obdélníka o stranách a, b.
Struktura programu v jazyce Pascal
1. hlavička
2. deklarační část
3. příkazová část
Hlavička
program identifikátor;
nemusí být uvedeno, je vhodné uvádět
standardní Pascal vyžaduje navíc za identifikátorem ještě seznam vstupních a výstupních souborů, se kterými program pracuje, např. program BLBOST (input, output);
- patří sem i uses (jednotky)
- pokud definujeme jednotku - místo program unit, musí být uvedeno
Deklarační část
popisuje (deklaruje) objekty, se kterými bude program pracovat (významy identifikátorů)
každý objekt musí být nejprve deklarován a potom teprve použit!!!
Deklarace
1. návěští
2. konstanty
3. typy
4. proměnné
5. procedury a funkce
lze v libovolném pořadí a vícekrát, standard - v daném pořadí a jen jednou
Příkazová část
popisuje vlastní výpočetní proces
co se s deklarovanými objekty bude dělat
začíná begin a je ukončen tečkou (.)
obsahuje příkazy oddělené středníkem
Způsob zápisu
volný, využití odsazení
komentáře
mezery
nedělitelnost některých objektů (klíč. slova, literály, identifikátory, speciální víceznakové symboly, návěští)
ruční zápis - velká, malá písmena, podtržení
Komentáře
posloupnost libovolných znaků v {}nebo (* *)
lze zapsat kdekoliv, kde je povolena mezera
Proměnná
objekt, jehož hodnota se může měnit
· jméno (identifikátor)
· typ
· hodnota
Představa proměnné v paměti (alokace + jméno + pam. prostor, vstupy a výstupy).
IDENTIFIKÁTORY
posloupnost písmen a číslic začínající písmenem
· velká x malá písmena
· délka identifikátoru (rozlišení) - Pascal = 63 zanků
· další znaky - velmi často podtržítko _
· rezervovaná slova - zakázané identifikátory - nesmí se shodovat s klíčovým slovem
· standardní identifikátory (předdefinované) - nedefinují se, definované jazykem - integer, real, boolean, write, sqrt, ...
· nelze použít 2 proměnné se stejným identifikátorem
identifikátory - konstanty, proměnné, návěští, funkce, procedury, typu, programu, ...
mnemotechnika identifikátorů
Typ proměnné
základní datové typy v Pascalu - integer, real, boolean, char, string (strukturované, ukazatel, objekt)
· množina přípustných hodnot
· množina operací a funkcí
· paměťové nároky
Deklarace proměnných (Pascal)
var
N : integer;
A,B,C : real;
R,S : string;
P,Q : boolean;
Každá proměnná musí být vždy nejprve deklarována a teprve potom použita.
Hodnota proměnné
definice hodnoty:
· příkaz vstupu - přečtené hodnoty (klávesnice, soubor,...)
· přiřazovací příkaz - „vypočítané“ hodnoty
Každá proměnná musí mít vždy definovánu hodnotu.
Příkazy
Příkazy jazyka Pascal
jedndoduché
- přiřazovací
- procedury
- skoku
- prázdný
strukturované
- složený
- podmíněný (if-then-else, if-then, case)
- cyklu (while, repeat, for)
- with
syntaxe a sémantika jazyka
Jednoduché příkazy
Přiřazovací příkaz
definuje hodnotu proměnné
proměnná := výraz
proměnná - identifikátor proměnné, jejíž hodnota se mění
výraz - výraz stejného (resp. kompatibilního) typu jako proměnná na pravé straně
Výraz na pravé straně se vyhodnotí a jeho hodnota se přiřadí proměnné na levé straně.
Kompatibilita vzhledem k přiřazení
1. proměnná a výraz stejného typu
2. proměnná..real, výraz..integer (lze definovat šířeji)
Příkaz vstupu
read(seznam proměnných)
seznam proměnných - identifikátory proměnných, do kterých se mají načíst hodnoty z klávesnice, oddělené čárkou
Z vstupního zařízení (klávesnice) se načítají hodnoty a přiřazují se proměnným v seznamu.
Příkaz výstupu
write(seznam výrazů)
seznam výrazů - výrazy oddělené čárkou
Výrazy se postupně vyhodnocují a jejich hodnoty se zobrazují na obrazovce.
Příkaz skoku
GOTO návěští
nepoužíváme
Prázdný příkaz
nic - má syntaktický význam
Vývojové prostředí Borland Pascal 7.0
editor + nástroje pro překlad, ladění, a spuštění programu
spuštění, okna, nonamexx.pas
File - New
- Open F3
- Save F2
- Save as...
- Save all
- Exit Alt+X
Compile - Compile Alt+F9
- Destination (Memory/Disk)
Run - Run Ctrl+F9
Debug - User Screen Alt+F5
Úpravy vstupů a výstupů
(příklad Čtverec)
nepříjemnosti
mazání obrazovky
ukončení bez potvrzení
málo informací na obrazovce
úprava na obrazovce
semilogaritmický tvar čísel real
Původní program:
program Ctverec;
var
A,Obvod,Obsah: real;
begin
read(A);
Obvod:=4*A;
Obsah:=A*A;
write(Obvod,Obsah)
end.
Cílový požadavek vzhledu
(čistá obrazovka)
Obvod a obsah ctverce
---------------------
Zadej velikost strany: 5
Obvod ctverce o strane 5 je 20.
Obsah ctverce o strane 5 je 25.
(čekání na stisk)
Mazání obrazovky, čekání na stisk klávesy
mazání obrazovky clrscr
čekání na stisk klávesy repeat until keypressed
Jednotka crt uses crt
Příkaz výstupu
pozice kurzoru, rozměry obrazovky v textovém režimu
write(seznam výrazů) - kurzor za posledním znakem
writeln(seznam výrazů) - kurzor na další řádek
writeln(vynech řádek)
Příkaz vstupu
na pozici kurzoru
read(seznam proměnných)
zadávání proměnných - odděleny mezerou (nebo Enter)
málo hodnot - ptá se dál; více hodnot - přebytečné si zapamatuje
read(seznam proměnných) - přečte kolik potřebuje a zbytek si zapamatuje
readln(seznam proměnných) - přečte kolik potřebuje a zbytek ignoruje (zahodí)
readln - čekání na Enter
doporučení: pro každou hodnotu zvláštní příkaz vstupu (a s výzvou) a raději readln
char:
1 znak, konec řádku (Enter)=mezera
string:
čte všechny znaky až po následující znak konce řádky (Enter), který však již není do proměnné zahrnut
pokud je výsledný řetězec delší, než maximální délka dané řetězcové proměnné, uloží se pouze znaky v rozsahu délky proměnné, zbytek se ztrácí
následující Read začne čtení znakem konce řádky, který ukončil čtení řetězce
ke čtení po sobě jsoucích řetězců používat readln
integer, real:
přeskočí všechny mezery, tabelátory a znaky konce řádky, které numerický řetězec předcházejí
jestliže číselný řetězec nevyhovuje, nastane chyba; jinak je hodnota přiřazena do proměnné
následující Read začíná na mezeře, tabelátoru nebo znaku konce řádky, který ukončil předchozí číselný řetězec
Formátování výstupu
real výraz:10 10 znaků, semilog. tvar, doplnění mezer zleva nebo potlačení formátu
integer výraz:10 10 znaků, doplnění mezer zleva nebo potlačení formátu
string výraz:10 zarovnání textu na 10 znaků, doplnění mezer nebo oříznutí zprava
real výraz:10:3 10 pozic, z toho 3 des. místa, desetinný tvar, doplnění mezer zleva nebo potlačení formátu
Program Čtverec po úpravě
program Ctverec;
uses crt;
var
A, Obvod, Obsah: real;
begin
clrscr;
writeln(‘Obvod a obsah ctverce’);
writeln(‘---------------------’);
write(‘Zadej velikost strany ctverce: ‘);
read(A);
writeln;
Obvod:=4*A;
Obsah:=A*A;
writeln(‘Obvod ctverce o strane ’,A:10:2,’ je ‘,Obvod,’.’);
writeln(‘Obsah ctverce o strane ’,A:10:2,’ je ‘,Obsah,’.’);
repeat until keypressed
end.
Požadavky na řešení úloh
smazání obrazovky na začátku, čekání na stisk na konci
zadávání hodnot po 1 a s výzvou
nadpis
komentované výstupy
odstraňovat semilogaritmický tvar čísel
žádné zbytečnosti
oddělovat vstupy a výstupy od vlastního algoritmu (pokud nejsou součástí algoritmu)
používat komentáře
Záměna hodnot
Sestavte posloupnost přiřazovacích příkazů pro záměnu hodnot A, B.
Vstupy:
A
B zadané hodnoty integer
Výstupy:
A
B zaměněné hodnoty
================================================================================
