PROGRAMOVANIE V LAZARUSE
PRE MATURANTOV
(učebný text)
Vzdelávacia oblasť:
Matematika a práca s informáciami
Predmet:
Programovanie
Ročník, triedy:
štvrtý
Vypracoval:
Mgr. Andrea Pločicová
Dátum:
2013
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Obsah
Textové súbory ........................................................................................................................................ 1
Dvojrozmerné polia ................................................................................................................................. 3
Záznamy................................................................................................................................................... 7
Triedenie................................................................................................................................................ 10
Práca s myšou ........................................................................................................................................ 17
Použité zdroje: ....................................................................................................................................... 20
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
(Téma)
Textové súbory
V tejto časti sa naučíme:



prečítať obsah textových súborov, spracovať prečítaný obsah;
vytvoriť textový súbor a zapisovať do neho;
zapisovať na koniec vytvoreného textového súboru.
Pri používaní textového súboru v programe je potrebné :
- deklarovať premennú typu TextFile, prostredníctvom ktorej budeme pristupovať
k textovému súboru,
- premennej typu TextFile priradiť konkrétny textový súbor na disku pomocou príkazu:
AssignFile(meno_premennej_typu_TextFile, cesta_k_suboru);
- otvoriť súbor na čítanie alebo zapisovanie údajov (musí sa rozlišovať, či zo súboru
čítame alebo do neho zapisujeme údaje, nedá sa zapisovať aj súčasne z neho čítať);
Reset(meno_premennej_typu_TextFile)
(čítanie)
Rewrite(meno_premennej_typu_TextFile)
(zapisovanie)
- Po ukončení práce s textovým súborom je potrebné ho zatvoriť príkazom
CloseFile(meno_premennej_typu_TextFile).
Skryté značky v textovom súbore:
Na koniec každého riadku sa automaticky vkladá značka <Eoln>.
Na koniec súboru sa vkladá značka <Eof>.
Tieto značky využívame vtedy, keď textový súbor nepoznáme a chceme prečítať celý jeho
obsah. Využijeme pritom funkciu Eof(meno_premennej_typu_TextFile), ktorá vráti hodnotu
true, ak sa ukazovateľ v súbore nachádza na značke <Eof>, teda sme na konci súboru. Inak
vracia hodnotu false.
V prípade, že chceme prečítať celý riadok súboru, použijeme funkciu
Eoln(meno_premennej_typu_TextFile), ktorá vráti hodnotu true, ak sa ukazovateľ v súbore
nachádza na značke <Eoln>, teda sme na konci aktuálneho riadku. Inak vracia hodnotu false.
<Eoln>
<Eoln>
<Eof>
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 1 z 22
(Téma)
Ako vidíme textový súbor my:
Programovanie
v
Lazaruse.
Ako ho vidí prekladač:
|P|r|o|g|r|a|m|o|v|a|n|i|e|<Eoln>| |v|<Eoln>|L|a|z|a|r|u|s|e|.|<Eof>
ukazovateľ
Štandardné procedúry na prácu s textovými súbormi:
AssignFile(f,p)



priradí premennej f meno súboru (alebo zadanie celej cesty na vyhľadanie súboru) p, napr.
AssignFile(f,´udaje.dat´).
premenná f musí byť typu TextFile
p – reťazec (v apostrofoch)
rewrite(f)



otvorí súbor pre zápis
ak súbor už existuje, vymaže jeho obsah
ak nenájde súbor s daným meno, vytvorí ho
append(f)



otvorí súbor pre zápis
súbor musí byť vytvorený
zapisuje za pôvodný obsah súboru
reset(f)

otvorí existujúci súbor pre čítanie
CloseFile(f)

zatvorí otvorený súbor
READ(LN)(f,p)



Čítanie jednej (p) alebo viacerých hodnôt (p1, p2,...pn) z textového súboru f
p, p1 , p2 , ...pn môžu typu: integer, real, char, string
po prečítaní kurzor zostáva v tom istom riadku (READ) alebo sa presúva do nasledujúceho
riadku (READLN)
WRITE(LN)(f,p)



