Algoritmy a datové struktury 1

Algoritmy a datové struktury 1 Modul 2 – Ukládání dat v operační paměti

text pro distanční studium

Ing. Eliška Treterová

Ostravská univerzita v Ostravě, Přírodovědecká fakulta Katedra Informatiky a počítačů

Ostrava 2003

Algoritmy a datové struktury 1

2


Obsah Úvod ....................................................................................................................4 1. Bloková struktura programu, podprogramy. ...............................................5 1.1. Podprogramy .......................................................................................5 1.2. Bloková struktura ................................................................................6 2. Podprogramy v Borland Pascalu .................................................................9 2.1. Podprogram typu funkce ...................................................................10 2.2. Podprogram typu procedura ..............................................................14 2.3. Formální parametry podprogramů ....................................................17 2.4. Skutečné parametry ...........................................................................18 2.5. Korespondenční úkol č. 1..................................................................21 3. Uložení dat v operační paměti – jednoduchá proměnná ...........................22 3.1. Číselná proměnná ..............................................................................22 3.1.1. Celočíselná proměnná ...............................................................22 3.1.2. Reálná proměnná.......................................................................24 3.2. Logická proměnná - datový typ (BOOLEAN).................................25 3.3. Znaková proměnná - datový typ CHAR ...........................................29 4. Strukturovaná proměnná ...........................................................................32 4.1. Řetězec znaků - datový typ STRING ................................................33 4.2. Jednorozměrné pole...........................................................................37 4.2.1. Deklarace jednorozměrného pole v programu ..........................37 4.2.2. Význam úseku CONST a TYPE pro definici datových typů....39 4.2.3. Práce s proměnnou typu pole ....................................................40 4.2.4. Proměnná typu pole a podprogramy .........................................44 4.2.5. Korespondeční úkol č. 2............................................................50 4.3. Vícerozměrná pole ............................................................................50 4.3.1. Deklarace dvourozměrného pole v programu ...........................50 4.3.2. Práce s dvourozměrným polem .................................................51 4.3.3. Generátor náhodných čísel ........................................................53 4.3.4. Korespondenční úkol č. 3..............................................................56 4.4. Množina hodnot.................................................................................57 4.4.1. Konstruktory množin: ...............................................................58 4.4.2. Množinové operace ...................................................................59 4.4.3. Korespondenční úkol č. 4..........................................................62 4.5. Proměnná typu záznam .....................................................................63 4.5.1. Využití příkazu WITH ..............................................................65 4.5.2. Pravidla pro tvorbu identifikátorů (názvů) položek záznamu ...66 4.5.3. Záznam v záznamu....................................................................67 4.5.4. Pole záznamů.............................................................................68 4.5.5. Vytvoření procedury pro načtení údajů do pole záznamů.........69 4.5.6. Korespondenční úkol č. 5.........................................................70 Závěr..................................................................................................................71 Literatura ...........................................................................................................71

3


Úvod Studijní text je určen pro zájemce o studium předmětu Algoritmy a datové struktury. Text nepostihuje celou problematiku předmětu Algoritmy a datové struktury, je zaměřen pouze na jeden blok učiva, a sice na problematiku ukládání dat v operační paměti počítače formou jednoduché proměnné a formou statických datových struktur. V úvodu studijního materiálu je zařazena kapitola týkající se problematiky tvorby podprogramů v prostředí Borland Pascalu. Důvodem zařazení této kapitoly je to, že znalost tvorby podprogramů zjednodušuje a zpřehledňuje sestavování složitějších algoritmů, a v dalších kapitolách se tato znalost předpokládá. V následující kapitole jsou pak vysvětlena základní pravidla, která platí v prostředí Borland Pascalu při ukládání dat do operační paměti pomocí jednoduché proměnné a jsou podrobně vysvětleny možností následného zpracování dat v závislosti na typech dat. Závěrečná kapitola je věnována problematice uložení dat ve formě statických datových struktur. Pro každou uvedenou datovou strukturu je v textu vysvětleno, jaké možnosti poskytuje programovací jazyk Borland Pascal při následném zpracování datových struktur. Pro zvládnutí učiva tohoto studijního textu se předpokládá základní znalost tvorby vývojových diagramů a znalost prostředí programovacího jazyka Borland Pascal. Studující by měl před začátkem studia také znát postup při tvorbě programu a měl by se orientovat v problematice a jednoduchých a strukturovaných příkazů.

4


1. Bloková struktura programu, podprogramy. Cíl: Cílem této kapitoly je, abyste po jejím prostudování byli schopni: - orientovat se v základních pojmech týkajících se podprogramů a blokové struktury programu - objasnit rozdíl mezi jednotlivými typy podprogramů - vysvětlit postup při sestavování a využití podprogramů - uvést klady a zápory využití podprogramů - prakticky použít podprogramy při řešení úkolů Klíčová slova: Blok, vnořený blok, bloková struktura, program, podprogram, procedura, funkce, lokální proměnná, globální proměnná, viditelnost proměnných.

Průvodce studiem: Již dobře znáte, jakou strukturu musí mít program napsaný v zdrojovém kódu programovacího jazyka Borland Pascal. Určitě jste si všimli, že jste doposud nepotřebovali některé úseky dovolené pro deklarační část programu. V této kapitole vám vysvětlím, k čemu vlastně slouží úsek začínající klíčovým slovem Procedure a úsek začínající klíčovým slovem Function.

1.1.

Podprogramy

Při řešení složitějších problémů se stává nutností provést před sestavením vývojového diagramu (nebo programu) analýzu problému. Analýza může být velmi podrobná až do úrovně stanovení názvů proměnných s popisem jejich významu při řešení. Minimálním výsledkem analýzy by ale mělo být : - rozdělení celého problému na dílčí částí - vyčlenění relativně samostatných částí, které lze vyřešit samostatně - stanovení návazností řešení A právě rozdělení celého problému na dílčí podproblémy, které je možné řešit odděleně, vede k potřebě vytvářet tzv. podprogramy. Podprogram pak lze chápat, jako relativně samostatnou část celého algoritmu. Sestavujeme jej tehdy, pokud potřebujeme, aby se prováděly stejné sekvence příkazů, ale s různými daty, nebo aby se prováděly stejné sekvence příkazů, ale v různých místech programu.

5

Algoritmy a datové struktury 1 Význam podprogramů: • • •

podprogram má význam jako celek s opakovaným použitím možnost sestavovat relativně samostatné části programu vede k členění celého problému na menší celky, z čehož vyplývá větší srozumitelnost řešení. jednou vytvořené podprogramy se dají využívat i v jiných programech

1.2.

Bloková struktura

Průvodce studiem: V okamžiku, kdy začnete přemýšlet, že byste potřebovali svůj algoritmus (program) rozdělit na dílčí podproblémy, a ty řešit zavedením podprogramů, musíte se začít dívat na řešený problém z pohledu členění do tzv. bloků. V dalším textu vám vysvětlím, co znamená bloková struktura programu a jaký dopad má členění programu na podprogramy na chod programu, jak to ovlivní platnost (viditelnost) proměnných. Základní logickou jednotkou programu je blok. Blok je tvořen hlavičkou, deklarační a příkazovou částí. To znamená, že všechny programy, které byly ve studijním textu doposud zařazeny, tvořily pouze jeden blok. Každý blok ale může obsahovat další bloky, které jsou v prostředí Borland Pascalu, umístěné v deklarační části programu. Těmto blokům pak říkáme vnořené bloky neboli podprogramy. Taktéž vnořený blok je tvořen hlavičkou, deklarační a příkazovou částí. V jazyku Borland Pascal je pro zavedení podprogramů určen úsek deklarační části začínající klíčovým slovem Procedure nebo Function. Postupným vkládáním podprogramů do deklarační částí programu vzniká tzv. hierarchická struktura programu, kterou nazýváme bloková struktura programu. Průvodce studiem: V dalším textu budete podrobně seznámeni s problematikou vlastní tvorby podprogramů. Ale již nyní by bylo dobré, kdybyste si uvědomili význam blokové struktury programu pro další Vaši práci. Pro lepší představu jsem vložila obrázek, na kterém je bloková struktura zakreslena. K tomuto obrázku se těsně váže další obrázek, na kterém je znázorněna bloková struktura z pohledu úrovní vnoření jednotlivých bloků. Úroveň vnoření má vliv na platnost proměnných.

6


Bloková struktura programu – jedná se o schématický pohled na členění do jednotlivých bloků, proto nejsou vůbec zařazeny příkazové části programu ani podprogramů.

PROGRAM A; VAR k,l,w:INTEGER; … PROCEDURE B; VAR m,n,q:INTEGER; FUNCTION C; VAR q:INTEGER; … BEGIN … END; PROCEDURE D; VAR p,r:INTEGER; … BEGIN … END; BEGIN … END; PROCEDURE E; VAR i,j,w:INTEGER; … BEGIN … END; BEGIN … END.

7

Algoritmy a datové struktury 1 Bloková struktura programu z hlediska úrovně vnoření:

A

Úroveň vnoření 0

k,l,w

B

C

q

E m,n,q

i,j,w

D



p,r

Vliv blokové struktury na platnost (viditelnost) deklarovaných objektů: •

•

•

•

objekty deklarované na 0-té úrovni vnoření jsou globální objekty programu a jejich rozsahem platnosti (viditelnosti) je blok programu včetně všech vnořených bloků - proměnné k, l je možno používat v příkazových částech bloků A, B, C, D, E. objekty deklarované v bloku úrovně vyšší než 0 mají rozsah platnosti omezen na blok, ve kterém jsou deklarovány, a na všechny bloky hierarchicky podřízené tomuto bloku – proměnné m, n lze požívat v příkazových částech bloků B, C, D. Těmto objektům se říká lokální objekty. objekt se stejným jménem uvedený ve vnořeném bloku zastiňuje, tzn. ruší platnost stejnojmenného objektu z nadřazeného bloku – v našem případě q deklarované v bloku B platí v blocích B a D. Neplatí však v bloku C, protože blok C má deklarovanou vlastní proměnnou q. To tedy znamená, že proměnná q z bloku B a proměnná q z bloku C jsou různé proměnné. Jinak řečeno: lokální objekt má přednost před globálním. Lokální objety zabírají své vlastní místo v paměti, po ukončení činnosti podprogramu uvolňují lokální objekty v tomto podprogramu deklarované místo v paměti

8


2. Podprogramy v Borland Pascalu Dělení podprogramů: • standardní – v Borland Pascalu existují předem definované podprogramy, které uživatel používá, aniž by je deklaroval. Tyto podprogramy jsou seskupeny do standardních knihoven podprogramů (UNIT), které jsou součástí programového prostředí Borland Pascal. Tato problematika není obsahem tohoto studijního textu. • definované uživatelem - tyto podprogramy sestavuje programátor sám. Právě sestavování vlastních podprogramů je náplní další části této kapitoly. Klíčová slova: Podprogram, procedura, funkce, formální parametry, formální parametry volané hodnotou, formální parametry volané odkazem, skutečné parametry, globální proměnná, lokální proměnná, deklarace podprogramu, volání podprogramu. Průvodce studiem: Učivo, které nyní máte před sebou, je velmi důležité pro optimalizaci vaší práce. Celou problematiku se vám pokusím vysvětlit na velmi jednoduchých algoritmech. Budete mít určitě pocit, že sestavení podprogramů je naprosto zbytečné a jen vám přidělává práci. Je to tím, že musíte pochopit všechny principy a varianty řešení nejdříve na opravdu triviálních algoritmech a teprve následně pak v algoritmech složitějších. Ze zkušenosti vím, že studenti mají tendenci se sestavování podprogramů ve svých řešeních vyhnout, protože program jim samozřejmě funguje ve své výsledné podobě stejně, ať už podprogramy použili či ne. Důvody, které vedou k zařazování podprogramů, se dají shrnout takto: • rozčlenění problému na menší podproblémy, což vede k lepší srozumitelnosti algoritmu • možnost použít již jednou sestavené podprogramy v jiných programech • možnost vytvářet vlastní knihovny podprogramů Podprogramy definované uživatelem

U podprogramů definovaných uživatelem rozlišujeme vlastní tvorbu podprogramu neboli deklaraci podprogramu a použití podprogramu neboli volání podprogramu. Deklarace těchto podprogramů se umísťují do deklarační části programu za deklarace konstant, typů a proměnných. V jazyce Borland Pascal rozeznáváme 2 typy podprogramů: • Funkce • Procedury

9


2.1.

Podprogram typu funkce

Deklarace funkce: Deklarace funkce se umisťuje do deklarační části programu. Deklarace funkce se skládá z hlavičky funkce a z těla funkce.

FUNCTION název (formální parametry): dat. typ výsledku; hlavička funkce … Deklarace lokálních objektů … BEGIN tělo funkce příkazy END; Hlavička funkce: - musí obsahovat klíčové slovo function, - musí obsahovat název funkce - musí obsahovat datový typ výsledku. - nemusí obsahovat kulaté závorky a formální parametry (pak vznikají tzv. funkce bez parametru) Tělo funkce: - pokud budete potřebovat zavést lokální proměnné, musíte tak učinit v deklarační části podprogramu, pokud lokální objekty nepotřebujete, bude deklarační část vynechána - musí obsahovat klíčová slova begin a end; (za end nesmí být tečka). Jako funkce sestavujeme takový algoritmus, jehož provedením se získá jedna hodnota. Získaná funkční hodnota se ukládá do identifikátoru (názvu) funkce. V příkazové části funkce musí být nejméně jeden přiřazovací příkaz, na jehož levé straně je identifikátor funkce. Funkce tak vrací do hlavního programu, odkud je volána, jednu vypočítanou hodnotu. Příklad: Sestavte funkci, která bude počítat N-tou mocninu reálného čísla X. Řešte i pro záporného mocnitele. Rozbor: N-tá mocnina se vypočítá tak, že N-krát násobíme hodnotu, kterou máme umocnit. Pokud je mocnitel záporný, postupujeme tak, jako by byl kladný, ale výsledkem je pak převrácená hodnota získaného výsledku. Význam proměnných: Z číslo, které umocňujeme – formální parametr N mocnitel – formální parametr V pro uložení výsledku - lokální proměnná I řídící proměnná cyklu - lokální proměnná Mocnina název funkce

