17.10.2002
|
Vymenovaný typ (enumerated
type)
- je ordinálny typ, ktorý definujeme
vymenovaním všetkých prípustných
hodnôt daného typu
- vymenované hodnoty sú identifikátory
konštánt (ich ordinálne hodnoty sú
čísla od 0 do počet-1), napr.
type
tyzden = (pon,uto,str,stv,pia,sob,ned);
- definuje nový ordinálny typ -
premenné tohto typu môžu nadobúdať
hodnotu len z tohto zoznamu konštánt
- vymenovaný typ, na rozdiel od intervalu,
nie je kompatibilný so žiadnym iným
typom (interval preberá všetky vlastnosti
aj konštanty nadradeného typu a tiež je s
ním kompatibilný - dovoľuje navzájom
sa priraďovať, miešať sa v operáciách
a pod.)
- deklarácia vymenovaného typu okrem
samotného typu automaticky definuje aj identifikátory
konštánt tohto typu, t.j. s deklaráciou
typu tyzden sa zadeklarovalo aj 7 identifikátorov
- ako keby const pon=...; uto=...; str=...; ...
- vymenovaný typ je ordinálny a
teda s ním fungujú všetky štandardné
funkcie a procedúry, ktoré pracujú
s inými ordinálnimi typmi (integer,
char, boolean) - napr. pred, succ, inc, dec, low,
high, ord
ukážka:
|
type
tyzden=(pon,uto,str,stv,pia,sob,ned);
var
d:tyzden;
begin
d:=pon;
d:=pred(pia); // d=stv
d:=succ(sob); // d=ned
d:=uto;
inc(d); // d=str
inc(d,3); // d=sob
i:=ord(pon); // i=0 prvá konštanta vymenovaného typu má hodnotu 0
i:=ord(uto); // i=1
d:=tyzden(4); // d=pia - identifikátor typu sa dá použiť ako funkcia
d:=low(tyzden); // d=pon
d:=high(d); // d=ned -- je to škaredé
end;
|
- práca s vymenovaným typom:
- štandardné funkcie, procedúry: ord,
pred, succ, low, high, inc, dec
- môžeme ho použiť ako index prvkov poľa,
resp. riadiaca premenná cyklu
- fungujú všetky relácie: =, <>,
<=, >=, <, >
- aj typ boolean je vymenovaný typ, t.j. ako
keby type boolean=(false,true);
- vymenovaný typ sa nedá vypísať
ani prečítať
- ordinálna hodnota je definovaná
tak, že prvá konštanta typu má
vnútornú hodnotu 0 a všetky ďalšie
postupne o 1 viac, t.j. ord(pon)=0;
ord(uto)=1; ord(str)=2; ... ord(ned)=6;
- meno typu (v našom prípade tyzden)
je automaticky menom konverznej funkcie, ktorá
z celého čísla vyrobí príslušnú
konštantu vymenovaného typu, napr. tyzden(2)=str;
tyzden(5)=sob;
- ak potrebujeme hodnoty vymenovaného typu
prečítať alebo vypísať, tak buď pri
vstupe/výstupe pracujeme iba s ordinálnymi
hodnotami, alebo si vytvoríme pomocné
pole mien konštánt, napr.
prečítanie a výpis
vymenovaného typu pomocou
poľa mien konštánt:
|
const
a:array [tyzden] of string =
('pon','uto','str','stv','pia','sob','ned');
var
s:string;
begin
s:=Edit1.Text;
d:=low(tyzden);
while (d<high(tyzden)) and (a[d]<>s) do inc(d);
if a[d]<>s then
Memo1.Lines.Add('... chyba ...')
else
Memo1.Lines.Add(a[succ(d)]); // spadne, ak d=ned
end;
|
zistite, v čom je chybné takéto
riešenie:
|
const
a:array [tyzden] of string =
('pon','uto','str','stv','pia','sob','ned');
var
s:string;
begin
s:=Edit1.Text;
d:=low(tyzden);
while (d<=high(tyzden)) and (a[d]<>s) do inc(d);
if d>high(tyzden) then
Memo1.Lines.Add('... chyba ...')
else
Memo1.Lines.Add(a[succ(d)]);
end;
|
- vymenovaný typ sme už používali, napr.
nasledujúce typy sú už preddefinované:
|
type
TPenStyle = (psSolid, psDash, psDot, psDashDot, psDashDotDot,
psClear, psInsideFrame);
TBrushStyle = (bsSolid, bsClear, bsHorizontal, bsVertical,
bsFDiagonal, bsBDiagonal, bsCross, bsDiagCross);
// a my sme mohli písať:
g.Pen.Style := psDash;
g.Brush.Style := bsVertical;
|
- V nasledujúcom príklade funkcia porovnaj
vráti jednu z hodnôt vymenovaného
typu (mensi, rovny, vacsi) podľa toho, v akej relácii
sú dva reťazce:
funkcia vráti konštantu
vymenovaného typu:
|
type
por=(mensi, rovny, vacsi);
function porovnaj(s1,s2:string):por;
begin
if s1<s2 then Result:=mensi
else if s1=s2 then Result:=rovny
else Result:=vacsi;
end;
|
iné možnosti definovania vymenovaného
typu v Delphi 6
- zatiaľ sme sa naučili, že prvé konštanta
vymenovaného typu má ordinálnu
hodnotu 0 a posledná počet-1
- toto pravidlo môžeme podľa potreby
zmeniť: pri definovaní vymenovaného
typu môžeme zároveň definovať aj ordinálne
hodnoty konštánt, napr. type
por=(mensi=-1,rovny,vacsi=3);
- pritom platí:
- ak je za konštantou celé číslo,
toto definuje jeho ordinálnu hodnotu
- ak prvá konštanta nemá definovanú
žiadnu hodnotu (napr. pon v tyzden),
tak dostáva hodnotu 0
- ak niektorá konštanta (okrem prvej)
nemá definovanú svoju ordinálnu
hodnotu, automaticky dostáva o 1 vyššiu
ako predchádzajúca konštanta
- viac identifikátorov konštánt
môže mať rovnaké ordinálne
hodnoty
- medzi minimálnou a maximálnou
hodnotou nemusia byť všetky ordinálne
hodnoty pomenované konštantami, napr.
v type por má konštanta rovny
hodnotu 0 a hodnotu 2 sme nepomenovali - aj
tak môže premenná takéhoto
vymenovaného typu nadobúdať aj
nepomenované hodnoty, napr. var p:por
= por(2);
- z tohoto vyplýva, že pre vymenovaný
typ je dôležitá minimálna a
maximálna konštanta - tieto dve definujú
interval a všetky ostatné konštanty
len pomenúvajú niektoré hodnoty
z daného intervalu, napr.
type
cislo=(minc=1,maxc=100,spec=10);
- definuje vymenovaný typ, ktorý
je intervalom s ordinálnymi hodnotami 1..100,
okrem toho je ešte definovaná jedna konštanta
tohoto typu spec s ordinálnou hodnotou
10
- aj pomocou const môžeme dodatočne
zadefinovať ďalšie konštanty do vymenovaného
typu, napr.
const
extra:cislo = 27;
- k trom konštantám typu cislo dodefinoval
ďalšiu s ordinálnou hodnotou 27
Typ množina
- je taký údajový typ, ktorý
umožňuje v pascale pracovať s istou triedou množín
podobným spôsobom ako je to obvyklé
v matematike
- v pascale je povolené vytvárať
množiny zložené len z prvkov rovnakého a to ordinálneho
typu - hovoríme mu bázový
(základný) typ, napr. množina znakov,
množina malých celých čísel,
množina dní v týždni a pod.
- nemôžeme vytvoriť množinu, ktorá
bude obsahovať napr. čísla aj znaky
- definícia množiny sa vždy skladá
aj z definície jej bázového
typu, napr. zápis set
of 1..100 definuje typ množina,
ktorá môže obsahovať len čísla
z intervalu (to je ordinálny typ) 1 až 100
- zrejme premenná takéhoto typu môže
byť napr. prázdnou množinou, alebo jednoprvkovou
množinou s prvkom 13 alebo dvojprvkovou množinou
s prvkami 2 a 3 a pod.
napr.
|
type
m=set of 1..100;
var
a,b:m;
|
- zadefinuje dve premenné typu množina
- do týchto premenných môžeme
priraďovať (iba množiny), môžeme s nimi manipulovať
pomocou množinových operácií
a relácií - nemôžeme ich priamo
vypísať alebo prečítať, musíme
si to naprogramovať
práca s typom množina
- množinové konštanty: [], [2], [1,3], [1,2,3],
[5..15,20,23..27]
- ale aj [1,1,1], [3,3,1], [1..2,2..3,1..3]
- operácie (oba operandy musia byť kompatibilné
množiny - majú kompatibilné
bázové typy):
- zjednotenie a:=a+b;
- prienik a:=a*[2,3];
- rozdiel a:=b-[1,3];
- príslušnosť prvku (prvý operand
je bázového typu, druhý je
množina):
- číslo 3 je prvkom množiny a: if 3 in a then ...
- relácie:
- rovnosť, nerovnosť: if a=b then if c<>[]
then ...
- podmnožiny: if (a<=b) or (a>=b)
then ...
príklady:
|
var
z:char;
...
if z in ['A'..'Z','a'..'z'] then ...
if not (z in ['0'..'9']) then ...
|
testovanie odpovede áno/nie:
|
const
ano=['a','A','y','Y']; nie=['n','N'];
...
s:=Edit1.Text;
if (s<>'') and (s[1] in ano) then ...
else if (s<>'') and (s[1] in nie) then ...
else MessageBox('chybná odpoveď - ano/nie')
|
generovanie množiny for-cyklom:
|
var
x:set of 1..100;
...
x:=[];
for i:=1 to 100 do x:=x+[i];
...
x:=[];
for i:=1 to 50 do x:=x+[i,101-i];
|
na množinách nefunguje write - vypisujeme
ich pomocou cyklu:
|
type
baza=1..100;
mnozina=set of baza;
procedure vypis(const m:mnozina);
var
i:baza; // 1..100
s:string;
begin
s:='[';
for i:=low(baza) to high(baza) do
if i in m then s:=s+IntToStr(i)+',';
Memo1.Lines.Add(s+']');
end;
|
výpis prvkov množiny do súboru tak,
aby sa za poslednym číslom nevypisovala čiarka:
|
procedure vypis(const t:TextFile; const m:mnozina);
var
i:baza;
begin
write(t,'['); b:=false;
for i:=low(baza) to high(baza) do
if i in m then begin
if b then write(t,',');
write(t,i); b:=true;
end;
write(t,']');
end;
|
NDÚ:
- vypisovanie množiny aj s intervalmi, napr. [1,3..5,10..41,43,45]
- čítanie množiny zo vstupu (na vstupe môžu
byť aj intervaly)
Príklad
program, ktorý z textového
súboru stud.txt prečíta mená študentov
(študentov je menej ako 101), ich priemerné známky
a informáciu o tom, či študent dostal alebo nedostal
internát (v tvare 0 alebo 1). Program potom vypíše
- a) všetkých študentov
- b) dobrých študentov (priemer do 1.5), ktorí
majú internát
- c) dobrých študentov, ktorí nemajú
internát
program:
|
type
baza=1..100;
tab=array[baza] of record
meno:string;
zn:real;
inter:boolean
end;
mn=set of baza;
procedure citajTab(var t:tab; var n:integer);
var
f:TextFile;
bb:integer;
z:char;
begin
AssignFile(f,'stud.txt'); Reset(f);
n:=0;
while not seekeof(f) do begin
inc(n);
with t[n] do begin
meno:='';
repeat read(f,z); if z<>';' then meno:=meno+z until z=';';
readln(f,zn,bb);
inter:=bb=1;
end;
end;
CloseFile(f);
end;
procedure vypis(const t:tab; m:mn);
var
i:baza;
begin
for i:=low(baza) to high(baza) do
if i in m then Memo1.Lines.Add(t[i].meno);
end;
var
t:tab;
a,b:mn; // a - indexy do tabuľky t, pre ktorých zn<=1.5
// b - indexy do tabuľky t, ktorí majú internát
n,i:integer;
begin
citajTab(t,n); // čítanie tabuľky
a:=[]; b:=[];
for i:=1 to n do begin
if t[i].zn<=1.5 then a:=a+[i];
if t[i].inter then b:=b+[i]
end;
Memo1.Lines.Add('*** Vsetci');
vypis(t,[1..n]);
Memo1.Lines.Add('*** dobri, maju intrak');
vypis(t,a*b);
Memo1.Lines.Add('*** dobri, nemaju intrak');
vypis(t,a-b);
end;
|
- aj štýl fontu je definovaný ako
množina:
deklarácie v systéme delphi vyzerajú
približne takto:
|
type
TFontStyle = (fsBold, fsItalic, fsUnderline, fsStrikeOut);
TFontStyles = set of TFontStyle;
...
// pre font je definované
Font:TFontStyles;
|
a preto môžeme zapísať
|
g.Font.Style:=[];
g.Font.Style:=[fsBold];
g.Font.Style:=g.Font.Style-[fsItalic];
Memo1.Font.Style:=[fsItalic,fsUnderline];
|
- neskôr uvidíme použitie množín
aj pri kreslení myšou do grafickej plochy (klikanie,
ťahanie myšou)
Príklad
Napíšeme program, ktorý vytvorí
podmnožinu M množiny 1..250 takú, že
- 1 je z množiny
- ak i je z množiny, tak 2i+1 aj 3i+1 sú z množiny
riešenie
|
var
m:set of 1..250;
i:integer;
begin
m:=[1];
for i:=1 to 124 do
if i in m then begin
m:=m+[2*i+1]; // 2*i+1 je vždy z 1..250
if 3*i+1<=250 then m:=m+[3*i+1]
// ak je aj 3*i+1 z 1..250, pridáme ho do množiny
end;
end;
|
Obmedzenia pre množiny
- pre set of baza musí platiť: 0<=low(baza)<=high(baza)<=255
- väčšie množiny môžeme nasimulovať pomocou
poľa množín - budeme tomu hovoriť "veľké
množiny"
napr.
|
var
m:array[0..max] of set of 0..255;
...
// pridávame x do takejto množiny:
m[x div 256]:=m[x div 256]+[x mod 256]
// zistíme, či je x v množine:
if [x mod 256] in m[x div 256] then ...
|
- riešenie predchádzajúceho príkladu
pomocou 20 množín - každá s 256 prvkami
(maximum bude 256*20-1 = 5119)
použitie veľkej množiny:
|
type
mnozina=set of byte; // t.j. 0..255
mn=array[0..19] of mnozina;
var
m:mn;
i,j:integer;
begin
m[0]:=[1];
for i:=1 to 19 do m[i]:=[];
for i:=1 to 2559 do
if (i mod 256) in m[i div 256] then begin
j:=2*i+1;
m[j div 256]:=m[j div 256]+[j mod 256];
j:=3*i+1;
if j div 256<=19 then
m[j div 256]:=m[j div 256]+[j mod 256];
end;
vypis; // procedúra, ktorá vypíše čísla z množiny
end;
|
Eratostenove sito
najprv s obyčajnou množinou:
|
var
m:set of byte;
i,j:integer;
s:string;
begin
m:=[2..255];
for i:=2 to 127 do
if i in m then begin
j:=2*i;
while j<=255 do begin
m:=m-[j]; inc(j,i);
end;
end;
s:='';
for i:=0 to 255 do
if i in m then
s:=s+IntToStr(i)+' ';
Memo1.Lines.Add(s);
end;
|
Vytvoríme si pomocné procedúry
a funkcie na prácu s veľkými
množinami a použijeme ich pri riešení úlohy
Eratostenove sito:
pomocné podprogramy pre prácu s veľkými množinami:
|
const
maxmn=100;
type
mnozina=record
m:array[0..maxmn] of set of byte;
max:integer; // maximálne číslo v množine
end;
procedure inicMn(var mn:mnozina; mx:integer);
var
i:integer;
begin
if mx>(maxmn+1)*256-1 then mx:=(maxmn+1)*256-1;
mn.max:=mx;
for i:=0 to mx div 256 do mn.m[i]:=[]
end;
procedure pridajMn(var mn:mnozina; i:integer);
begin
with mn do
if (i>=0) and (i<=max) then
m[i div 256]:=m[i div 256]+[i mod 256];
end;
function vMn(const mn:mnozina; i:integer):boolean;
begin
if (i<0) or (i>mn.max) then Result:=false
else Result:=(i mod 256) in mn.m[i div 256]
end;
function pocetMn(const mn:mnozina):integer; // počet prvkov
var
i:integer;
begin
Result:=0;
for i:=0 to mn.max do
if vMn(mn,i) then inc(Result);
end;
function vypisMn(const mn:mnozina):string;
var
i:integer;
b:boolean;
begin
Result:='['; b:=false;
for i:=0 to mn.max do
if vMn(mn,i) then begin
if b then Result:=Result+',';
Result:=Result+IntToStr(i); b:=true
end;
Result:=Result+']';
end;
procedure vsetkyMn(var mn:mnozina);
var
i:integer;
begin
with mn do begin
for i:=0 to max div 256-1 do m[i]:=[0..255];
// všetky okrem poslednej
m[max div 256]:=[0..max mod 256];
end;
end;
procedure uberMn(var mn:mnozina; i:integer);
begin
with mn do
if (i>=0) and (i<=max) then
m[i div 256]:=m[i div 256]-[i mod 256];
end;
|
riešenie úlohy eratostenove
sito:
|
procedure TForm1.Button1Click(Sender: TObject);
var
mn:mnozina;
i,j:integer;
begin
inicMn(mn,25000); vsetkyMn(mn); uberMn(mn,0); uberMn(mn,1);
for i:=2 to mn.max div 2 do
if vMn(mn,i) then begin
j:=i+i;
while j<=mn.max do begin
uberMn(mn,j); inc(j,i);
end;
end;
Memo1.Lines.Add(vypisMn(mn));
Memo1.Lines.Add('počet prvkov = '+IntToStr(pocetMn(mn)));
end;
|
Realizácia množiny v pamäti počítača
- pascalovská množina = postupnosť bitov
- napr. pre set of 0..99 je vyhradených 100
bitov, t.j. 13 bajtov
- v každom bite je buď 0 - prvok nepatrí do
množiny alebo 1 - prvok patrí do množiny
- a:=[]; - vynuluje všetky bity
- a:=[5,7,8]; - nastaví iba bity 5,7,8, ostatné
vynuluje
- a+b - ide po bitoch a robí operáciu
binárne OR
- množina 0..255 zaberá 32 bajtov
|