READ(LN)(f,p1 , p2 , ...pn)
WRITE(LN)(f,p1 , p2 , ...pn)
zápis jednej (p) alebo viacerých hodnôt (p1, p2, ...pn) do textového súboru f
p, p1 , p2 , ...pn typu: integer , real , char , string
po zápise kurzor zostáva v tom istom riadku (WRITE) alebo sa presúva do nasledujúceho
riadku (READLN)
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 2 z 22
(Téma)
Dvojrozmerné polia
Môžeme si ich predstaviť ako tabuľku s R riadkami a S stĺpcami. Bunky tabuľky obsahujú hodnoty
prvkov poľa. Napríklad dvojrozmerné pole s 5 riadkami (prvý rozmer) a 4 stĺpcami (druhý rozmer)
dokážeme reprezentovať pomocou nasledovanej tabuľky:
1. stĺpec
2. stĺpec
3. stĺpec
4. stĺpec
1. riadok
4
3
9
2
2. riadok
5
3
9
4
3. riadok
11
6
7
5
4. riadok
3
2
14
4
5. riadok
3
3
6
6
Deklarácia dvojrozmerného poľa
type
meno_typu=array[indexy_riadkov, indexy _stlpcov] of typ_prvkov;
var
meno_pola: meno_typu;
Príklad
type
pole=array[1..3, 1..4] of integer;
var
cisla: pole;
Prístup k prvkom poľa
riadky
1 .. 3
stĺpce
1 .. 4
4
3
9
2
5
3
9
4
2. riadok
11
6
7
5
ľ
3. stĺpec
Načítanie prvkov poľa:
meno_pola[2,3]
ľ
Pri práci s dvojrozmerným poľom je nevyhnutné použiť „vnorený“ cyklus For. Zvyčajne vonkajší cyklus
slúži na spracovanie riadkov a vnútorný spracúva bunky v riadkoch (stĺpce).
Príklad:
Do dvojrozmerného poľa 5R x 4S načítajte náhodné čísla 1..50.
type
pole=array[1..5, 1..4] of integer;
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 3 z 22
(Téma)
var
cisla: pole;
i, j: integer;
riadky i = 1 .. 5
begin
for i := 1 to 5 do
Stĺpce j = 1 .. 4
for j := 1 to 4 do cisla[i, j] := Random(50) + 1;
end;
Pole sa bude napĺňať po riadkoch v poradí: cisla[1,1], cisla[1,2], cisla[1,3]; cisla[1,4],
cisla[2,1], cisla[2,2], cisla[2,3], cisla[2,4]; cisla[3,1], cisla[3,2], cisla[3,3], cisla[3,4],
cisla[4,1], cisla[4,2], cisla[4,3], cisla[4,4]; cisla[5,1], cisla[5,2], cisla[5,3], cisla[5,4]
Výpis prvkov poľa:
Keď chceme vypísať prvky dvojrozmerného poľa ako tabuľku, nestačí použiť rôzne typy „Boxov“, ani
Memo, potrebujeme Image. Vo vonkajšom cykle (riadky) sa po každom výpise celého riadku
posúvame do ďalšieho riadku (v smere osi y) a zároveň sa presúvame k ľavému okraju (v smere osi x).
Vo vnútornom cykle sa po každom vypísanom prvku presúvame v smere osi y doprava.
type
p = array[1..5,1..4] of Integer;
var
pole: p;
i,j,x,y: integer; //[x,y] – súradnice bodu výpisu
begin
x:=5; y:=5;
Vonkajší cyklus
for i:=1 to 3 do begin
for j:=1 to 4 do begin
vnútorný cyklus
Image.Canvas.TextOut(x,y,IntToStr(pole[i,j]));
x:=x + 15;
end;
x:=5;
y:=y + 15;
end;
Matice
Dvojrozmerné polia sa často využívajú v úlohách s maticami.
j=1
 a1,1

 a 2,1
a
 3,1
a1, 2
a 2, 2
a 3, 2
a1,3 

a 2,3 
a3,3 
j=2
j=3
I=1
a1,1
a1,2
a1,3
I=2
a2,1
a2,2
a2,3
I=3
a3,1
a3,2
a3,3
Vlastnosti, ktoré budeme v maticiach zisťovať:
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 4 z 22
(Téma)
 a1,1

 a 2,1
a
 3,1
a1, 2
a 2, 2
a 3, 2
a1,3 