10

Algoritmy a datové struktury 1 Vývojový diagram, který řeší výpočet N-té mocniny čísla Z.

Začátek podprogramu Vstup Z Vstup N V := 1

I := 1,2,…,Abs(N) +

-

N<0

V := V * Z

V := 1/V

Mocnina := V Konec podprogramu

Následuje zápis algoritmu v syntaxi jazyka Borland Pascal. Úkolem bylo sestavit funkci, proto je v hlavičce klíčové slovo FUNCTION. Podprogram, který je zde sestaven, je soběstačný, protože všechny objekty, se kterými se pracuje v příkazové části, jsou známé: Z a N jsou formální parametry, I a V jsou lokální proměnné – potřebujeme je pouze v tomto bloku, po skončení činnosti tohoto podprogramu tyto proměnné zaniknou FUNCTION Mocnina (Z:REAL; N:INTEGER) : REAL; VAR lokální I : INTEGER; V : REAL; deklarace BEGIN V := 1; FOR I := 1 TO ABS(N) DO V := V*Z; IF N < 0 THEN V := 1/V; Mocnina := V; END;

11

deklarace funkce


Příklad: Sestavte program, který vypočítá N-tou mocninu každého čísla z intervalu . Využijte funkci Mocnina z předchozího příkladu. Rozbor: Vzhledem k tomu, že algoritmus výpočtu N-té mocniny reálného čísla je již vyřešen formou funkce, využijeme této skutečnosti při řešení zadaného úkolu. Význam proměnných: Moc Proměnná pro uložení zadaného mocnitele – získáme v hlavním programu J Řídící proměnná cyklu a zároveň číslo, které umocňujeme získáme v hlavním programu K, L Hranice intervalu – získáme v hlavním programu Vysl Proměnná pro uložení výsledku volání funkce Mocnina Z formální parametr - číslo, které umocňujeme N formální parametr - mocnitel V pro uložení výsledku - lokální proměnná I řídící proměnná cyklu - lokální proměnná Mocnina Název funkce

Začátek Zadej mocnitele Čti: Moc Zadej hranice intervalu Čti: K, L J:=K,…,L Vysl := Mocnina(J, Moc) Tisk: Vysl Konec

12


Průvodce studiem:

Nyní bych vás chtěla upozornit na novou značku ve vývojovém diagramu. Je to značka, která znamená volání podprogramu. Zařazením této značky se vývojový diagram velmi zjednodušil - zakreslený algoritmus obsahuje pouze jeden příkaz cyklu pro získání všech čísle z intervalu K,L. V těle tohoto cyklu je volání funkce a tisk výsledků. Je to ukázka přínosu znalostí sestavení podprogramu. Pokud si algoritmus pro výpočet N-té mocniny jednou vyřešíte a vytvoříte z něj podprogram, máte možnost pak v každém programu, kde se tento výpočet požaduje, tento podprogram zařadit. Nyní vám ještě vysvětlím, jak tedy bude vypadat program s použitím podprogramu. Vše je viditelné na níže vloženém zdrojovém kódu. V tomto místě ještě máte málo informaci o parametrech a předávání hodnot. Bude to vysvětleno v dalším textu.

Zdrojový kód programu, který řeší výpočet n-té mocniny čísla X s využitím funkce Mocnina.

PROGRAM vypocet; VAR vysl : REAL; Moc,K,L,J : INTEGER;

globální deklarace

FUNCTION Mocnina (Z:REAL; N:INTEGER) : REAL; VAR lokální i : INTEGER; v : REAL; deklarace BEGIN v := 1; FOR i := 1 TO ABS(N) DO v := v*z; IF n < 0 THEN v := 1/v; Mocnina := v; END; BEGIN WRITE(‘Zadej mocninu: ‘); READLN(Moc); WRITE(‘Zadej hranice intervalu: ‘); READLN(K); READLN(L); FOR J := K To L Do Begin vysl := Mocnina_1(J, Moc); WRITELN(‘Vysledek: ‘,Vysl); End; END.

13

formální parametry volané hodnotou

deklarace funkce

skutečné parametry

volání funkce


2.2.

Podprogram typu procedura

Procedury jsou druhým typem podprogramu, který v Borland Pascalu je dovolen. Formou procedury se sestavují především ty dílčí algoritmy, jejichž výsledkem nemusí být jen jediná hodnota jako je tomu u funkcí. Procedura dokáže vracet do programu, odkud je volána, více hodnot, případně nemusí vracet žádnou hodnotu. Deklarace procedury

Deklarace procedury se umisťuje do deklarační části programu. Deklarace procedury se skládá z hlavičky procedury a z těla procedury. PROCEDURE název_procedury (formální parametry); … hlavička procedury … lokální deklarace … BEGIN … tělo procedury příkazy … END; Hlavička procedury: - musí obsahovat klíčové slovo procedure, - musí obsahovat název procedury - Nemusí obsahovat kulaté závorky a formální parametry (tzv. procedura bez parametru) Tělo procedury: - všechny lokální objekty, které bude podprogram využívat, musí být deklarovány – deklarační část - musí obsahovat klíčová slova begin a end; (za end nesmí být tečka) příkazová část Volání procedury Volání procedury se umisťuje do příkazové části programu. Proceduru voláme tak, že napíšeme samostatně na řádek její název a do kulaté závorky skutečné parametry (pokud byly při deklaraci uvedeny parametry formální).

Výsledkem volání může být: • provedení nějaké činnosti – bez návratové hodnoty • výsledkem volání je jedna nebo více návratových hodnot.

14

Algoritmy a datové struktury 1 Příklad: Sestavte proceduru, která bude počítat N-tou mocninu reálného čísla X. Řešte i pro záporného mocnitele. Význam proměnných: Z číslo, které umocňujeme – formální parametr N mocnitel – formální parametr V pro uložení výsledku – formální parametr I řídící proměnná cyklu - lokální proměnná Mocnina_1 název funkce

PROCEDURE Mocnina_1(z:REAL; N:Integer; VAR v:REAL); VAR i : INTEGER; … deklarace lokální proměnné BEGIN v := 1; FOR i := 1 TO ABS(n) DO v := v*z; IF n < 0 THEN v := 1/v; END;

deklarace procedury

Průvodce studiem: Algoritmus, který je tady řešen, je stejný, jako u sestavení funkce. Základní rozdíl je v tom, že procedura neumí vrátit výsledek ve svém názvu, takže neuvádí se datový typ výsledku v hlavičce a v těle procedury nesmí být příkaz pro přiřazení výsledku do názvu procedury. Jak tedy dostaneme výsledek do hlavního programu ? K tomu slouží další parametr v hlavičce procedury. Před tímto parametrem musí být klíčové slovo VAR. Příklad: Sestavte program, který vypočítá N-tou mocninu čísla X. Využijte proceduru Mocnina_1 z předchozího příkladu. Význam proměnných: X Číslo, které se má umocnit - získáme ho v hlavním programu Moc Proměnná pro uložení zadaného mocnitele – získáme v hlavním programu Vysl Proměnná do které se uloží výsledek z procedury Z formální parametr - číslo, které umocňujeme N formální parametr - mocnitel v pro uložení výsledku – formální parametr I řídící proměnná cyklu - lokální proměnná Mocnina_1 Název procedury

15

Algoritmy a datové struktury 1 Zdrojový kód programu, který řeší výpočet n-té mocniny čísla X s využitím procedury Mocnina.

PROGRAM vypocet_2; VAR globální vysl, X : Real; moc : Integer; deklarace

formální parametry volané hodnotou

formální parametr volaný odkazem

PROCEDURE Mocnina_1(z:Real;n:Integer;VAR v:Real); VAR i : INTEGER; … deklarace lokální proměnné BEGIN v := 1; FOR i := 1 TO ABS(N) DO v := v*z; IF n < 0 THEN v := 1/v; END; BEGIN WRITE(‘Zadej cislo: ‘); READLN(X); WRITE(‘Zadej mocninu: ‘); READLN(moc); Mocnina_2(X,moc,vysl); WRITELN(‘Vysledek: ‘,vysl); END.

deklarace procedury

skutečné parametry

volání procedury

Sestavením podprogramu pro výpočet N-té mocniny zadaného čísla se velmi zjednodušila příkazová část programu. Příkazová část je nyní tvořena pouze posloupností příkazů.

Průvodce studiem:

V podprogramu správně proběhne výpočet – v proměnné v je výsledek. Klíčové slovo VAR před formálním parametrem v způsobí, že obsah proměnné v se přenese do skutečného parametru vysl do hlavního programu. Pokud byste klíčové slovo VAR před daný parametr nenapsali, výpočet v podprogramu by proběhl správně, ale výsledek by se do skutečného parametru nepřenesl. Nezařazení klíčového slova Var před formální parametry, které slouží k přenesení výsledků do skutečného parametru, je velmi častá chyba. Z hlediska syntaxe je vše v pořádku, pouze nemáte výsledek.

16


2.3.

Formální parametry podprogramů

Podprogram může pracovat s objekty trojího druhu: • s formálními parametry • s lokálními proměnnými • s globálními proměnnými Formální parametry Za názvem podprogramu mohou, ale nemusí být uvedeny kulaté závorky a v nich seznam tzv. formálních parametrů. Jako oddělovač parametrů slouží středník. Pokud formální parametry nezavádíme, nepíšeme ani kulaté závorky.

Např.: FUNCTION výpočet (x:INTEGER ; z:REAL) : REAL; x je formální parametr, je celočíselného typu FUNCTION výpočet : REAL;

z je formální parametr, je reálného typu

… funkce bez formálních parametrů

Výpočet v podprogramu se pak provádí s formálními parametry, které při volání (použití) podprogramu jsou nahrazeny parametry skutečnými. Formální parametry dělíme na: •

parametry volané odkazem – tyto parametry jsou uvozeny klíčovým slovem VAR. Tento druh parametrů se používá jako výstupní proměnné – budou v nich uloženy výsledky, kterých jsme chtěli dosáhnout. Tyto parametry se nejčastěji používají u procedur. Nedoporučuje se používat je u funkcí! Skutečným parametrem v tomto případě může být pouze proměnná. • Parametry volané hodnotou – předávají podprogramu počáteční hodnoty. Před těmito parametry není klíčové slovo VAR. Skutečným parametrem v tomto případě může být: - proměnná - konstanta - výraz, jehož výsledek je stejného typu jako formální parametr Obecně platí: • formální parametry uvedené v hlavičce podprogramu se již nesmí deklarovat v deklarační části podprogramu • počet, pořadí a datový typ skutečných parametrů musí odpovídat počtu, pořadí a datovým typům formálních parametrů

17


2.4.

Skutečné parametry

Parametry, které jsou uvedeny při volání podprogramů, se nazývají skutečné parametry. Hodnoty těchto parametrů se přenesou do parametrů formálních. Pokud je před formálním parametrem klíčové slovo Var, dojde po ukončení podprogramu k předání obsahu takto označených formálních parametrů do odpovídajících parametrů skutečných. Vztah mezi formálními a skutečnými parametry: Příklad: V následujícím programu je ukázka několika volání procedury s názvem Mocnina. Procedura nemá sestavenou příkazovou část, slouží nám pouze k demonstraci správných a chybných způsobů volání procedury.

Program Test; VAR a,b,c : Real; l,m : Integer; PROCEDURE Mocnina(z:Real; n:Integer; VAR v:Real); Begin … … end; … konec procedury Begin … Správné volání procedury: Mocnina(a, m, b); Mocnina(a, 4, b); Mocnina(l, m, c); Mocnina(a, -2, a); Mocnina(a+b, 5, c);

{ Do b se uloží an } { Do b se uloží a4 } { Do c se uloží lm } { Do a se uloží a-2 } { Do c se uloží (a+b)5 }

Chybné volání procedury: Mocnina(a, b, c); Mocnina(2, 3, 4); Mocnina(a, l, m); Mocnina(a, 1, a+b);

{ Parametr b není Integer } { Místo 4 musí být název proměnné } { Proměnná m není Real } { Nemůže být (a+b) }

… END.

18

deklarace procedury

Algoritmy a datové struktury 1 Schéma rozdělení parametrů:

Parametry

Formální parametry (v deklaraci)

Skutečné parametry (při volání)

Volané hodnotou Volané odkazem

Průvodce studiem:

Po prostudování této kapitoly byste měli mít jasnou představu o formálních a skutečných parametrech. V úvodu kapitoly je ale uvedeno, že podprogramy mohou pracovat také s lokálními a globálními proměnnými. Informace ohledně lokální a globální proměnné jsou zařazeny v kapitole „Bloková struktura programu“. Základní vlastností lokálních a globálních proměnných si tady ale opět připomeneme. Lokální proměnné Lokální proměnné se deklarují v deklarační části podprogramu. Název lokální proměnné nesmí být shodný s názvem formálního parametru. Lokální proměnné mají náhodnou počáteční hodnotu !! Po ukončení činnosti podprogramu jsou tyto proměnné nepřístupné pro další práci. V deklarační části podprogramu je možno zařadit deklaraci dalšího podprogramu. Globální proměnné Globální proměnné jsou ty proměnné, které byly deklarovány v deklarační části hlavního programu. Tyto proměnné se nulují při spuštění programu a ponechávají si svou hodnotu až do ukončení hlavního programu. Průvodce studiem:

Z vlastností globální proměnné vyplývá, že ji bez problému můžete využít v každém vnořeném bloku (podprogramu). Pak v podstatě nemusíte zavádět formální parametry. Je třeba si ale uvědomit, že takto sestavené podprogramy ztrácejí svou obecnost (nezávislost na globálních proměnných).

19


Shrnutí:

Bloková struktura programu vzniká na základě možnosti sestavovat podprogramy. Podprogram chápeme jako soubor příkazů, které řeší ucelený dílčí problém, který se bude opakovat na více místech programu nebo i v jiných programech s jinými vstupními daty. Programovací jazyk Borland Pascal dovoluje sestavovat dva typy podprogramů, a sice funkce a procedury. Funkce je podprogram, který sestavujeme tehdy, jestliže výsledkem výpočtu je jedna hodnota. Výsledek funkce vrací ve svém názvu, musíme tedy definovat datový typ výsledku v hlavičce funkce a v těle funkce musíme zařadit přiřazovací příkaz, který přiřadí výsledek do názvu funkce. Procedura je podprogram, který sestavujeme tehdy, jestliže výsledkem činnosti podprogramu není žádná hodnota nebo tehdy, jestliže z podprogramu vystupuje hodnot více. Samozřejmě je možné, aby i procedura vracela pouze jednu hodnotu. Hodnoty z procedury se do hlavního programu předávají prostřednictvím formálních parametrů volaných hodnotou. Předávání hodnot mezi podprogramem a programem prostřednictvím formálních parametrů zvyšuje poněkud dobu trvání celého výpočtu. To může být chápáno jako určitá nevýhoda. Naopak z hlediska obecnosti podprogramů se zavedení formálních parametrů jeví jako výhodné, protože při zařazování podprogramů do nových programů není třeba vůbec zohledňovat proměnné, které program využívá.

Kontrolní otázky:

1. Co je to blok ? 2. Co je to vnořený blok ? 3. Co je to podprogram ? 4. Které podprogramy jsou v Borland Pascalu dovoleny ? 5. Jak vypadá deklarace funkce ? 6. Jak vypadá deklarace procedury ? 7. Jak vypadá volání funkce ? 8. Jak vypadá volání procedury ? 9. Kdy použijeme funkci a kdy proceduru ? 10. Co jsou to formální parametry, jaký význam má klíčové slovo Var před názvem formálního parametrů ? 11. Jaký je vztah mezi formálními a skutečnými parametry ? 12. Co je to lokální proměnná ? 13. Co je to globální proměnná ? 14. Jak se řeší problém stejného jména pro globální a lokální proměnnou ? 15. Je možné sestavovat podprogramy bez formálních parametrů ?

20


2.5.

Korespondenční úkol č. 1

Zadání: Sestavte funkci s názvem FAKTORIAL, která vypočítá faktoriál čísla N. Tuto funkci pak použijte v programu, který požádá o zadání celého kladného čísla a pokud číslo je větší nebo rovno nule, provede výpočet faktoriálu pomocí funkce Faktoriál a vytiskne výsledek na obrazovku. Pokud číslo nevyhovuje stanovené podmínce, vypíše na obrazovku informaci „chyba v zadání“ a program požádá o zadání nové hodnoty. Rozbor: Pro řešení použijte níže sestavený vývojový diagram výpočtu faktoriálu. Sestavte vývojový diagram pro zadaný úkol a zapište v programovacím kódu jazyka Borland Pascal. Význam proměnných, které jsou použity ve vývojovém diagramu: N formální parametr - číslo, jehož faktoriál počítáme V Pro uložení výsledku - lokální proměnná I řídící proměnná cyklu - lokální proměnná FAKTORIAL Název funkce Proměnné, které použijete ve vlastním programu, pojmenuje podle svým představ. Vývojový diagram funkce FAKTORIAL:

Začátek podprogramu Vstup N v := 1

I := 1,2,…,N

v := v * I

FAKTORIAL:= v Konec podprogramu

21


3. Uložení dat v operační paměti – jednoduchá proměnná Data, která potřebujeme zpracovat pomocí programovacího jazyka, jsou uložena v operační paměti. Různé typy dat zabírají různě veliké místo v operační paměti. Každé paměťové místo má svou adresu vyjádřenou v číselné podobě. S adresou v číselné podobě ale programátor takřka nepracuje. Ukládání dat se realizuje prostřednictvím proměnných a konstant. Konstanta je místo v operační paměti, které má své jméno (identifikátor konstanty). Konstanta je takový datový objekt, kterému je na začátku běhu programu přiřazena hodnota a po celou dobu běhu programu se tato hodnota nemění. Proměnná je místo v paměti, které má své jméno (identifikátor proměnné). Pomocí tohoto jména s proměnnou pracujeme. Proměnná je takový datový objekt, jehož hodnota se v průběhu programu může měnit. V prostředí programovacího jazyka BORLAND PASCAL je nutné, aby každá proměnná, kterou chceme v programu použít, měla stanoveno jméno a datový typ. Datový typem jednoznačně určujeme, zda do proměnné budeme ukládat celé číslo, desetinné číslo, znak, skupinu znaků nebo logickou hodnotu. Za tímto účelem byla v programu zavedena deklarační část a byla zavedena určitá klíčová slova, která umožňují jednoznačně datový typ proměnné určit.

3.1.

Číselná proměnná

Při práci s číselnými daty musíme rozhodnout, zda budeme pracovat pouze s celočíselnými hodnotami, nebo zda budeme potřebovat i desetinnou část čísel. Je rozdíl v uložení celočíselných hodnot a čísel s desetinnou částí v operační paměti. V Borland Pascalu musíme důsledně rozlišovat mezi číslem celým a číslem s desetinnou částí. 3.1.1. Celočíselná proměnná

Překladač Borland Pascalu rozlišuje 5 datových typů pro celá čísla. Typ BYTE SHORTINT WORD INTEGER LONGINT

Množina hodnot (rozsah) 0 .. 255 -128 .. 127 0 .. 65 535 -32 768 .. 32 767 -2 147 483 648 .. 2 147 483 647

Velikost paměti v bytech 1 1 2 2 4

Není nutné, aby programátor přesně znal číselné údaje uvedené v tabulce. Tyto hodnoty lze vždy jednoduchým způsobem dohledat v literatuře nebo v nápovědě programovacího prostředí.

22


Důležité je uvědomit si, že existuje více možností deklarace celočíselné proměnné a že již deklarováním proměnné můžeme ušetřit místo v operační paměti. Operace, které je možné s celočíselnou proměnnou provádět, jsou stejné pro všechny výše uvedené deklarace . Dovolené operace s proměnnými celočíselných typů: a) aritmetické: + , - , * , DIV, MOD, / + … sčítání … odčítání * … násobení DIV … celočíselné dělení MOD… zbytek po celočíselném dělení / … přesné dělení Použití operace dělení pomocí operátoru / je dovoleno pro celočíselné proměnné, ale výsledek tohoto dělení je reálné číslo (číslo s desetinnou částí). Výsledkem ostatních operací bude celočíselná hodnota. b) relační : = … <> … > … >= … < … <= …

rovná se nerovná se větší než větší nebo rovno menší než menší nebo rovno

Výsledkem těchto operací je logická hodnota TRUE nebo FALSE. Předdefinované celočíselné konstanty - není třeba je zavádět v deklarační části programu.

MAXINT - obsahuje největší dovolenou hodnotu , kterou lze uložit do proměnné typu INTEGER, což je 32 767. MAXLONGINT - obsahuje největší dovolenou hodnotu , kterou lze uložit do proměnné typu LONGINT, což je 2 147 483 647. Průvodce studiem:

Pokud úplně zapomenete, že existují nějaké předdefinované konstanty, vůbec nic se nestane. Uvedla jsem informaci o existenci předdefinovaných konstant proto, že je celkem výhodné je občas použít. Nemusíte je před použitím v programu deklarovat a také máte jistotu, že mají vždy stejnou hodnotu. V dalším textu jsou občas použity.

23

Algoritmy a datové struktury 1 3.1.2. Reálná proměnná Průvodce studiem:

Čísla s desetinnou částí jsou často v dalším textu nazývána reálná čísla. Je to v programátorské terminologii běžné, proto vás na to upozorňuji již zde v úvodních informacích. Taktéž vás chci upozornit na to, že i když do proměnné, kterou definujete jako reálnou, uložíte číslo celé (bez zadání desetinné části), je přesto toto číslo považováno za reálné a některé operace s ním tudíž nejsou dovoleny (např. celočíselné dělení). V BORLAND PASCALU je předdefinováno 5 datových typů pro reálná čísla: TYP REAL SINGLE DOUBLE EXTENDED COMP

Množina hodnot (rozsah) Velikost paměti v bytech 2.9 * 10-39 .. 1.7 * 1038 6 -45 38 1.5 * 10 .. 3.4 * 10 4 5.0 * 10-324 .. 1.7 * 10308 8 -4932 4932 3.4 * 10 .. 1.1 * 10 10 -263 + 1 .. 263 - 1 8

Nejpoužívanější je datový typ REAL. Tento datový typ má přesnost 11 až 12 platných číslic. Dovolené operace s proměnnými reálného datového typu: a) aritmetické: + … sčítání … odčítání * … násobení / … dělení Nelze použít operace DIV a MOD !!! b) relační : = … <> … > … >= … < … <= …

rovná se nerovná se větší než větší nebo rovno menší než menší nebo rovno

Výsledkem těchto operací je logická hodnota TRUE nebo FALSE. Předdefinované reálné konstanty - není třeba je zavádět v deklarační části programu. PI – Ludolfovo číslo, které má hodnotu 3,14

24


Průvodce studiem: Načtení nebo přiřazení celočíselné hodnoty do proměnné reálného typu nezpůsobí chybu. Dojde k automatické konverzi (převodu) celého čísla na číslo s desetinnou částí . Obráceně to neplatí ! Nelze tedy do proměnné celočíselného typu načíst nebo přiřadit číslo s desetinnou částí. Taktéž je dobré si uvědomit, že pokud je proměnná deklarována jako proměnná reálného typu, nelze s ní provést operace DIV a MOD, i když byste do ní uložili číslo celé. Již při uložení dojde ke konverzi celého čísla na číslo s desetinnou částí. Kontrolní otázky:

1. 2. 3. 4. 5. 6. 7. 8.

K čemu slouží datové typy ? Čím se od sebe liší jednotlivé datové typy pro celá čísla ? Které operace jsou dovoleny pro celočíselné proměnné ? Čím se od sebe liší jednotlivé datové typy pro desetinná čísla ? Které operace jsou dovoleny pro reálné proměnné ? Které znáte předdefinované celočíselné konstanty ? Které znáte předdefinované reálné konstanty ? Jaký význam mají pro programátora předdefinované konstanty ?

3.2.

Logická proměnná - datový typ (BOOLEAN)

Průvodce studiem:

Někdy se při řešení algoritmu dostanete do situace, kdy mohou nastat pouze dva stavy. Buď se „něco stane“ nebo „se nestane“ a je třeba si pamatovat, který stav nastal.V těchto případech zavádíme tzv. přepínač, což je proměnná, která bude nabývat pouze dvou různých hodnot. Datový typ této proměnné pak obvykle závisí na programátorovi. Jako velmi vhodné se ale jeví použití tzv. logické proměnné, protože do této proměnné lze uložit pouze dvě hodnoty – logickou pravdu nebo logickou nepravdu. V dalším textu jsou uvedeny všechny potřebné informace o logické proměnné. Logickou hodnotu zavedete v deklarační části programu za klíčovým slovem Var pomocí klíčového slova BOOLEAN. Do této proměnné pak lze uložit pouze logickou hodnotu. Za logickou hodnotu jsou v Borland Pascalu považována slova: • TRUE (neboli logická pravda) • FALSE (neboli logická nepravda). Také pro tento typ proměnné lze určit množinu dovolených hodnot a množinu dovolených operací.

25

Algoritmy a datové struktury 1 Množina hodnot: TRUE - logická pravda (logická 1) FALSE - logická nepravda (logická 0) Logická hodnota zabírá v paměti 1B. Množina operací:

a) = <> > >= < <=

relační operace … rovná se … nerovná se … větší než … větší nebo rovno … menší než … menší nebo rovno

b) logické operace NOT … logická negace AND … logický součin OR … logický součet XOR … neekvivalence (exkluzivní součet) Pravdivostní tabulka R S FALSE FALSE FALSE TRUE TRUE FALSE TRUE TRUE

NOT R TRUE TRUE FALSE FALSE

R AND S R OR S FALSE FALSE FALSE TRUE FALSE TRUE TRUE TRUE

R XOR S FALSE TRUE TRUE FALSE

Pro lepší zapamatování:: • NOT TRUE je FALSE a naopak • Výsledek operace AND je TRUE, mají-li oba operandy hodnotu TRUE • Výsledek operace OR je TRUE, má-li alespoň jeden operand hodnotu TRUE • Výsledek XOR je TRUE, jsou-li hodnoty operandů rozdílné (neekvivalentní) Práce s logickou proměnnou má pro programátora určitá omezení: • Hodnotu do logické proměnné můžeme dostat pouze přiřazením pomocí přiřazovacího příkazu: B := TRUE; nebo B := FALSE; • Do logické hodnoty nelze načíst • Obsah logické proměnné lze vytisknout. • Logické proměnné můžeme přiřadit buď přímo konstanty TRUE nebo FALSE nebo můžeme přiřadit výsledek logického výrazu. • Logický výraz je výraz, jehož výsledkem je logická hodnota TRUE nebo FALSE (to znamená, že výraz obsahuje alespoň jeden relační nebo logický operátor).

26

Algoritmy a datové struktury 1 Průvodce studiem: Význam logické proměnné vám asi nyní není úplně zřetelný. Zdá se vám tato proměnná pro práci málo použitelná ? Opravdu to tak může někdo pochopit, ale pokusím se vám na ukázkových příkladech přiblížit využití logické proměnné. V prvním ukázkovém příkladu je zařazena možnost přiřazení výsledku logického výrazu do logické proměnné. V dalším příkladu je logická proměnná použita pro testování skutečnosti, zda nastala nebo nenastala stanovena událost. Příklad přiřazení výsledku logického výrazu do logické proměnné: Sestavte program, který požádá o zadání dvou čísel a na obrazovku vytiskne tvrzení „první číslo je větší než číslo druhé: „ a za tímto tvrzením vytiskne TRUE nebo FALSE v závislosti na zadaných hodnotách.

Program testovani; Var Test:boolean; X,Y:Integer; Begin Write (‘ zadej prvni cislo: ‘); Toto je přiřazení výsledku Readln(X); logikého výrazu do log. Write (‘ zadej druhe cislo: ‘); proměnné Readln(Y); Test := X > Y; Writeln (‘ první cislo je vetsi nez cislo druhe: ‘, Test); End. Program lze samozřejmě sestavit i bez použití přiřazení výsledku logického výrazu do logické proměnné. Zdrojový text by pak vypadal následovně:

Program testovani_1; Var Test:boolean; X,Y:Integer; Begin Write (‘ zadej prvni cislo: ‘); Readln(X); Write (‘ zadej druhe cislo: ‘); Readln(Y); If X > Y Then Test := TRUE Else TEST := FALSE; Writeln (‘ první cislo je vetsi nez cislo druhe: ‘, Test); End.

27

Algoritmy a datové struktury 1 Příklad: Sestavte program, který požádá o zadání hledané hodnoty a pak začne postupně načítat N čísel. Každé načtené číslo srovná s hledanou hodnotou X. Celý program skončí v okamžiku, kdy se zadaná hodnota rovná hodnotě hledané nebo skončí načtením N čísel. Význam proměnných: N Počet čísel na vstupu X Hledaná hodnota a Proměnná pro načtení hodnoty p Počítadlo B Logická proměnná, ve které je uložena informace o tom, zda hodnota byla nalezena Program vyhledani_hodnoty; var a,p,n,X:integer; b:boolean; begin write('zadej pocet cisel: '); readln(n); Write ('zadej hledane cislo '); readln (X); p:=1; b := False; while (p <= n) and (b = False) do begin write('zadej ',p,'. cele cislo: '); readln(a); If a = X then b := True; p:=p+1; end; writeln('Hledane cislo bylo nalezeno: ',b); writeln; write('zmackni ENTER '); readln; end.

Průvodce studiem: V programu jsem zařadila logickou proměnnou, pomocí které na konci cyklu zjistím, zda byla či nebyla hodnota nalezena. Důležité je před příkazem cyklu do logické proměnné dát jednu z možných hodnot – v programu je přiřazena hodnota FALSE (není povinné přiřadit na začátku FALSE, klidně můžete přiřadit hodnotu TRUE, ale pak musíte další algoritmus přizpůsobit této počáteční hodnotě). V těle cyklu pak každou načtenou hodnotu testujeme, zda se rovná hodnotě hledané – je zařazen rozhodovací příkaz. Cyklická činnost se opakuje na základě složené podmínky, jejíž význam je v tom, že ukončí cyklus: - buď až po načtení všech N hodnot – v tom případě hledaná hodnota nebyla mezi zadanými a v logické proměnné je FALSE - nebo na základě změny obsahu logické proměnné na TRUE – to pak znamená, že hledaná hodnota byla na vstupu.

28

Algoritmy a datové struktury 1 Shrnutí:

V Borland Pascalu existují logické hodnoty TRUE a FALSE. Logickou proměnnou lze zavést pomocí klíčového slova BOOLEAN. S logickou proměnnou lze provádět pouze relační a logické operace. Pro práci s touto proměnnou existuje jedno podstatné omezení, a sice to, že do této proměnné nelze načíst hodnotu pomocí příkazu READLN. Hodnotu do logické proměnné lze pouze přiřadit pomocí přiřazovacího příkazu. Vytisknou obsah logické proměnné lze. Do logické proměnné lze přiřadit výsledek logického výrazu. Vzhledem k tomu, že tato proměnná může nabývat pouze dvou hodnot, využívá se v programování hlavně jako přepínač mezi dvěmi možnými stavy.

Kontrolní otázky 1. Jak se zavede logická proměnná ? 2. Jakých hodnot může logická proměnná nabývat ? 3. Kdy a proč je vhodné použít logickou proměnnou ? 4. Jak lze do logické proměnné dostat hodnotu ? 5. Které operace lze s logickou proměnnou provádět ? 6. Co znamená a jaké výsledky dává logický součin, logický součet a neekvivalence ? 7. Lze obsah logické proměnné vytisknout ? 8. Co znamená přiřazení výsledku logického výrazu do logické proměnné?

3.3.

Znaková proměnná - datový typ CHAR

Průvodce studiem:

Doposud jste pracovali většinou s číselnou proměnnou. S přibývajícími znalostmi problematiky využití programovacího jazyka pro řešení algoritmu narazíte na potřebu zpracovávat nejen čísla, ale také jednotlivé znaky a řetězce znaků. V jazyku Borland Pascal je možné číst ze vstupu a dále zpracovávat textové údaje. V dalším této kapitole vám vysvětlím práci s jedním znakem, v následující kapitole pak práci s řetězcem znaků. Pascalu existuje datový typ, který umožňuje deklarovat proměnnou tak, že do ní lze uložit jeden znak. Proměnnou s touto vlastností zavedeme v deklarační části programu v úseku Var pomocí klíčového slova CHAR. Množina hodnot Do proměnné typu CHAR můžeme uložit libovolný znak z ASCII tabulky. Je rozdíl mezi malým a velkým písmenem. V paměti proměnná typu CHAR zabere 1 B.

29


Množina operací Můžeme použít pouze relační operace: = … rovná se <> … nerovná se > … větší než >= … větší nebo rovno < … menší než <= … menší nebo rovno Standardní funkce

ORD(x) … funkce, která vrací číslo (pořadí) znaku v ASCII tabulce, tj. číslo z intervalu 0 ..255. CHR(c) … funkce, která vrací znak, který odpovídá danému číslu v ASCII tabulce PRED(x) … funkce, která vrací znak, který v ASCII tabulce má pořadové číslo o 1 menší než znak uvedený jako argument funkce SUCC(x) … funkce, která vrací znak, který v ASCII tabulce má pořadové číslo o 1 větší než znak uvedený jako argument funkce UPCASE(x) ..funkce, která převádí malé písmeno na velké. Pokud je argumentem funkce jiný znak než malé písmeno, zůstává argument beze změny. Možnosti zápisu znakových konstant ve zdrojovém textu: •

Uzavření znaku mezi apostrofy. Toto lze použít pouze pro zobrazitelné znaky. • Jakýkoliv znak lze zapsat pomocí symbolu # a celého čísla bez znaménka vyjadřujícího pořadí znaku v ASCII tabulce. Např.: #7 …. zvonek #13 … enter Upozornění: stejný význam jako znak # má funkce CHR( ). #7 a CHR(7) dávají stejný výsledek (zvonek).

Průvodce studiem:

Datový typ CHAR je pro programátora určitým komfortem. Dovoluje totiž programátorům zlepšit komunikaci s uživatelem. V následujícím příkladu je ukázka použití proměnné typu CHAR pro získání odpovědi uživatele na dotaz opakování celého algoritmu. Samozřejmě byste úspěšně mohli použít proměnnou číselnou. Ale právě zde bych doporučovala využívat proměnné typu CHAR.

30


Příklad: Sestavte program, který požádá o zadání poloměru kruhu a vypočítá a vytiskne obvod a obsah kruhu. Načtení hodnoty poloměru se opakuje v případě, že zadaná hodnota je menší nebo rovna nule. Po zobrazení výsledku se zobrazuje dotaz, zda celý výpočet zopakovat. Uživatel si zvolí pomocí nabídnutých písmem další postup. Program opakovani_vypoctu; uses crt; var r:integer; obvod,obsah:real; odp:CHAR; begin repeat clrscr; repeat write('Zadej polomer: '); readln(r); until r>0; obvod:=2*PI*r; obsah:=PI*sqr(r); writeln('obvod: ',obvod:0:2,' obsah: ',obsah:0:2); writeln; repeat write('chces opakovat vypocet ? A=Ano,N=Ne: '); readln(odp); until (UPCASE(odp) = 'A') or (UPCASE(odp) = 'N'); until Upcase(odp) = 'N'; end. Průvodce studiem:

V programu je jako příkaz cyklu zařazen příkaz s podmínkou na konci. Úkol by se dal samozřejmě řešit i pomocí příkazu cyklu s podmínkou na začátku, ale pro tyto algoritmy je nejvhodnější právě cyklus s výstupní podmínkou, protože je nutné, aby se příkazy těla cyklu provedly alespoň jednou – načtení poloměru a taktéž výpočet obvodu a obsahu kruhu. Pro zjištění odpovědi uživatele jsem zařadila proměnnou typu CHAR, proto uživatel může odpovědět zadáním příslušného písmenka. Vnořený příkaz cyklu REPEAT zajistí, aby uživatel byl donucen zadat pouze jedno z dovolených písmen, funkce UPCASE (odp) řeší problém rozdílu mezi malými a velkými písmeny. Funkce UPCASE je vysvětlena v kapitole 3.3 Znaková proměnná.

31


4. Strukturovaná proměnná Cíl:

Po nastudování této části textu byste měli umět: - orientovat se v problematice uložení dat ve formě datových struktur - definovat strukturované datové typy - charakterizovat datové typy pro jednorozměrné a dvourozměrné pole - charakterizovat datový typ množina - demonstrovat využití těchto typů na příkladech Průvodce studiem:

Při sestavování algoritmu jste se doposud soustředili hlavně na to, které kroky a v jakém pořadí provést, abyste dosáhli požadovaného výsledku. Nyní byste se měli začít zamýšlet také nad tím, jak co nejlépe vstupní data, potřebné mezivýsledky a výsledné hodnoty v paměti uložit. Všechny úlohy, které jste řešili, byly zadány tak, že stačilo do operační paměti uložit jednu vstupní hodnotu, tu zadaným způsobem zpracovat a v dalším kroku pak tuto vstupní hodnotu přepsat vstupní hodnotou novou. Pokud byste ale potřebovali po zpracování poslední vstupní hodnoty se vrátit k některým (nebo všem) vstupním hodnotám, museli byste je znovu zadat. To by bylo dosti nepohodlné a bylo by to také zdrojem chyb. Takže pokud při sestavování algoritmu vyplyne potřeba mít k dispozici (v operační paměti) vstupní data po celou dobu vykonávání programu, doporučuje se zvolit uložení dat ve formě tzv. datové struktury. V programovacím jazyku Borland Pascal je možnost využívat datové struktury pro uložení dat dána vhodnou deklarací proměnné v deklarační části programu. Pak hovoříme o tzv. strukturované proměnné. Pro strukturovanou proměnnou platí: • strukturovaná proměnná má svou vnitřní strukturu, člení se na jednodušší části (prvky, položky, komponenty) • se strukturovanou proměnnou lze pracovat buď jako s celkem nebo s jejími jednotlivými komponentami, přičemž práce s jednotlivými komponentami se vyskytuje častěji, než práce s proměnnou jako s celkem. Strukturované proměnné dělíme na: homogenní – všechny komponenty jsou stejného datového typu, patří mezi ně proměnná typu řetězec, pole, množina, soubor, výčtový typ a typ interval heterogenní – komponenty mohou být různých datových typů, patří mezi ně datový typ záznam

32


4.1.

Řetězec znaků - datový typ STRING

Klíčová slova: Strukturovaná proměnná, řetězec, nultý byte, délka řetězce, sloučení řetězců, konverze čísla na znak, konverze znaku na číslo.

Proměnná typu STRING je určena pro práci s řetězcem znaků, tzn. že je možné do takto definované proměnné uložit i více než jeden znak (slovo, větu). Proměnná tohoto typu se zavede v deklarační částí programu v úseku Var pomocí klíčového slova STRING. 2 způsoby deklarace proměnné typu STRING: •

a:STRING[30]; … do proměnné a se uloží pouze 30 znaků, ostatní budou ignorovány proměnná v paměti zabere 31 B

•

a: STRING; … do proměnné a je možno uložit až 255 znaků proměnná v paměti zabere 256 B

BORLAND PASCAL přidává k proměnné typu STRING na počátek řetězce interně 1 byte, který obsahuje skutečnou délku řetězce. Tato délka je indexována jako nultý byte . Skutečná délka řetězce je uložena ve formě znaku, pro převod do číselné podoby použijeme standardní funkce ORD( ). Délku řetězce lze také zjistit pomocí standardní funkce LENGTH( ). Máme deklaraci … Retez:STRING; Pak platí: ORD( Retez[0] ) = LENGTH(Retez) Retez[0] slouží k uložení aktuální délky řetězce Retez, délka je uložena ve formě znaku. Proměnná typu STRING patří mezi strukturované proměnné, a proto je možno pracovat: • jako s celkem • nebo s jednotlivými byty (znaky). Pokud pracujeme s jednotlivými znaky, přistupujeme ke znakům pomocí hranatých závorek. Příklad: Var Retez: STRING; I:Integer; Begin Retez := ‘AHOJ’; nebo Readln (Retez);

33


nebo Retez[1] := ‘A’; Retez[2] := ‘H’; Retez[3] := ‘O’; Retez[4] := ‘J’; Writeln(Retez); nebo For I:= 1 To Length(Retez) do Write(Retez[I]); Writeln; End. Průvodce studiem:

V uvedeném programu vidíte, že je možné jedním příkazem READLN načíst celý řetězec do paměti a také je možné jedním příkazem WRITELN vytisknout celý řetězec na obrazovku. Toto platí pouze pro strukturovanou proměnnou typu STRING. Celá práce s touto proměnnou se velmi zjednoduší. Taktéž existuje v Borland Pascalu existuje mnoho předdefinovaných funkci a procedur pro práci s řetězci. Všechny níže uvedené podprogramy pracují s proměnnou jako s celkem. Je vhodné o těchto podprogramech vědět, protože vám to velmi usnadní práci s řetězci. Asi by se vám podařilo sestavit algoritmy, které by vykonávaly činnosti řešené pomocí standardních podprogramů, ale bylo by to dost pracné. Přesný popis níže uvedených podprogramů je možno získat v nápovědě programovacího jazyka. Standardní podprogramy pro práci s řetězcem jako s celkem: LENGTH – vrací délku řetězce CONCAT – sloučí posloupnost textových řetězců

Tato funkce je zavedena kvůli kompatibilitě s ostatními kompilátory. Naprosto stejný výsledek dostaneme při použití operátoru plus (+). Např.: S:= ‘ABC’ + ‘DEF’; S:= CONCAT(‘ABC‘, ‘DEF‘);

Dostaneme stejný výsledek S = ABCDEF

COPY – vrací definovanou část řetězce (podřetězec)

COPY(S, zacatek, počet) Řetězec

od které kolik Pozice znaků

34


Např.: VAR S:string; BEGN

Výsledek: S:= ‘ABCDEF‘; S:= COPY(S,2,3);

S = BCD

END., DELETE – vyjme z řetězce jeho část DELETE(S, zacatek, počet) Řetězec

od které kolik Pozice znaků

Např.: VAR S:string; BEGN

