---

Polia, vymenovaný typ, množiny

1. ukážeme prácu so zásobníkom

2. definujeme vymenovaný typ

3. naučíme sa používať typ množina

---

Štruktúrovaný (zložený) typ POLE

type pole = array[typ_indexu] of typ_prvkov;

• všetky prvky poľa sú rovnakého typu, t. j. pole sa skladá z mnohých "jednoduchších" premenných
• tieto premenné sú prístupné cez index (selektovanie)
• typ_indexu - ľubovoľný ordinálny typ
• typ_prvkov - ľubovoľný typ
• celá štruktúra musí zaberať menej ako 64 KB - v Turbo pascale

---

Príklad: Zásobník je postupnosť prvkov, v ktorej je možné pridávať a odoberať prvky len na jednom konci. Tento koniec sa nazýva vrchol zásobníka. Teda zásobník môžeme považovať za istú štruktúru údajov.

procedúry pre prácu so zásobníkom:

Const nmax=100;
 
Type
 zasobnik=array[1..nmax,1..3] of integer;
 rozsah: 0..nmax;
 
var z: zasobnik; vrchol: rozsah;
 
procedure vytvor_z(var zz: zasobnik; var vrch:rozsah);
{Vytvori prazdny zasobnik}
begin
 vrch:=0;
end; 
 
procedure vloz_z(var zz: zasobnik; var vrch:rozsah; e,f,g: integer);
{Vlozi prvok do zasobnika}
begin
 if vrch<nmax then 
 begin zz[vrch,1]:=e; zz[vrch,2]:=f; zz[vrch,3]:=g;
inc(vrch) end
 else writeln('Zasobnik je plny');
end; 
 
procedure vyber_z(var zz: zasobnik; var vrch:rozsah; var e, f, g: integer);
{Vyberie prvok zo zasobnika}
begin
 if vrch>0 then 
 begin e:=zz[vrch,1]; f:=zz[vrch,2]; 
 g:=zz[vrch,3]; dec(vrch) end
 else writeln('Zasobnik je prazdny');
end;
 
 
 

Príklad na použitie zásobníka:

 
V nasledujúcom príklade si to ukážeme na Fibonacciho postupnosti. Definovaná je rekurentne takto:


  

  
 
 
 
F(0)=1; F(1)=1; F(N)=F(N-1)+F(N-2) pre N>1
F(2)=2
F(3)=3
F(4)=5
F(5)=8
F(6)=13
F(7)=21
 
F(7)= F(6) + F(5)
F(4) + F(3)
F(2) + F(1)
1
F(1) + F(0) 
1
1 
F(3) + F(2)
 

rekurzívna procedúra, ktorá počíta N-té Fibonacciho číslo:

Var
 ff:integer; { globálna premenná, v ktorej je vypočítaná hodnota}
 
procedure fib(n:integer);
var
 f : integer;
begin
{časť 1:}
 if n<2 then ff:=1
 else begin 
fib(n-1);
{časť 2:}
 f := ff;
 
fib(n-2);
{časť 3:}
 ff:=ff+f;
 end;
end;

nerekurzívny tvar predchádzajúcej procedúry:

 
var
 ff:integer; { globálna premenná, v ktorej je vypočítaná hodnota}
 
 
procedure fibN(n:integer);
var
 f, e, v: integer;
 z: zasobnik;
 vr: rozsah;
begin
v:=1;
f:=0;
vytvor_z(z, vr); 
vloz_z(z,vr,n,f,v);
while vr>0 do begin
vyber_z(z,vr,n,f,v);
case v of
 1:
  if n<2 then ff:=1
 else begin
 vloz_z(z,vr,n,f, 2); 
 vloz_z(z,vr,n-1,f, 1); {rekurzívne volanie}
 end;
 2:
 begin
 f:=ff; 
 vloz_z(z,vr,n, f, 3); 
 Vloz_z(z,vr,n-2, f, 1); {fib(n-2)}
 end;
 3: ff:=ff+f;
 end;
 end;
end;

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 nastroj = (husle,bubon,klavir,truba,saxofon,flauta,triangel);

· 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 nastroj sa zadeklarovalo aj 7 identifikátorov - ako keby const husle=...; bubon=...; truba=...; ...

· vymenovaný typ je ordinálny a teda s ním fungujú všetky štandardné funkcie a procedúry, ktoré pracujú s inými ordinálnymi 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:=succ(sob); 
 d:=uto;
 inc(d); 
 inc(d,3); 
 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:

o štandardné funkcie, procedúry: ord, pred, succ, low, high, inc, dec

o môžeme ho použiť ako index prvkov poľa, resp. riadiaca premenná cyklu

o fungujú všetky relácie: =, <>, <=, >=, <, >

o aj typ boolean je vymenovaný typ, t.j. ako keby type boolean=(false,true);

o vymenovaný typ sa nedá vypísať ani načítať

o 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;

o 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 načí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.

načítanie a výpis vymenovaného typu pomocou poľa mien konštánt:

type
 tyzden=(pon,uto,str,stv,pia,sob,ned);
const
 a:array [tyzden] of string =
 ('pon','uto','str','stv','pia','sob','ned');
var
 s:string[3];
begin
 readln(s);
 d:=low(tyzden);
 while (d<high(tyzden)) and (a[d]<>s) do inc(d);
 if a[d]<>s then 
 writeln('... chyba ...')
 else
 writeln(a[succ(d)]); { spadne, ak d=ned}
end;

Typ množina

· je taký údajový typ, ktorý umožňuje v pascale pracovať s istou triedou množín podobným spôsobom ako v je obvyklé v matematike

· v pascale je povolené vytvárať množiny len 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 načí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]

· operácie (oba operandy musia byť kompatibilné množiny - majú kompatibilné bázové typy):

o zjednotenie a:=a+b;

o prienik a:=a*[2,3];

o rozdiel a:=b-[1,3];

· príslušnosť prvku (prvý operand je bázového typu, druhý je množina):

o číslo 3 je prvkom množiny a: if 3 in a then ...

· relácie:

o rovnosť, nerovnosť: if a=b then if c<>[] then ...

o 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'];
...
 readln(s);
 if (s<>'') and (s[1] in ano) then ...
 else if (s<>'') and (s[1] in nie) then ...
 else writeln('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; 
 s:string;
begin
 s:='[';
 for i:=low(baza) to high(baza) do
 if i in m then s:=s+chr(i....)+',';
 writeln(s+']');
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

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ť "super 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 (pre množinu do 256*20-1 = 5119):

 
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;

Príklad

Erathostenovo sito pre hľadanie prvočísel v malých množinách:

Erathostenes pre malé množiny

var
 m, prvoc:set of 1..255;
 i:integer;
 d: integer;
begin
m:=[];
for i:=1 to 255 do m:= m+[i];
prvoc:=[2];
for i:=1 to 255 do
if i mod 2=0 then m:=m-[i];
d:=3;
while d<=123 do
begin
j:= d;
while j<=255 do
begin
if j in m then m:=m-[j];
j:= j+d;
end;
d:=d+2;
end;
 
end;