a 2,3 
a3,3 
Prvky nad hlavnou diagonálou, index riadku je menší ako index stĺpca
Prvky na hlavnej diagonále, index riadku je rovnaký ako index stĺpca
Prvky pod hlavnou diagonálou, index riadku je väčší ako index stĺpca
Úlohy:
1.
Vytvorte program, ktorý do matice m x mi (m<=20) s m riadkami (m<=20) a n stĺpcami (n<=20)
vygeneruje náhodné čísla v intervale <1,100> a vypíše priemerný prvok matice, súčet prvkov na
diagonále, pod a nad diagonálou.
2.
Vytvorte program, ktorý do matice s s m riadkami (m<=20) a n stĺpcami (n<=20) vygeneruje
náhodné čísla v intervale <1,100> a vymení 2 riadky alebo 2 stĺpca matice.
3.
Prvky dvojrozmerného poľa (nxm) predstavujú nadmorskú výšku bodov. Zostavte program, ktorý
vypíše najvyššiu nadmorskú výšku, súradnice bodu s najvyššou nadmorskou výškou a
tiež súradnice bodov, ktoré ležia na úrovni mora. Prvky poľa vygenerujte náhodne z intervalu
<0,8000> m. Objekty do formulára umiestnite podľa potreby.
4.
Pozemok obce Počítačovo je rozdelený na N x N
rovnakých parciel (1 < N ≤ 30). V pozemkovej mape
(Obr. 8.) sú uvedení vlastníci jednotlivých parciel.
Obecná cesta je v pozemkovej mape označená číslom 0,
vlastníci parciel majú čísla od 1 do 20. Pozemková·
mapa je deklarovaná ako dvojrozmerné pole NxN
(Prvky do poľa vygenerujte z intervalu <0,20>. Vytvorte
program, ktorý zistí, koľko štvorcov vlastnia jednotliví vlastníci. Prvky do formulára pridajte
podľa potreby.
Využitie komponentu StringGrid pri práci s dvojrozmerným poľom
Komponent StringGrid mám môže uľahčiť prácu s dvojrozmerným poľom. Môžeme si ho predstaviť
ako tabuľku, v ktorej môžeme nastaviť taký počet riadkov a stĺpcov, aby zodpovedala poľu, s ktorým
pracujeme.
Po umiestnení do formuláru nastavíme v Inšpektore objektov tieto vlastnosti:




celkový počet riadkov
celkový počet stĺpcov
počet pevných riadkov
počet pevných stĺpcov
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 5 z 22
(Téma)
Celkový počet stĺpcov - ColCount
Počet pevných stĺpcov – FixedCols
Počet pevných riadkov – FixedRows
Celkový počet riadkov - RowCount
Dvojklikom na komponent sa zobrazí editor,
v ktorom sa dajú vkladať do buniek hodnoty,
presúvať riadky a stĺpce.
Indexy riadkov, stĺpcov, označenie prvkov
komponentu StringGrid
stĺpec 0.
stĺpec 1.
stĺpec 2.
stĺpec 3.
stĺpec 4.
riadok 0.
Označenie riadkov:
<0, RowCount – 1>
riadok 1.
Označenie stĺpcov:
riadok 2.
<0, ColCount – 1>
riadok 3.
Označenie prvku :
StringGrid1.Cells[2,1]
StringGrid1.Cells[index stĺpca, index riadku]
Výpis prvkov dvojrozmerné podľa do komponentu StringGrid.
type
pole=array[0..5,0..8] of real;
var
p: pole;
i,j: integer;
begin
for i:=0 to 5 do
for j:=0 to 8 do
StringGrid1.Cells[j,i] := StrToFloat (p[i,j]);
end;
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 6 z 22
(Téma)
Záznamy
Pri vytváraní programov sme si doteraz mohli všimnúť, že niektoré premenné spolu súvisia (popisujú
vlastnosť jedného objektu). Napríklad premenné X, Y (Integer) sú súradnice jedného bodu v rovine,
alebo premenné Meno, Priezvisko, Vek vyjadrujú informácie o jednej osobe.
Takéto premenné sme doteraz do jedného celku nevedeli združiť. Spôsobom, ako to vyriešiť je
deklarovať vlastný typ, ktorý nám toto umožní – ZÁZNAM (RECORD).
Príklad 1.:
Definujme si nový typ Bod obsahujúci 2 premenné X, Y typu Integer;
type
Bod = record
X: integer;
Y: integer;
end;
Príklad 2.:
Definujme si nový typ Osoba obsahujúcu 3 premenné: Meno(String), Priezvisko (String), Vek (Integer)
type
Osoba = record
meno: string;
priezvisko: string;
vek: Integer;
end;
Po zadefinovaní nových typov môžeme používať štrukturované premenné týchto typov.
Príklad:
var
A: Bod;
ziak: osoba;
Tieto premenné si môžeme predstaviť nasledovne:
ziak
A
Meno
X
Priezvisko
Y
Vek
Používanie záznamov:
Na prístup k položkám záznamu používame operátor . (bodka)
Príklad:
Ziak.meno
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 7 z 22
(Téma)
(ziak musí byť premenná typu záznam a meno položka záznamu)
Príklad uloženia údajov do premennej typu záznam:
Procedure TForm1.Button1.Click(Sender: TObjekt);
type
Osoba = record
meno: string;
priezvisko: string;
vek: Integer;
end;
var
ziak: Osoba;
begin
ziak.meno : = ‘Jožko’;
ziak.priezvisko := ‘Mrkvička’;
ziak.vek := 45;
end;
Pole záznamov
Pri evidovaní väčšieho počtu záznamov je možné deklarovať pole, ktorého prvky budú záznamy.
Príklad:
type
Osoba = record
meno: string;
priezvisko: string;
vek: Integer;
end;
var
ziaci: array[1 .. 5] of Osoba;
pole ziaci
1. prvok
2. prvok
3. prvok
4. prvok
5. prvok
Meno 1. žiaka
Meno 2. žiaka
Meno 3. žiaka
Meno 4. žiaka
Meno 5. žiaka
Priezvisko 1. žiaka
Priezvisko 2. žiaka
Priezvisko 3. žiaka
Priezvisko 4. žiaka
Priezvisko 5. žiaka
Vek 1. žiaka
Vek 2. žiaka
Vek 3. žiaka
Vek 4. žiaka
Vek 5. žiaka
Pristupovanie k prvkom poľa:
meno_pola[index_prvku].nazov_polozky_zaznamu
ziaci[1].meno;
ziaci[1].priezvisko;
ziaci[1].vek;
prvý prvok poľa so všetkými
troma zložkami.
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 8 z 22
(Téma)
Úlohy:
1. Vytvorte program, ktorý by nám pomohol pri práci s diárom na telefónne kontakty. Formulár má
umožňovať zadať meno, priezvisko, telefónne číslo a operátora (T-Mobile, Orange, O2). Po
zatvorení programu sa všetky pridané kontakty prekopírujú do textového súboru diar.txt. Chceme
vedieť pracovať aj s tými kontaktmi, ktoré sme pridali pri predchádzajúcom spustení programu.
Použiť môžete len jedno pole. Komponenty do formulára pridajte podľa potreby.
2. Vytvorte program, ktorý bude do databázy školy načítavať nasledovné informácie o učiteľoch:




meno,
priezvisko,
skratka predmetu, ktorý vyučuje (len jeden),
pohlavie.
Program bude vedieť vypísať zoznam všetkých učiteľov, počet žien a mužov, navyše po zadaní
skratky predmetu vypíše všetkých učiteľov, ktorý daný predmet vyučujú. Komponenty do
formulára umiestnite podľa potreby.
3. Vytvorte program, ktorý umožní jednoduché spravovanie knižnice. Cez vstupný formulár načíta
o knihe tieto informácie:




meno a priezvisko autora,
názov knihy,
vydavateľstvo,
rok vydania
a uloží ich do databázy. Program bude navyše po zadaní priezviska autora vedieť vyhľadať
v databáze všetky knihy od daného autora. Komponenty do formulára umiestnite podľa potreby.
4. V textovom súbore body.txt máme uložené názvy štátov a bodový
zisk za umiestnenia ich športovcov na olympiáde. Vytvorte program,
ktorý tieto štáty usporiada zostupne podľa získaného počtu bodov
s použitím jedného poľa. Komponenty do formulára umiestnite
podľa potreby.
Možné riešenie úlohy 4.
procedura naplnpole naplní pole záznamov údajmi z textového súboru
body.txt. Procedúra vypispole pole vypíše prvky poľa do komponentu Memo1.
type
stat=record
skratka: string;
body: integer;
end;
var
pole:array[1..20] of stat;
pocet: integer = 0;
pole p
1.
prvok
p[1].skratka
2.
prvok
…
p[2].skratka
…
p[1].body
p[2].body
p[1].body
Priezvisko 2. žiaka
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 9 z 22
procedure naplnpole(var p: pole);
var
f: TextFile;
begin
AssignFile(f,'body.txt');
Reset(f);
while not eof(f) do begin
inc(pocet);
readln(f, p[pocet].skratka);
readln(f, p[pocet].body);
end;
CloseFile(f);
end;
procedure vypispole(p: pole);
var
i: integer;
begin
for i:=1 to pocet do
Form1.Memo1.Lines.Add(p[i].skratka + ' : ' +
IntToStr(p[i].body));
end;
Premenná „pocet“ je použitá z toho dôvodu, že dopredu
nepoznáme počet záznamov (počet riadkov v textovom súbore).
Táto premenná má na začiatku inicializovanú hodnotu na nulu a po
každom prečítaní dvoch riadok = 1 záznamu sa jej hodnota zväčší
o jedna.
(Téma)
Triedenie
„Je to jedna z najčastejšie sa vyskytujúcich operácií pri spracovaní údajov, resp. dátových štruktúr.
Usporiadanie množiny prvkov výrazne zvyšuje efektívnosť vyhľadávania prvkov. Typickými príkladmi
triedenia je spracovanie rôznych zoznamov, registrov, skladov, slovníkov a pod.“, (Podlubný, I.: Úvod
do programovania v jazyku C)
Pod triedením postupnosti prvkov budeme rozumieť preusporiadanie jej prvkov do špecifického
poradia. Najčastejšie sa triedia číselné údaje alebo aj textové reťazce. V prípade číselných údajov
môžeme utriediť:
-
od najmenšieho po najväčší (vzostupne)
od najväčšieho po najmenší (zostupne).
Textové reťazce môžeme podobne usporiadať:
- od A po Z (vzostupne)
- od Z po A (zostupne).
Triedenie je nevyhnutné aj v prípade, keby sme chceli v poli použiť efektívny vyhľadávací algoritmus.
Všetky takéto algoritmy pracujú s usporiadanou postupnosťou prvkov.
Ukážka:
Neutriedená postupnosť
8
6
≤
9
≤
4
10
≤
≤
5
≤
Usporiadaná postupnosť
4
5
6
8
9
10
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 10 z 22
(Téma)
V tejto kapitole sa budeme venovať triedeniu jednorozmerného poľa čísel. Algoritmy, ktoré sa
zaoberajú triedením, budeme nazývať triediace algoritmy. Dôležitou vlastnosťou algoritmov je čas,
ktorý potrebujú na usporiadanie postupnosti prvkov. Časová zložitosť algoritmov sa posudzuje podľa
relatívneho času tzv. O-notáciou.
Typy algoritmov:
pomalé (kvadratická zložitosť – O(n2))
efektívnejšie (logaritmická zložitosť – O(nlogn))
BUBBLESORT
QUICKSORT
INSERTSORT
MERGESORT
SELECTSORT
HEAPSORT
Exitujú aj rýchlejšie algoritmy s časovou zložitosťou O(n), tie však predpokladajú u zoraďovaných
prvkov určitú vlastnosť.
BubbleSort (Bublinkové triedenie)
Bubblesort pracuje veľmi jednoducho. Porovnáva každý prvok postupnosti s nasledujúcim, v prípade,
že prvok vľavo je väčší ako vpravo, vymení ich. Názov je odvodený od chovania sa vzdušných
bubliniek. Malé (ľahké) bublinky stúpajú hore, podobne sa malé prvky posúvajú dopredu a veľké
dozadu.
Možné prístupy naprogramovania:
A)
Ľavá časť poľa je neutriedená, pravá utriedená. Postupne prechádzame neutriedenou časťou
postupnosti od začiatku do konca. Ak sa stane, že väčší prvok sa nachádza pred menším prvkom,
vymeníme tieto prvky. Takto sa ľavá neutriedená časť každým krokom zmenší o jeden prvok. Zároveň
sa vždy najväčší prvok neusporiadanej časti poľa dostane na jej koniec a je najmenším prvkom
usporiadanej časti.
Počet prechodov je o jedna menší ako počet prvkov. Počet porovnaní sa v každom prechode
zmenšuje o jedna.
Príklad:
Neusporiadaná postupnosť prvkov
5
1
12
-5
16
Počet prvkov je 5, teda budeme potrebovať 4 prechody. Pri 1. prechode sa uskutočnia 4 porovnania,
pri 2. prechode 3 porovnania, pri 3. prechode 2 porovnania a pri poslednom 4. prechode len 1
porovnanie. Spolu prebehne 10 porovnaní bez ohľadu na výmeny.
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 11 z 22
(Téma)
1.
prechod
2.
prvé porovnanie
5
1
prvé porovnanie
12
-5
16
1
5 > 1, vymenia sa
5
12
-5
16
1
12
16
utriedená časť
5
-5
12
5>-5, vymenia sa
tretie porovnanie
5
-5
druhé porovnanie
5<12, zostávajú
1
5
1 < 5, zostávajú
druhé porovnanie
1
prechod
16
utriedená časť
tretie porovnanie
12
-5
16
1
-5
12>-5, vymenia sa
5
12
16
5 < 12, zostávajú utriedená časť
štvrté porovnanie
1
5
-5
12
16
12<16, zostávajú
3.
prechod
4.
prvé porovnanie
1
-5
prechod
prvé porovnanie
5
1 > -5, vymenia sa
12
16
-5
1
-5 < 1, zostávajú
utriedená časť
5
12
16
utriedená časť
druhé porovnanie
-5
1
5
12
16
1 < 5, zostávajú utriedená časť
Výsledná usporiadaná postupnosť prvkov
-5
1
5
12
16
Časový odhad algoritmu:
V najhoršom prípade (postupnosť usporiadaná zostupne) pri každom porovnaní prebehne aj výmena.
Pri n – prvkovej postupnosti potrebujeme sčítať (n – 1) prvkov aritmetickej postupnosti:
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 12 z 22
(Téma)
, čo je kvadratická zložitosť.
V najlepšom prípade (už utriedená postupnosť) neprebehne ani jedna výmena, ale počet porovnaní
bude rovnaký.
procedure bubblesort(pocet: integer; var p: pole);
var
i,j,pom: integer;
begin
for i:=1 to pocet-1 do
for j:=1 to pocet-i do begin
if p[j]>p[j+1] then begin
vnútorný cyklus
pom:=p[j];
porovnáva dvojice
p[j]:=p[j+1];
susedných prvkov
p[j+1]:=pom;
end;
end;
end;
vonkajší cyklus spúšťa porovnávanie od prvého prvku
B)
Uvedený algoritmus A) dá vylepšiť, ak si zapamätáme, či v danom prechode prebehla aspoň jedna
výmena. Ak bude počet výmen nulový, znamená to, že postupnosť je utriedená a algoritmus môže
skončiť.
procedure bubblesort2(pocet: integer; var p: pole);
var
i,j,pom: integer;
vymenaok: boolean;
begin
vymena:=false;
while vymena do begin
vymena:=false;
for j:=1 to pocet do begin
if p[j]>p[j+1] then begin
pom:=p[j];
p[j]:=p[j+1];
p[j+1]:=pom;
vymena:=true;
end;
end;
end;
end;
Časový odhad algoritmu:
V najhoršom prípade (postupnosť usporiadaná zostupne) pri každom porovnaní prebehne aj výmena.
Pri n –prvkovej postupnosti potrebujeme sčítať (n – 1) prvkov aritmetickej postupnosti:
, čo je opäť kvadratická zložitosť.
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 13 z 22
(Téma)
V najlepšom prípade (už utriedená postupnosť) neprebehne ani jedna výmena, počet porovnaní bude
(n – 1), čo je len lineárna zložitosť.
Porovnanie:
Bubblesort je najpomalší algoritmus, pretože potrebuje veľký počet výmen. Ostatné algoritmy, ako
Insertsort, Selectsort, sú rýchlejšie, pretože nevyžadujú taký veľký počet výmen. V praxi sa Bubblesort
neodporúča.
SelectSort (Triedenie výberom)
V každom kroku cyklu hľadáme najmenší prvok postupnosti na určitom úseku. Pri prvom prechode je
to celá postupnosť, pri ďalšom je postupnosť o jeden prvok kratšia a podobne. Nájdené minimum
vymeníme s prvým prvkom, od ktorého sme hľadali minimum. Pri hľadaní si uchovávame len index
minimálne prvku.
Počet výmen je o jeden menší ako počet prvkov.
Príklad:
Neusporiadaná postupnosť prvkov
5
1
12
-5
16
Počet prvkov je 5, teda 4-krát budeme hľadať minimálny prvok a spolu prebehnú 4 výmeny.
1.
hľadanie minima
Celá postupnosť je neutriedená, minimum hľadáme spomedzi všetkých prvkov.
5
1
12
-5
16
Prvok s indexom jedna (päťka) vymeníme s minimálnym prvkom s indexom 4 (mínus päť).
2.
hľadanie minima
Prvý prvok postupnosti (- 5) už je na svojom mieste, ďalšie minimum hľadáme od druhého prvku.
-5
1
12
5
16
neutriedená časť postupnosti
Ďalšie minimum je jednotka, zostáva na svojom mieste
3.
hľadanie minima
Minimum hľadáme od tretieho prvku.
-5
1
12
5
16
neutriedená časť postupnosti
Tretie minimum je päťka, vymení sa s dvanástkou.
4.
hľadanie minima
Minimum hľadáme od štvrtého prvku.
-5
1
5
12
16
-5
1
5
12
16
Posledné minimum je dvanástka, zostáva na svojom mieste, postupnosť je utriedená.
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 14 z 22
(Téma)
procedure selectsort(pocet: integer; var p: pole);
var
i,j,pom, mini: integer;
begin
for i:=1 to pocet-1 do begin
mini:=i;
for j:=i+1 to pocet do
if p[j]<p[mini] then mini:=p[j];
hľadanie minima
pom:=p[i];
p[i]:= p[mini];
p[mini]:=pom;
end;
spúšťanie hľadania minima a jeho výmena s prvkom, od ktorého sa
minimum hľadá
end;
Porovnanie:
Selectsort je rýchlejší ako Bubblesort, ale pomalší ako Insertsort. Oplatí sa ho použiť, ak chceme
ušetriť výmeny, pretože si pamätá len index najmenšieho prvku a v každom kroku tak nastane najviac
jedna výmena.
InsertSort (Triedenie priamym vkladaním)
Neutriedenú postupnosť rozdelíme na dve časti (utriedenú a neutriedenú), na začiatku za utriedenú
postupnosť považujeme prvý prvok poľa, prvky z neutriedenej časti postupne zaraďujeme do
utriedenej časti. Na konci sú všetky prvky zaradené a neutriedená časť zanikne. Prvky zaraďujeme
tak, že ich porovnávame s prvkami z neusporiadanej postupnosti, ak sú väčšie, posúvajú sa o jeden
prvok vpravo.
Príklad:
Neusporiadaná postupnosť prvkov
5
1
12
-5
16
Počet prvkov je päť. Štyri prvky zaradíme na príslušné miesto.
1.
zaraďovanie
Prvý prvok je na svojom mieste, chceme zaradiť druhý prvok.
5
1
12
-5
16
-5
16
utriedené neutriedené
2.
1
zaraďovanie
5
utriedené
12
neutriedené
Chceme zaradiť prvok 12, začneme ho porovnávať s prvkami z usporiadanej časti. Zistíme že hneď
prvý prvok (ktorý je v usporiadanej časti najväčší) je menší, teda zostane na svojom mieste
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 15 z 22
(Téma)
3.
1
zoraďovanie
5
12
utriedené
-5
16
neutriedené
4.
hľadanie minima
Zaradíme posledný prvok.
-5
1
5
12
utriedené
16
-5
1
5
12
16
neutriedené
Posledný prvok zostane na svojom mieste a postupnosť je utriedená.
procedure selectsort(pocet: integer; var p: pole);
var
i, j, zarad: integer;
begin
for i:=2 to pocet do
begin
j:=i-1;
zarad:=p[i];
while (j>0) and (zarad<p[j]) do begin
p[j+1]:=p[j];
Vnútorný cyklus zaraďuje prvok p[i] na správne
dec(i);
miesto tak, že všetky väčšie posúva o jedno
end;
miesto vpravo
p[j+1]:= zarad;
end;
Vonkajší cyklus posúva druhý až posledný prvok na zaraďovanie.
end;
Porovnanie:
Insertsort je približne dvakrát rýchlejší, ako Bubblesort a o 40% rýchlejší, ako Selectsort. Je vhodný
pre zoznamy, ktoré majú veľkosť do 1000 prvkov a pre zoznamy, ktoré sú takmer usporiadané.
Úlohy
1.
Vytvorte program, ktorý utriedi prvky jednorozmerného poľa. Použite aspoň 2 rôzne metódy
triedenia. Porovnajte ich. Prvky poľa vygenerujte ako náhodné čísla z intervalu <0,50>.
Objekty do formulára umiestnite podľa potreby.
2.
V textovom súbore bodovanie.txt máme uložené
názvy štátov a bodový zisk za umiestnenia ich
športovcov na olympiáde. Vytvorte program, ktorý
tieto štáty usporiada zostupne podľa získaného
počtu bodov s použitím jedného poľa. Komponenty
do formulára
umiestnite
podľa
potreby.
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 16 z 22
(Téma)
Práca s myšou
Udalosti
Sú to podnety (kliknutie myšou, stlačenie ľavého tlačidla myši, ...), na ktoré môžu komponenty na
formulári aj samotný formulár reagovať (udalosť ang. event). Každá udalosť má:
 meno, z ktorého sa dá vyčítať, o aký podnet ide, napr. onClick, onDblClick, onCreate.
 akciu, t.j. časť programu, ktorá sa vykoná pri vzniku udalosti;