Výsledek: S:= ‘ABCDEF‘; DELETE(S,2,3);

S = AEF

END.

INSERT – vkládá do řetězce podřetězec od udané pozice

INSERT(zdroj, S, pozice) Co budeme řetězec,do kterého od které Vkládat vkládáme pozice Např.: VAR S:string; BEGN S:= ‘Karel Macha‘ ; INSERT(‘Hynek ‘ ,S,7);

Výsledek: S = Karel Hynek Macha

END. POS – hledá pozici zadaného řetězce v jiném řetězci, výsledkem je číslo

POS (hledany, S) Hledaný Řetězec

řetězec, ve kterém hledáme

35


Např.: X:= POS(‘CDE‘, ‘ABCDEEFXXBCDE‘);

výsledek: X = 3

VAL – převádí řetězec na číselnou hodnotu VAL(S, V, kod)

Řetězec S musí obsahovat posloupnost znaků, které odpovídají syntaktickým pravidlům TP pro zápis čísla příslušného typu. V tom případě VAL převede S na číselnou hodnotu, kterou uloží do proměnné V. Jestliže proběhla konverze úspěšně, je hodnota proměnné KOD nulová. Pokud řetězec S obsahuje nedovolené znaky, je v proměnné KOD nenulová hodnota, která udává pozici prvního znaku, který zmařil konverzi. Např.: VAL (12A0, N,Chyba) je písmeno

v proměnné Chyba bude hodnota 3, neboť třetí znak

STR – převede číselnou hodnotu do podoby znakového řetězce

STR(X[:celkem[:deset]], S); V proměnné X bude číslo – celé nebo s desetinnou částí Celkem - počet znaků, které výsledný řetězec zaujme Deset - počet míst pro desetinnou část numerické hodnoty Např. X := 123.50 ; STR(X:8:2,S); V proměnné S bude osm prvních míst obsazeno číslem 123.50, přičemž první dvě místa budou mít mezeru. Shrnutí:

Pro práci s textem je určena proměnná typu STRING. Do této proměnné lze uložit maximálně 255 znaků, jeden znak (nultý znak) je určen pro uložení aktuální délky řetězce. Tato proměnná patří mezi strukturované datové typy, což znamená, že s ní můžeme pracovat jako s celkem, ale také s jejími jednotlivými částmi. Přístup k jednotlivým částem se realizuje pomocí hranatých závorek a pořadového čísla znaku ve větě. Práce s řetězci je rozdílná v různých programovacích jazycích. V Borland Pascalu existuje mnoho standardních procedur a funkcí, které práci s řetězci velmi usnadní.

36

Algoritmy a datové struktury 1 Kontrolní otázky:

1. Jaké vlastnosti má strukturovaný datový typ ? 2. Co znamená, že datový typ je homogenní ? Které datové typy mají tuto vlastnost ? 3. Co je to řetězec ? 4. Jak deklarujeme proměnnou pro práci s řetězci ? 5. K čemu slouží nultý byte v řetězci ? 6. Jak zjistíte délku řetězce ? 7. Jak pracujeme s jednotlivými komponentami řetězce ? 8. Které standardní podprogramy pro práci s řetězci znáte ?

4.2.

Jednorozměrné pole

Klíčová slova: Pole hodnot, prvek pole, indexovaná proměnná, deklarace pole, datový typ indexu, datový typ prvku pole, úsek TYPE, pole jako formální parametr podprogramu.

Nejznámějším představitelem datové struktury je pole údajů. Je to datová struktura, která má předem pevně stanovený počet prvků, proto také říkáme, že je to statická datová struktura. Položky se vzájemně rozlišují pomocí indexu. V operační paměti tato struktura zabírá souvislý úsek. Datový typ pole patří mezi strukturované homogenní datové typy. 4.2.1. Deklarace jednorozměrného pole v programu

Při deklaraci proměnné typu pole se určuje jeho název, rozměr a datový typ prvků pole. Rozměr pole určuje počet prvků, které se do pole mohou vložit. Velikost pole je vždy omezena paměťovými nároky. Jednorozměrné pole odpovídá matematickému objektu vektor. Příklad deklarace pole: VAR A : ARRAY [1 .. 100] OF INTEGER; Název proměnné typu pole Klíčové slovo, které nám říká, že jde o datový typ pole (ARRAY = pole) Určuje počet prvků pole a současně hodnoty indexů Určuje datový typ prvků pole

37


Prvky jednorozměrného pole označujeme názvem proměnné typu pole a indexem v hranatých závorkách. Např.: A[1] := 10; … do prvního prvku pole A jsme přiřadili hodnotu 10 A[2] := -5; … do druhého prvku pole A jsme přiřadili hodnotu -5 Hodnota indexu nemusí být uvedena přímo konstantou. Na místě indexu může být i proměnná, např.: A[k] je odkaz na k-tý prvek pole A. Musí ale platit, že v našem případě k je číslo z intervalu <1,100>. Obecně: na místě indexu může být konstanta, název proměnné nebo výraz příslušného typu. Typ hodnot ukládaných do jednotlivých prvků pole může být: - celočíselný - reálný - logický (BOOLEAN) - CHAR - STRING - Pole - Záznam Počet prvků pole se určuje jako interval z typů celočíselných , CHAR nebo BOOLEAN. Příklady deklarací: B : ARRAY[-3 .. 2] OF CHAR; C : ARRAY[‘A’ .. ‘D‘] OF REAL; D : ARRAY[1001 ..1003] OF INTEGER; E : ARRAY[False .. True] OF STRING[5] ;

B: N A Z D A R -3 -2 -1 0 1 2 Přístup k prvkům pole B:

B[-3] , B[-2] , B[-1] , B[0] , B[1] , B[2]

C: 1.23 0.17 -5.31 0.0 ‘A’ ‘B’ ‘C’ ‘D’ Přístup k prvkům pole C: C[‘A‘] , C[‘B‘] , C[‘C‘] , C[‘D‘] D: -17 3 161 1001 1002 1003 Přístup k prvkům pole D: D[1001] , D[1002] , D[1003] E: Dnes Zítra False True Přístup k prvkům pole E: E[False] , E[True] 38

Algoritmy a datové struktury 1 4.2.2. Význam úseku CONST a TYPE pro definici datových typů Průvodce studiem:

Při práci se strukturovanou proměnnou typu pole považuji za vhodné Vás upozornit na možnost využití úseků CONST a TYPE v programu. Úsek CONST slouží k zavedení objektu, který nazýváme konstanta.

Pravidla pro zavedení konstanty: pro název konstanty platí stejná pravidla jako pro stanovení jakéhokoliv jiného identifikátoru v prostředí Borland Pascalu konstantě se v okamžiku jejího zavedení v úseku CONST přiděluje hodnota. Datový typ konstanty je závislý na tom, jaká hodnota jí byla přidělena. Obsah takto zavedené konstanty nelze během vykonávání programu měnit mezi název konstanty a její hodnotu je nutné vložit znak „rovnítko“. Pokud změníme hodnotu konstanty v úseku Const, bude program všude tam, kde je konstanta použita, pracovat s touto novou hodnotou. Příklad: Const N = 20; Koef = 2.5; Chyba = ‘ !!! chyba na vstupu !!!‘;

Konstanta N je celočíselná Konstanta Koef je reálná Konstanta Chyba je řetězec

Úsek TYPE slouží k pojmenování a definování datového typu

Obecně: TYPE Název_dat_typu = popis datového typu ;

Pravidla pro zavedení datového typu:

Pro stanovení názvu platí stejná pravidla jako pro stanovení jakéhokoliv jiného identifikátoru v prostředí Borland Pascalu (viz. kapitola „Algoritmus a program“). Pro popis datového typu slouží klíčová slova a parametry, pomocí kterých je datový typ přesně popsán. Mezi název a popis je nutné vložit znak „rovnítko“.

39


Příklad: CONST N = 10 ; TYPE Tpole = Array [1..N] of Integer ;

Tento zápis má stejný význam:

VAR A:Tpole ;

VAR A:Array[1..N] of Integer ;

CONST N = 10 ;

V popisu datového typu je použita konstanta N. Zavedení konstanty pro uložení počtu prvků pole je výhodné, protože pokud počet prvků pole potřebujeme změnit, stačí provést opravu v úseku CONST. Význam zavedení datového pomocí úseku TYPE:

Pokud dojde ke změně některých parametrů datového typu (např. změna typu hodnot prvků pole), stačí provést opravu v popisu úseku TYPE Proměnné, kterým je přidělen datový typ definovaný v úseku TYPE jsou kompatibilní.

4.2.3. Práce s proměnnou typu pole

Jedná se o strukturovaný datový typ a proto platí, že s proměnnou můžeme pracovat jako s celkem nebo s jejími jednotlivými komponentami. a) práce s jednotlivými prvky pole Můžeme provádět takové operace, které jsou dovoleny pro datový typ, který jsme pro prvky pole nadeklarovali b) práce s polem jako s celkem Lze provést pouze operaci přiřazení. Přiřazení lze provést, pokud jsou obě proměnné typu pole totožného typu. A právě zde může dojít k problémům s kompatibilitou datových typů.

40

Algoritmy a datové struktury 1 Příklad: Máme zaveden vlastní datový typ Tpole v úseku TYPE a pak proměnné A a B tohoto typu. Pak máme v deklarovanou proměnnou C, která je taktéž typu pole a na první pohled je viditelné, že typ této proměnné je zaveden stejně jako náš typ Tpole. Přesto Borland Pascal považuje oba datové typy za různé.

TYPE TPole = ARRAY [1 .. 3] of Real; VAR A,B: TPole; C:ARRAY[1 .. 3] of Real; … Begin A:=B; … toto přiřazení je v pořádku C:=B; … toto přiřazení není v pořádku, protože z hlediska Pascalu pole C a B nejsou totožného typu (nemají společný popis datového typu). End. I když je popis datového typu pole v úseku TYPE stejný jako v úseku VAR u proměnné C, přesto nejsou chápány v Borland Pascalu tyto typy jako stejné a překladač hlásí chybu, pokud provedeme příkaz přiřazení C:=B .

Průvodce studiem:

Nyní již máte dostatek informací o datovém typu pole. Možná vám ještě není úplně jasné, jak velký přínos pro programátora má datový typ pole. Představte si, že máte zpracovat 100 celých čísel a potřebujete je mít všechny uloženy v paměti, protože je potřebujete použít vícekrát. Samozřejmě byste mohli deklarovat 100 různých proměnných celočíselného typu. Další práce by ale pro vás byla hodně vyčerpávající, protože např. pro načtení hodnot do proměnných byste museli zařadit 100 krát příkaz READLN( ), taktéž tisk obsahu proměnných na obrazovku by byl realizován pomocí 100 příkazů pro tisk. Pokud využijete možnosti zavést proměnnou typu pole, práce se vám velmi zjednoduší. Ukázka toho, jak pracovat s proměnnou typu pole, následuje níže.

41

Algoritmy a datové struktury 1 Příklad: Sestavte program, který uloží do paměti 100 celých čísel zadaných z klávesnice. Pro uložení hodnot použijte proměnnou typu pole. Obsah jednotlivých prvků pole vytiskněte na obrazovku vedle sebe na řádek oddělené čárkou.

Program pole1; Var A:Array [1..10] of integer; I: Integer; Begin Write(‘zadej 1. cele cislo: ‘); Readln(A[1]); Write(‘zadej 2. cele cislo: ‘); Readln(A[2]); . . Write(‘zadej 100. cele cislo: ‘); Readln(A[100]);

Řešení bez příkazu cyklu: Takto by bylo možné postupně načíst do všech proměnných hodnotu. Příkaz READLN ( ) by musel být zařazen 100 krát.

Tento postup ale nepoužíváme !!!

Správný postup pro načtení do všech prvků pole: For I := 1 To 100 Do Begin Write(‘zadej‘, I , ‘. cele cislo: ‘); Readln(A[I]); End; Writeln(‘Obsah pole :’);

Řešení načtení pomocí příkazu cyklu s řídící proměnnou !

Tisk všech prvků pole

For I:= 1 To 100 Do write(A[I],’ , ‘); Writeln; End. Průvodce studiem:

Pro práci s polem můžete použít libovolný příkaz cyklu. Ale právě pro práci s proměnnou typu pole je nejpohodlnější použít příkaz cyklu s řídící proměnnou (FOR). Použijte jej vždy, když se potřebujete dostat postupně ke všem prvkům pole – naplnění pole hodnotami, vytištění obsahu pole, prohledávání všech prvků, apod. V některých algoritmech ale příkaz FOR není úplně nejvhodnější. Jsou to algoritmy, kdy potřebujeme ukončit procházení pole na základě vyhodnocení nějaké podmínky, např. algoritmus zjištění, zda pole obsahuje nějakou konkrétní hodnotu. Pak použijte příkaz cyklu s podmínkou na začátku nebo na konci.

42

Algoritmy a datové struktury 1 Příklad: Sestavte program, který uloží do paměti 20 celých čísel zadaných z klávesnice a zjistí, zda mezi zadanými čísly byla hodnota X. Pro uložení hodnot použijte proměnnou typu pole. Obsah jednotlivých prvků pole vytiskněte na obrazovku vedle sebe na řádek oddělené čárkou.

Význam proměnných: A ... název pole I ... řídící proměnná cyklu(index pole) X ... hledaná hodnota B ... logická proměnná pro pamatování, zda se hodnota X v poli nachází Vývojový diagram:

Začátek I:=1,2,…,20 I:=1,2,…,20 Zadej číslo Tisk: A[I]

Čti: A[I]

Zadej hledané číslo Čti: X I := 1 B := FALSE

-

(B= FALSE) AND (I<=20)

+ +

A[I] = X

+

B = True

-

Hodnota X nalezena

B:= True I := I + 1

Hodnota X nenalezena

Konec

43

Algoritmy a datové struktury 1 Program v Borland Pascalu:

program Pole2; uses crt; Const N = 20; Type Tpole = array[1..N] of integer; Var i,X:integer; A: Tpole; B:Boolean; begin clrscr; for i:= 1 to N do begin write('zadej ',i,'. cislo: '); readln(A[i]); end; for i:= 1 to N do write(A[i],' '); writeln; Write('zadej hledane cislo: '); Readln(x); B:= False; I:= 1; while (B=False) and (i<=N) do begin if A[i] = X then B:=true; i:=i+1; end; If B = True Then writeln('cislo ',X,' bylo nalezeno') Else writeln('cislo ',X,' nebylo nalezeno'); writeln('zmackni enter'); readln; end.

4.2.4. Proměnná typu pole a podprogramy Průvodce studiem:

Pokud studujete tento učební text postupně, je vám problematika tvorby podprogramů v programovacím jazyku Borland Pascal známá. Vy, kteří nestudujete postupně, se nyní musíte vrátit ke 2. kapitole „Podprogramy v Borland Pascalu“ a doplnit své vědomosti.

44


Proměnná typu pole se může objevit na místě formálních parametrů obou dovolených typů podprogramů – procedur a funkcí. Samozřejmě jí pak musíte zařadit také při volání těchto podprogramů, tedy na místě skutečných parametrů. Abyste se vyvarovali problémům se syntaxi a také problémům s nečekanými logickými chybami, postupujte takto: • datový typ pole zaveďte využitím úseku TYPE • tento datový typ použijte pro deklaraci formálních parametrů a taktéž globálních proměnných • jako skutečný parametr uveďte jen jméno globální proměnné – bez hranatých závorek. Příklad: Sestavte program, který uloží do paměti N celých čísel zadaných z klávesnice a vypočítá aritmetický průměr zadaných hodnot a zjistí, kolik hodnot je menších, než průměr. Pro načtení a pro tisk sestavte vlastní procedury, pro výpočet průměru sestavte vlastní funkci. Význam proměnných: A ... název pole N …počet prvků pole I ... řídící proměnná cyklu(index pole) Nacti …název procedury pro načtení do pole Tisk …název procedury pro tisk prvků pole Prum_hodnota ... název funkce pro výpočet průměru Prumer ... proměnná pro uložení výsledku volání funkce Prum_hodnota Pocet …proměnná pro uložení počtu čísel menších než je průměr Rozbor: Při řešení budeme předpokládat, že pole nebude mít více než 100 prvků. Tento předpoklad musíme udělat, abychom mohli udělat definici pole. Konkrétní počet prvků pole budeme zadávat z klávesnice a ukládat do proměnné N. Vývojový diagram podprogramu pro načtení do pole: Začátek procedury Nacti

I:=1,2,…,Poc Zadej číslo

Konec procedury Nacti

Čti: A[I]

45


Zápis v Borland Pascalu:

Procedure Nacti (var A: Tpole; Poc:Integer); Var I:integer; Begin For I := 1 to Poc Do Begin Write(‘Zadej cislo: ‘); Readln(A[I]); End; End; Průvodce studiem:

Sestavit tuto proceduru pro načtení hodnot do pole není vůbec těžké. Jen vás chci upozornit na chybu, která se často objevuje. Cílem této procedury je uložit do pole hodnoty. Dochází ke změně obsahu formálního parametru A a tato změna se musí promítnout do skutečného parametru. Je tedy nezbytné, aby před formálním parametrem A bylo klíčové slovo VAR, které zajistí, že se změněný obsah pole přenese do skutečného parametru (do hlavního programu). Parametr A tady plní funkcí výstupního parametru. Vývojový diagram podprogramu pro tisk prvků pole:

Začátek procedury TISK

I:=1,2,…,Poc Tiskni: A[I]

Konec procedury TISK


Procedure Tisk (A: Tpole; Poc:Integer); Var I:integer; Begin For I:= 1 to Poc Do Writeln(A[I]); End; 46


Průvodce studiem:

Také sestavení procedury pro vytištění všech prvků pole je jednoduché. Při činnosti této procedury je pole naplněné hodnotami a obsah pole se tiskem nemění. Proto před formálním parametrem A není třeba uvádět klíčové slovo VAR , parametr A tady plní pouze funkcí vstupního parametru. Pokud byste klíčové slovo VAR zařadili, nedojde k žádné chybě.

Vývojový diagram podprogramu pro výpočet průměrné hodnoty prvků pole:

Začátek funkce Prum_hodnota

S:=0 I:=1,2,…,Poc S := S + A[I]

Prum_hodnota := S / Poc

Konec funkce Prum_hodnota


Function Prum_hodnota (A: Tpole; Poc:Integer):real; Var I, S:integer; Begin S := 0; For I := 1 to Poc Do S:= S+A[I]; Prum_hodnota := S/I ; End;

47


Vývojový diagram programu - použité podprogramy zde jsou rozkresleny jako jeden krok.

Začátek

Zadej počet prvků pole Čti: N Volání procedury pro čtení Nacti(A,N); Volání procedury pro tisk

Tisk(A,N);

Prumer:= Prum_hodnota(A,N); Pocet:= 0 Tisk: Prumer

I:=1,2,…,N

+

A[I] < Prumer

Tisk: Pocet

Počet:=Počet+1 Konec

48

Algoritmy a datové struktury 1 Zápis v Borland Pascalu: program pole3; const R = 100; type Tpole = array[1..R] of integer; var N,i,Pocet:integer; A:Tpole; Prumer:real; procedure nacti(var a:Tpole;Poc:integer); var i:integer; begin for i:= 1 to Poc do begin write('Zadej cislo: '); Readln(a[i]); end; end; procedure Tisk(a:Tpole;Poc:integer); var i:integer; begin for i:= 1 to Poc do write(a[i],' '); writeln; end; Function Prumer_hodnota(a:Tpole; Poc:integer):Real; var i,S:integer; begin S:=0; for i:= 1 to Poc do S:= S + A[i]; Prumer_hodnota := S/Poc; end; begin Write('Zadej pocet prvku pole :'); readln(N); nacti(A,N); tisk(A,N); Prumer := Prumer_hodnota(A,N); Writeln('Prumerna hodnota je: ',Prumer:10:2); pocet:=0; for I:= 1 to N do If A[I] < Prumer then Pocet := Pocet +1; writeln('Pocet hodnot mensich nez prumer je ', pocet); writeln; writeln('zmackni enter'); readln; end.

49

Algoritmy a datové struktury 1 Kontrolní otázky:

1. Jak vypadá deklarace jednorozměrného pole ? 2. Podle čeho poznáme, kolik prvků jednorozměrného pole máme k dispozici ? 3. Jaký datový typ můžeme použít pro index pole ? 4. Jaký datový typ můžeme použít pro typ jednotlivých prvků pole ? 5. Jaký je vztah mezi datovým typem indexu a datovým typem prvků pole? 6. K čemu slouží úsek CONST ? 7. K čemu slouží úsek TYPE ? 8. Které operace můžeme provádět s proměnnou typu pole jako s celkem ? 9. Které operace můžeme provádět s jednotlivými komponentami proměnné typu pole ? 10. Který příkaz cyklu je nejlépe použitelný pro práci s proměnnou typu pole ? 4.2.5. Korespondeční úkol č. 2 Zadání:

Sestavte vývojový diagram a program, který uloží do paměti N celých čísel zadaných z klávesnice a nalezne mezi nimi nejmenší hodnotu. Pro načtení a pro tisk sestavte vlastní procedury, pro nalezení minima sestavte vlastní funkci. Ke kontrole pošlete vývojový diagram a zdrojový text programu sestavený v prostředí Borland Pascal.

4.3.

Vícerozměrná pole

Klíčová slova: Pole polí, matice, řádek, sloupec, indexovaná proměnná, naplnění pole, tisk pole ve tvaru matice, náhodné číslo, generátor náhodných čísel.

Borland Pascal dovoluje, aby prvky pole měly opět strukturu pole. Tímto způsobem pak vznikne pole polí, nebo-li dvourozměrné pole. 4.3.1. Deklarace dvourozměrného pole v programu

TYPE TYDEN = ARRAY[1 .. 7] OF ARRAY [1 .. 24] OF REAL; Typ TYDEN charakterizuje dvojrozměrné pole – týden má 7 dní, každý den má 24 hodin. Pole tohoto typu slouží k uložení hodnot typu REAL.

50


V praxi však zpravidla tuto rozepsanou formu deklarace nahrazujeme ekvivalentní zkrácenou formou zápisu: TYPE TYDEN = ARRAY[1 .. 7, 1 .. 24] OF REAL; Počet řádků

Počet sloupců

Přístup k položkám dvojrozměrného pole realizujeme pomocí indexované proměnné (název proměnné a index v hranatých závorkách). Např.: TYPE TYDEN = ARRAY[1 .. 7, 1 .. 24] OF REAL; VAR A:TYDEN;

totožný význam má tento zápis: VAR A:ARRAY[1 .. 7, 1 .. 24] OF REAL;

Proměnná se jmenuje A, je to pole, které má 7 řádků a 24 sloupců. 4.3.2. Práce s dvourozměrným polem

Dvojrozměrné pole odpovídá matematickému objektu matice. Jedná se o strukturovaný datový typ a proto platí, že s proměnnou můžeme pracovat jako s celkem nebo s jejími jednotlivými komponentami. a) práce s polem jako s celkem Lze provést pouze operaci přiřazení. Přiřazení lze provést, pokud jsou obě pole totožného typu. Platí stejná pravidla jako u jednorozměrného pole. b) práce s jednotlivými prvky pole můžeme provádět takové operace, které jsou dovoleny pro datový typ, který jsme pro prvky pole nadeklarovali Přístup k jednotlivým položkám je přes dva indexy, které jednoznačně definují číslo řádku a číslo sloupce. Např. A[ 1, 2 ] ... prvek pole A, který leží v prvním řádku a ve druhém sloupci Obecně: A[ i , j ] … prvek pole A, který leží v i-tém řádku a j-tém sloupci. číslo řádku

číslo sloupce

51


Průvodce studiem:

Při práci s proměnnou typu dvourozměrné pole je důležité, abyste si uvědomili, které prvky máte k dispozici a jak se k nim dostanete. Níže uvedená ukázka deklarace a následný výpis názvu prvků pole Vám pomůže zorientovat se v dané problematice. TYPE Tpole = ARRAY[1 .. 3, 1 .. 4] OF REAL ; VAR A:Tpole;

Prvky, které máme dispozici jsou tyto: A[ 1, 1 ] A[ 1, 2 ] A[ 1, 3 ] A[ 1, 4 ] A[ 2, 1 ] A[ 2, 2 ] A[ 2, 3 ] A[ 2, 4 ] A[ 3, 1 ] A[ 3, 2 ] A[ 3, 3 ] A[ 3, 4 ] V programu obvykle potřebujeme se dostat ke každému prvku deklarovaného pole. Nejjednodušší řešení spočívá v použití dvou příkazů cyklu s řídící proměnnou. Načtení hodnoty do každého prvku pole lze provést takto: For I := 1 TO 3 do Begin For J := 1 TO 4 do Begin Write(‘Zadej číslo: ‘); Readln(A[I,J]) ; End; End; Postup provádění: a) Příkaz s řídící proměnnou I přiřadí do proměnné I hodnotu 1, což je pro nás první řádek. b) Pak se začne vykonávat tělo cyklu tohoto příkazu. Tělo cyklu je tvořeno příkazem cyklu s řídící proměnnou J, která postupně nabude hodnot 1, 2, 3 a 4 . c) Pro každou tuto hodnotu provede načtení čísla, znamená to tedy, že načte postupně čísla do proměnných A[1, 1], A[1, 2], A 1, 3] , A[1, 4] d) Pak dojde k návratu na příkaz cyklu s řídící proměnnou I, hodnota I se automaticky zvedne o jedničku, tzn. má nyní hodnotu 2 (druhý řádek) a opakuje se činnosti od bodu b). Tak se postupně načtou hodnoty do proměnných druhého a třetího řádku.

Uvedený postup naplnil pole po řádcích. Je samozřejmě možné naplnit pole tak, že se budou hodnoty zadávat po sloupcích. Při takovémto řešení by vnější cyklus měl řídící proměnnou J (číslo sloupce) a vnitřní cyklus proměnnou I (číslo řádku). Viz. následující řešení:

52


For J := 1 TO 4 do Begin For I := 1 TO 3 do Begin Write(‘Zadej číslo: ‘); Readln(A[I,J]) ; End; End; Vytištění obsahu všech prvků dvourozměrného pole lze provést v různé podobě. Výše deklarované pole má celkem 12 prvků. Tyto prvky můžete vytisknou do jednoho řádku vedle sebe, nebo všechny prvky do jednoho sloupce nebo ve tvaru matice. A právě tisk ve tvaru matice je nejvíce názorný a provede se takto:

For I := 1 TO 3 do Begin For J := 1 TO 4 do Write(A[I,J] , ‘ ‘); {tisk prvků jednoho řádku vedle sebe} Writeln; {tento příkaz způsobí při tisku přechod na nový řádek } End; Průvodce studiem:

Nyní jste se seznámili s možností využití dvourozměrného pole pro uložení dat. Abyste ale při hledání řešení konkrétního úkolu rozpoznali, že právě uložení dat ve formě dvourozměrného pole je pro vás to nejvýhodnější, musíte přesně znát, jak s touto proměnnou můžete pracovat. My se nyní zaměříme na tuto oblast a veškeré úkoly budou bez návaznosti na reálné problémy. Tím jsem vám chtěla sdělit, že pro nás není důležité, jaké hodnoty máme v poli uložené, ale jak tu kterou akci vykonat. Proto ve všech dalších úkolech budeme zajišťovat naplnění pole náhodnými čísly, abychom se vyhnuli pracnému zadávání z klávesnice. V dalším odstavci vás seznámím s generováním náhodných čísel.

4.3.3. Generátor náhodných čísel

V prostředí Borland Pascalu je pro generování (získání) náhodného čísla k dispozici standardní funkce s názvem RANDOM. Tato funkce má dvě podoby: •

X := Random ; Takto zapsaná funkce vygeneruje číslo s desetinnou částí z intervalu < 0, 1 )

•

X := Random (10) ;

53


Takto zapsaná funkce vygeneruje celé číslo z intervalu < 0, 10 ), tzn. že může vygenerovat některé z čísel 0, 1, 2, 3, 4 ,5 ,6, 7, 8 nebo 9. Nikdy nevygeneruje číslo 10. V kulaté závorce za Random je možno uvést: • přímo číselnou konstantu tak, jak je uvedeno výše • nebo je možno do závorky dát název celočíslené proměnné Pokud potřebujeme z nějakého důvodu vyloučit ze zpracování nulu, můžeme pak generování náhodného čísla zapsat takto: X := Random (10) + 1 ;