Udalosti sa vykonávajú často procedúrami. Napr. Button1Click, Image1.Click, FormCreate, .... Ich
mená sa vytvárajú automaticky (obsahujú meno objektu a názov komponentu).
Táto procedúra sa automaticky
vygenerovala po dvojkliku na
komponent s názvom Button1.
meno procedúry
parameter procedúry
Udalosti myši
Udalosť OnMouseDown vyjadruje, že sme s myšou klikli niekde do grafickej plochy. Udalosti vieme
pridávať v Inšpektore objektov, na záložke Udalosti:
2 x click
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 17 z 22
(Téma)
Názov procedúry
Návratové parametre [x, y]
sú súradnice bodu, do
ktorého sme s myšou klikli.
Vytvoríme procedúru, ktorá bude reagovať na udalosť „kliknutie myšou na plátno“ s akciou
vykreslenie bodu v mieste kliknutia s polomerom 2 px. (Obr. 1.)
procedure TForm1.Image1MouseDown(Sender: TObject; Button:
TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
Image1.Canvas.Brush.Color:=clyellow;
Image1.Canvas.Pen.Color:=clred;
Image.Canvas.Ellipse(x - 2, y - 2, x + 2, y + 2);
end;
Udalosť OnMouseMove reaguje na pohyb myši po plátne bez ohľadu na to, či je niektoré tlačidlo
myši stlačené. V nasledujúcej procedúre prechádzame myšou nad grafickou plochou, pričom sa
vykresľuje čiara do bodu, nad ktorým sa nachádza kurzor myši. (Obr. 2)
procedure TForm1.Image1MouseMove(Sender: TObject; Button:
TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
Image1.Canvas.Pen.Widht:=2;
Image1.Canvas.Pen.Color:=clred;
Image.Canvas.LineTo(x, y);
end;
Obr. 1
Obr. 2
Procedúry, ktoré spracúvajú udalosti myši, majú ďalší dôležitý návratový parameter Shift. Z neho sa
dozvieme, ktoré tlačidlo myši bolo stlačené. Možné hodnoty:
Shift = []
nebolo stlačené sme žiadne tlačidlo
Shift = [ssLeft]
bolo stlačené len ľavé tlačidlo
Shift = [ssRight]
bolo stlačené len pravé tlačidlo
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 18 z 22
(Téma)
Shift = [ssLeft, ssRight] naraz boli stlačené obe tlačidlá
S týmito znalosti môžeme predchádzajúcu procedúru upraviť tak, aby sa kreslili čiary len pri
stlačenom ľavom tlačidle myši.
procedure TForm1.Image1MouseMove(Sender: TObject; Button:
TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
Image1.Canvas.Pen.Widht:=2;
Image1.Canvas.Pen.Color:=clred;
if Shift = [ssshift] then Image.Canvas.LineTo(x, y);
end;
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 19 z 22
(Téma)
Použité zdroje:
1. http://melisko.webnode.sk/news/dvojrozmerne-polia-matice/
2. http://people.tuke.sk/igor.podlubny/C/Kap11.htm
3. http://pascal.input.sk/index.php/7.Prednaska
„Moderné vzdelávanie pre vedomostnú spoločnosť/Projekt je spolufinancovaný zo zdrojov EÚ“
Strana 20 z 22
Download

PROGRAMOVANIE V LAZARUSE PRE MATURANTOV