Funkce Random(10) bude generovat některé z čísel 0, 1, 2, 3, 4 ,5 ,6, 7, 8 nebo 9, ale do proměnné se uloží vždy vygenerovaná hodnota zvětšená o jedničku, tzn. 1, 2, 3, 4 ,5 ,6, 7, 8, 9 nebo 10. Pro generování náhodných čísel je v prostředí Borland Pascalu zabudován algoritmus, který uživatel nemusí znát, pouze jej využívá prostřednictvím funkce RANDOM. Tento algoritmus začíná výpočet náhodného čísla od předem definované hodnoty. Abychom si zajistili, že po každém spuštění programu budou generovaná čísla v jiném pořadí, musíme do programu ještě před prvním voláním funkce RANDOM zařadit volání procedury RANDOMIZE. Pak výpočet náhodného čísla bude začínat v závislosti na systémovém čase a tím je zajištěno, že generovaná čísla budou v jiném pořadí.

Příklad: Do čtvercového pole o N řádcích a N sloupcích uložte celá náhodná čísla z intervalu <1,100>. Pole vytiskněte ve tvaru matice. Vypočítejte součet prvků na hlavní diagonále a součet prvků na vedlejší diagonále. Rozbor: Čtvercová matice je dvourozměrné pole, které má stejný počet řádků jako sloupců.

Pojmy, které se vztahují ke čtvercové matici: Hlavní diagonála - prvky, které leží na úhlopříčce zleva doprava. Tyto prvky mají totožné číslo řádku a číslo sloupce. Vedlejší diagonála – prvky, které leží na úhlopříčce zprava doleva program ctvercova_matice; Type Tpole = array[1..50,1..50] of integer; var pole:Tpole; N,hlavni,vedlejsi:integer;

54

Algoritmy a datové struktury 1 procedure napln(var a:Tpole;N:integer); var i,j:integer; begin randomize; for i:= 1 to N do for j:=1 to N do a[i,j]:=random(100)+1; end; procedure vytiskni(a:Tpole;N:integer); var i,j:integer; begin randomize; for i:= 1 to N do begin for j:=1 to N do write(a[i,j]:3); writeln; end; writeln; end; function hlavni_diagonala(a:Tpole;N:integer):integer; var i,s:integer; begin s:=0; for I:=1 to N do s:=s+a[i,i]; hlavni_diagonala:=s; end; function vedlejsi_diagonala(a:Tpole;N:integer):integer; var i,j,s:integer; begin s:=0; j:=N; for I:=1 to N do begin s:=s+a[i,j]; j:=j-1; end; vedlejsi_diagonala:=s; end; begin Write('Zadej velikost matice: '); Readln(N); napln(pole,N); vytiskni(pole,N); hlavni:=hlavni_diagonala(pole,N); vedlejsi:=vedlejsi_diagonala(pole,N); writeln('soucet na hlavni diagonale: ',hlavni); writeln('soucet na vedlejsi diagonale: ',vedlejsi); writeln; write('zmackni ENTER: '); readln; end.

55


Kontrolní otázky:

1. 2. 3. 4. 5. 6. 7.

Jak vznikne dvourozměrné pole ? Co označuje první index v definici dvourozměrného pole ? Co označuje druhý index v definici dvourozměrného pole ? Jak funguje v Borland Pascalu generátor náhodných čísel ? K čemu slouží funkce RANDOM ? Jaké možnosti máme při volání funkce RANDOM ? Kterému pojmu z matematiky odpovídá jednorozměrné pole ? 4.3.4. Korespondenční úkol č. 3

Zadání: Sestavte program, který naplní dvourozměrné pole o M řádcích a N sloupcích náhodnými čísly a vytiskne ve tvaru matice. Pak vypočítá součet prvků v každém sloupci a součet prvků v každém řádku. Rozbor: • předpoklad: maximální počet řádků je 20 a maximální počet sloupců je 30. • hodnoty M a N zadávejte z klávesnice, zajistěte, aby nedošlo k zadání větších hodnot, než jsou maximální hodnoty. • pro načtení a tisk pole sestavte vlastní procedury • pro uložení součtů v řádcích použijte jednorozměrné pole s názvem R_soucty • pro uložení součtů ve sloupcích použijte jednorozměrné pole s názvem S_soucty • ke kontrole pošlete zdrojový text programu

56


4.4.

Množina hodnot

Klíčová slova: Množina, bázový typ, prázdná množina, konstruktor množin, sjednocení množin, průnik množin, rozdíl množin, náležitost k množině, relace na množinách. Průvodce studiem:

Programovací jazyk Pascal má k dispozici datový typ množina, který není příliš často zařazován do programování. Považuji za vhodné vás seznámit s možnostmi, výhodami i nevýhodami takové datové struktury. Základní charakteristika datové struktury množina: • Všechny položky struktury musí být stejného datového typu, dovolené jsou pouze ordinální datové typy • Položky se ve struktuře nemohou opakovat • Každé položce je přiděleno ordinální číslo z rozsahu 0 .. 255 Obecná definice typu množina v Pascalu:

SET OF ordinální datový typ;

Základem pro definování typu množina je vždy určitý ordinální datový typ, tzv. bázový typ. Příklady definování proměnné typu množina: X: set of CHAR ; Z: set of ‘A’ .. ‘Z’; Cisla: set of 0 .. 9 ; Průvodce studiem:

Tím, že deklarujete podle platných pravidel proměnnou typu množina, neznamená to, že proměnná takto deklarovaná má obsah daný deklarací, např. že proměnná Z z výše uvedené deklarace nemá jako svůj obsah velká písmena anglické abecedy. Tato proměnná je prázdná množina. Je to stejné, jako když deklarujete proměnnou Y: CHAR. Po této deklaraci je obsahem proměnné Y mezera (v případě, že se jedná o globální proměnnou), případné náhodná hodnota (pokud se jedná o lokální proměnnou). Pro zajištění obsahu proměnné typu množina nám slouží tzv. konstruktory množin, které jsou vysvětleny v další části textu.

57

Algoritmy a datové struktury 1 4.4.1. Konstruktory množin:

Hodnoty proměnné typu množina zapisujeme do hranatých závorek, do tzv. konstruktoru. Pomocí přiřazovacího příkazu pak tyto hodnoty uložíme do proměnné typu množina. Způsoby zápisu množin: uvedeme do hranatých závorek seznam hodnot bázového typu oddělených čárkou skupinu po sobě jdoucích hodnot bázového typu můžeme zapsat uvedením nejmenší a největší hodnoty, oddělených symbolem dvě tečky (interval) prvky množiny mohou být určeny i libovolným výrazem bázového typu Např.: TYPE SKUPINA = (Jan,Petr,Vaclav); VAR Tym : SET OF SKUPINA; Proměnná tym je typu množina a může nabývat hodnot, které jsou množinami vytvořenými z prvků bázového typu, v našem případě se jedná o výčtový typ. Proměnná tym může nabývat hodnot: Tym := [ ] ; prázdná množina Tym := [ Jan] ; Tym := [Petr ] ; Tym := [Vaclav] ; Tym := [ Jan,Petr] ; Tym := [Jan,Vaclav] ; Tym := [Petr,Vaclav] ; Tym := [ Jan,Petr,Vaclav] ; Tym := [Jan .. Vaclav ] ; Maximální počet těchto množin v našem příkladu je 23 = 8. Ordinální čísla prvků jsou z intervalu 0..2. Příklady správných i chybných deklarací proměnné typu množina: VAR Mn1 : SET OF ‘A‘ .. ‘Z‘ SPRÁVNĚ! maximální počet prvků je 26, ordinální čísla jsou 65 .. 90 Mn2 : SET OF 0 .. 20 SPRÁVNĚ! maximální počet prvků je 21, ordinální čísla jsou 0 .. 20 Mn3 : SET OF 10 .. 270 CHYBA ! maximální počet prvků je 261 – dovoleno je 256 Mn4 : SET OF 300 .. 310 CHYBA !..ordinální čísla jsou mimo interval 0 .. 255

58

Algoritmy a datové struktury 1 4.4.2. Množinové operace

Do proměnnou typu množina nelze načíst hodnoty pomocí příkazu Read (nebo Readln). Lze hodnotu do této proměnné pouze přiřadit pomocí přiřazovacího příkazu. Nelze obsah proměnné typu množina vytisknout pomocí příkazu Write (Writeln). Řešení vytištění obsahu takovéto proměnné je v řešeném příkladu č.2. Množinové operace: a) sjednocení množin operátor + Výsledkem sjednocení množin A + B je množina obsahující všechny prvky sjednocovaných množin. V programu to zajišťuje možnost přidání prvku do množiny. b) rozdíl množin operátor Rozdílem množin A-B je množina, která obsahuje prvky množiny A, které nejsou v množině B. V programu to zajišťuje možnost odebrání prvku do množiny. c) průnik množin operátor * Průnikem množin A*B je množina, která obsahuje společné prvky obou množin. V programu to zajišťuje jednoduchý způsob nalezení prvků, které jsou současné pro obě množiny. d) Test náležení k množině X IN A ; X je prvkem množiny A (X musí být ordinálního typu) d) Relace na množinách (výsledkem je logická hodnota TRUE nebo FALSE) A <= B množina A je podmnožinou B A >= B množina obsahuje množinu B A <> B množina A není totožná s množinou B A=B množiny obsahují totožné prvky Příklad:

TYPE INTER = 1.. 3; SI = Set of INTER; VAR J : INTER; SJ : SI;

typ interval typ množina Proměnná typu interval, může nabývat hodnot 1, 2 a 3 (např. J := 1). Proměnná typu množina, může nabývat hodnot: [] prázdná množina [ 1], [2], [3] jednoprvkové množiny [1,2], [1,3], [2,3] dvouprvkové množiny [1,2,3] tříprvková množina

59


Průvodce studiem:

Prostudováním textu týkajícího se datové struktury množina jste získali informace o tom, že programovací jazyk Pascal umožňuje využití datové struktury množina zavedením proměnné typu množina. Asi vás ale nyní nenapadá, jak toto vše využít. V další části textu jsem zařadila ukázky použití množiny na algoritmech, které jste v předchozích úkolech řešili bez použití množiny. Příklad: Přečtěte větu z klávesnice a zjistěte, kolik tato věta obsahuje velkých písmen, malých písmen a kolik ostatních znaků. Sestavte proceduru, jejímž vstupním parametrem je zadaná věta a výstupem jsou počty písmen a znaků. Pro řešení použijte datový typ množina. Rozbor: V proceduře deklarujeme lokální proměnné typu Set OF CHAR, v příkazové části musíme proměnným typu množina přiřadit hodnotu pomocí konstruktoru množin. Při rozhodování o jaký znak se jedná, použijeme operátor IN. Řešení v Borland Pascalu: Program Pismena_a_ostatni_znaky; { program zjisti počet velkých, počet malých písmen a počet ostatních znaků } uses Crt; var s:string; m,v,o:integer; Procedure veta (s:string; var V,M,O:integer); var velka,mala:Set Of Char; I:integer; begin velka := ['A'..'Z']; mala := ['a'..'z']; for I:= 1 to length(s) do if s[I] IN velka then inc(v) else if s[I] IN mala then Inc(m) else Inc(o); end; begin clrscr; writeln('Napis readln(s); veta(s,v,m,o); writeln('pocet writeln('pocet writeln('pocet write('Zmackni readln; END.

vetu:'); velkych pismen: ',v); malych pismen: ',m); ostatnich znaku: ',o); ENTER');

60


Příklad: Sestavte program, jehož vstupem budou dvě posloupnosti celých čísel z intervalu <1,50>. První posloupnost bude obsahovat K hodnot – uložte do množiny A. Druhá posloupnost bude obsahovat N hodnot – uložte do množiny B. Upozornění: jednotlivé prvky zařazujte do množiny pomocí množinového operátoru +. Vytvořte množinu C, která bude obsahovat pouze ty hodnoty, které se nacházejí v množině A i množině B. Vytiskněte obsah množiny A, B a C. Rozbor: V tomto algoritmu budeme vytvářet ze zadaných hodnot množinu A a B. S využitím operátoru plus je vytvoření množiny velmi pohodlné. Tady je třeba si pouze uvědomit, že v množině se hodnoty nemohou opakovat. Sestavení množiny C, která má obsahovat společné prvky množin A a B provedeme pomocí operátoru hvězdička (průnik množin). Poněkud složitější je výpis obsahu množiny. Neexistuje cyklus přes všechny prvky množiny, jako např. u statického pole. Musíme řešit takto: víme, že v množině jsou pouze hodnoty z intervalu <1,50> (viz. zadání). Zařadíme cyklus FOR P:= 1 to 50 a při každém průchodu tělem cyklu testujeme, zda hodnota řídící proměnné je v množině. Pokud ano, tak ji vytiskneme. Řešení v Borland Pascalu: Program mnozina; { program vytváří dvě množiny ze zadaných hodnot, třetí množina vzniká jako jejich průnik. Obsah všech množin se vytiskne. } type inter = 1..50; var K,N,I:integer; p:inter; A,B,C:set of inter; begin Write('Pocet prvku mnoziny A: '); Readln(N); A:=[]; For I:= 1 to N do Begin write('Zadej ',i,'. prvek mnoziny A : '); readln(p); A:= A+[p]; end; Write('Pocet prvku mnoziny B: '); Readln(K); B:=[]; For I:= 1 to K do begin write('Zadej ',i,'. prvek mnoziny B : '); readln(p); B:= B+[p]; end; writeln; Write('vypis mnoziny A: '); Write('['); for p:= 1 to 50 do if p IN A then write(p,',');

61

Algoritmy a datové struktury 1 writeln(#8,']'); Write('vypis mnoziny B: '); Write('['); for p:= 1 to 50 do if p IN B then write(p,','); writeln(#8,']'); writeln; C := A*B; If C=[] then writeln('Prunik mnozin A a B je prazdna mnozina') else begin write('Prunik mnozin A a B je mnozina: ['); for p:= 1 to 50 do if p IN C then write(p,','); writeln(#8,']'); end; writeln; writeln('zmackni ENTER'); readln end.

4.4.3. Korespondenční úkol č. 4 Zadání: Sestavte program, který vygeneruje 6 různých čísel z intervalu 1 .. 49 (čísla do SPORTKY). Využijte datový typ množina. Rozbor: Deklarujeme proměnnou CISLA: set of INTEGER; její hodnotu definujeme příkazem: CISLA:= [1 ..49]; V programu pak postupně generujte čísla z intervalu <1,49>. Pokud číslo je v dané množině, uložte jej do pole a z množiny jej odstraňte (odečteme).

Kontrolní otázky: 1. Jak se deklaruje datový typ množina ? 2. Co je to bázový typ ? 3. Jakého typu mohou být položky v množině ? 4. Mohou se hodnoty v množině opakovat ? 5. Kolik položek může být maximálně v množině ? 6. Jak se hodnotám v množině přiřazují ordinální čísla a jakém rozmezí se mnohou pohybovat ordinální čísla pohybovat ? 7. Lze do proměnné typu množina načíst hodnoty pomocí příkazu Read (Readln) ? 8. Co je to konstruktor množin ? 9. Lze vytisknout obsah proměnné typu množina příkazem Write (Writeln) ? 10. K čemu slouží při práci s proměnnou typu množina operátory plus, mínus a hvězdička ? 11. K čemu slouží operátor IN ? 12. K čemu slouží operátory >, >=, <, <=, = ?

62


4.5.

Proměnná typu záznam

Cíl:

Po prostudování této kapitoly byste měli být schopni: - rozpoznat situace, kdy je vhodné pro uložení dat využít datovou strukturu záznam - charakterizovat zvláštnosti práce s proměnnou typu záznam - využít možnost ukládání dat do pole záznamů - demonstrovat využití těchto typů na příkladech

Klíčová slova: Záznam, položky záznamu, datový typ položek, záznam v záznamu, tečková konvence, příkaz WITH, pole záznamů.

Při návrhu algoritmu řešení některých úloh se dostáváme do situace, kdy o jednom objektu si musíme pamatovat informace různých datových typů. Příkladem může být třeba informace o studentovi, kdy potřebujeme znát jeho jméno, data narození, prospěch. Každý s těchto údajů je jiného datového typu, ale patří ke stejnému objektu. A právě v takových případech je velmi vhodné pro uložení dat použít datovou strukturu záznam. Datový typ záznam je strukturovaný heterogenní datový typ. Proměnná typu záznam se skládá z dílčích položek, které mohou být různých datových typů.

Průvodce studiem:

Existence datového typu záznam vám především umožní v Borland Pascalu řešit úlohy databázového typu. Řešení těchto typů úloh je v Borland Pascalu sice hodně pracné, ale přesto se základní kroky naučíme. Příkladem datové struktury může být informace o studentovi, která obsahuje: Jméno: 20 znaků Den, měsíc, rok narození: 3 celočíselné údaje Označení třídy: 3 znaky Průměrný prospěch: reálné číslo Zdravotní stav: 0 – špatný, 1 – vyhovující, 2 – výborný

63


Pro práci s takovou strukturou se v Pascalu využívá datový typ záznam, jehož obecný popis v programu vypadá takto: RECORD Název položky_1: datový typ; Název položky_2: datový typ; .. Název položky_n: datový typ; END; Strukturu o studentovi můžeme popsat takto: RECORD jmeno : String[25]; den,mesic,rok: INTEGER; trida : ARRAY[1 .. 3] OF CHAR; prospech : REAL; zdr_stav : 0 .. 2; END; Tento záznam obsahuje 5 sekcí, v jedné sekci uvádíme popis jedné nebo více položek stejného typu. Uvedený popis záznamu lze použít v úseku deklarací typů (TYPE) nebo přímo v deklaraci proměnné v úseku VAR. Výhodnější je deklarovat nejdříve typ záznam a pak tento typ použít pro deklaraci proměnných. Např.: TYPE Tstudent = RECORD Jmeno : ARRAY[1 .. 20] OF CHAR; … ZDR_STAV: 0 .. 2; END; VAR Student, X : Tstudent; …

Tímto způsobem jsme deklarovali nový datový typ záznam, který se jmenuje Tstudent, a pak jsme zavedli 2 proměnné Student a X typu Tstudent. Průvodce studiem:

Při práci se strukturovanými datovými typy se běžně využívají vlastní datové typy, které se zavádějí v úseku TYPE. Proto bych doporučila těm z vás, kteří v této problematice nemáte úplně jasno, abyste se vrátili ke 4.2. Jednorozměrné pole doplnili své znalosti o úseku TYPE. Princip práce s proměnnými typu záznam a) Práce s jednotlivými položkami proměnné typu záznam

64


Pro přístup k jednotlivým položkám se uplatňuje tzv. tečková konvence. Jednotlivé položky proměnné Student jsou: Student.jmeno Student.den Student.mesic Student.rok Student.trida Student.prospech Student.zdr_stav S jednotlivými položkami proměnné typu záznam můžeme provádět všechny operace, které jsou pro příslušný datový typ povoleny. Položky trída je typu pole znaků. Přístup k jednotlivým prvkům tohoto pole tak bude vypadat takto: Student.trida[1] … první znak označení třídy Student.trida[2] … druhý znak označení třídy Student.trida[3] … třetí znak označení třídy b) práce se proměnnou typu záznam s celkem

Lze provést pouze operaci přiřazení. Přiřazení lze provést, pokud jsou obě proměnné typu záznam totožné (kompatibilní). Student := X; Tento příkaz přesune obsahy všech položek záznamu X do odpovídajících položek záznamu Student.

4.5.1. Využití příkazu WITH

Příkaz WITH usnadňuje (zkracuje) zápis při práce s položkami proměnné typu záznam. Student.den := 5; Student.mesic := 1; Student.rok := 1970;

Lze zapsat:

With Student Do Begin Den := 5; Mesic := 1; Rok := 1970; End;

65


4.5.2. Pravidla pro tvorbu identifikátorů (názvů) položek záznamu a) položky patřící do jednoho popisu typu záznam musíme pojmenovat různě

TYPE A = RECORD Cislo:REAL; Cislo:INTEGER; END;

dojde k chybě při překladu

b) položka v záznamu může mít stejný identifikátor, jako položka vně popisu typu záznam. Identifikátory položek záznamu považujeme za lokální a nemají vliv na vnější (globální) identifikátory. Příklad: TYPE Tzaznam = RECORD x,y,z : INTEGER; END;

VAR Zaznam : Tzaznam; z: CHAR; pak lze přiřadit: z := ‘A’; zaznam.z := 10;

… jedná se o jednoduchou proměnnou typu CHAR … jedná se o celočíselnou položku proměnné záznam

c) dva stejné popisy typu záznam, přestože obsahují položky shodných jmen i typů, nejsou kompatibilní. VAR zaz1: RECORD A,b,c:INTEGER; END;

zaz2 : RECORD a,b,c:INTEGER; END; Při této deklaraci nejsou zaz1 a zaz2 kompatibilní a není možno napsat zaz1 := zaz2;

66


Aby byly proměnné zaz1 a zaz2 kompatibilní, je třeba provést deklaraci takto: TYPE Tzaznam = RECORD a,b,c: INTEGER ; END; VAR zaz1,zaz2:integer; Pak lze napsat

totožný význam: VAR zaz1,zaz2 : RECORD a,b,c:INTEGER; END;

zaz1 := zaz2;

4.5.3. Záznam v záznamu

TYPE Tdatum = RECOED den,mesic,rok:INTEGER; END; Tosoba = RECORD jmeno:STRING[10]; prijmeni:STRING[15]; dat_nar:Tdatum; zdr_stav: 0 .. 2; END; VAR Osoba : Tosoba; Přístup k položkám proměnné Osoba: Osoba.jmeno Osoba.prijmeni Osoba.dat_nar.den Osoba.dat_nar.mesic Osoba.dat_nar.rok Osoba.zdr_stav

Je vhodné použít příkaz WITH, který zápis identifikátorů položek velmi zkrátí.

67


4.5.4. Pole záznamů Průvodce studiem:

Proměnná typu záznam umožňuje efektivním způsobem uložit a zpracovat různorodé informace o jednom objektu. Pokud ale potřebujete uložit a zpracovat data o více objektech, pak je třeba se zamyslet nad tím, jaký je nejlepší způsob uložení těchto dat. Jako nejlepší se jeví vytvoření pole záznamů, kdy každý prvek pole obsahuje všechny údaje jednoho objektu. Můžeme pak využít všech možností, která platí pro práci s polem. Lepší než zdlouhavý popis, co a jak je možné, je prostudovat si níže uvedený příklad. Pro ty, kteří si nevybavují potřebné znalosti z problematiky datového typu pole, doporučuji prostudovat znovu kapitolu 4.2. Jednorozměrné pole. Příklad: Uložte do paměti informace o 20 zaměstnancích. O každém zaměstnanci evidujeme jeho jméno, příjmení a plat. Rozbor: O jednom objektu (zaměstnanci) máme evidovat informace různých datových typů, z čehož vyplývá použití proměnné typu záznam. Máme evidovat informace o 20 zaměstnancích. Pro každého zaměstnance nebudeme zavádět zvláštní proměnnou, ale problém vyřešíme tím, že deklarujeme proměnnou typu pole záznamů. Každý prvek pole bude mít strukturu záznamu.

Type Tclovek = Record jmeno: string; prijm: string; plat :Real; End; Tpole = Array [1 .. 20] of Tclovek; Var Lide:Tpole; I: integer;

Načteme do paměti údaje o 20 zaměstnancích, ukládáme do prvků pole (1 prvek pole = 1 zaměstnanec): Řešení bez použití příkazu WITH Řešení s použitím příkazu WITH

For I:= 1 to 20 do For I:= 1 to 20 do Begin With Lide[I] do Write(‘zadej jmeno zaměstnance: ‘,); Begin Readln(Lide[I].jmeno); Write(‘zadej jmeno zaměstnance: ‘,); Write(‘zadej příjm. zaměstnance: ‘,); Readln(jmeno); Readln(Lide[I].prijm); Write(‘zadej příjm. zaměstnance:’);

68


Write(‘zadej plat zaměstnance: ‘,); Readln(Lide[I].plat); End;

Readln(prijm); Write(‘zadej plat zaměstnance: ‘,); Readln(plat); End;

4.5.5. Vytvoření procedury pro načtení údajů do pole záznamů

Při sestavování podprogramů s využitím strukturované proměnné musíme počítat s tím, že strukturovaná proměnná se může použít jako formální parametr, ale není možné v Borland Pascalu sestavit funkci, jejíž návratová hodnota by byla deklarována jako strukturovaný datový typ. Proto vždy, když výstupem z podprogramu je strukturovaná proměnná, sestavujeme proceduru a výsledek získáváme pomocí formálního parametru volaného odkazem. Const N = 20; Type Tclovek = Record Jmeno: string; prijm: String; Plat:Real; End; Tpole = Array [1 .. N] of Tclovek; Procedure Nacti (var lide:Tpole; N:integer); Var I:integer; Begin For I:= 1 to N do With Lide[I] do Begin Write(‘zadej jmeno zaměstnance: ‘,); Readln(jmeno); Write(‘zadej st. příjmení zaměstnance Readln(prijm); Write(‘zadej plat zaměstnance: ‘,); Readln(plat); End; End; Stejným způsobem se postupuje při jakékoliv práci s polem záznamů. Kontrolní otázky: 1. Kdy je vhodné pro uložení dat zvolit datovou struktur záznam ? 2. Kterým klíčovým slovem začíná deklarace datového typu záznam ? 3. Co je to „tečková konvence“ ? 4. K čemu slouží příkaz WITH ? 5. Které operace je možno provádět s jednotlivými položkami datového typu záznam ? 6. Které operace je možno provádět s proměnnou typu záznam jako s celkem? 7. Kdy je vhodné pro uložení dat využít pole záznamů ?

69

Algoritmy a datové struktury 1 4.5.6. Korespondenční úkol č. 5 Zadání: Sestavte program podle níže uvedeného vývojového diagramu. Vývojový diagram řeší algoritmus: • uložení údajů o N zaměstnancích do operační paměti (do pole záznamů). O každém zaměstnanci evidujeme jeho jméno, příjmení a měsíční plat. Využijte proceduru Nacti. • výpočet průměrného platu zaměstnance • výpis těch zaměstnanců, kteří mají plat vyšší než je průměr

Začátek Volání procedury pro načtení dat Nacti (Lide,N) Pom:= 0 I:=1,2,…,N Pom := pom +

lide[i].plat Pom:= pom / N I:=1,2,…,N

-

Lide[i].plat > pom

+

Tisk: lide[i].jmeno Lide[i].prijm Lide[i].plat

70

konec


Závěr Předložený text Vám dal základní informace z oblasti ukládání dat v operační paměti počítače, které je potřebné znát při zpracování algoritmů pomocí programovacího jazyka Borland Pascal. Při zpracování větších objemů dat se dostanete do situace, kdy budete potřebovat uložit data tak, abyste k nim měli přístup opakovaně (tzn. abyste měli data uložena trvale mimo operační paměť). Programovací jazyk Borland Pascal má prostředky pro uložení dat mimo operační paměť. Tato problematika bude vysvětlena ve dalších studijních textech, týkajících se ostatních bloků studia předmětu Algoritmy a datové struktury.

Literatura Základní literatura

Saptrapa, P.: Pascal pro zelenáče, Neokortex, 2000 Kvoch, M.: Programování v TURBO PASCALU 7.0, KOOP, 1994 Töpfer, P.: Programovací techniky, Prometheus, 1995 Doporučená literatura

Drozd, J., Kryl, M.: Začínáme s programováním, GRADA, 1992 Ježowicz, E., Laga, J.: Základy programování v PASCALU, Státní pedagogické nakladatelství, 1989 Mikula, P.: TURBO PASCAL 7.0 od příkladů k příkazům, GRADA 1993 Vogel, J.,Müller, K.,Jinoch, J.: Programování v jazyku PASCAL, SNTL 1988

71

Algoritmy a datové struktury 1

Recommend Documents