9. Vymenovaný typ, typ množina


Posledná zmena: 17.10.2002

Banner Text 17.10.2002

    čo sme sa doteraz naučili

    • základné ordinálne typy integer, char a boolean a od nich vieme odvodiť nový typ interval

    čo sa budeme dnes učiť

    • naučíme sa nový ordinálny typ - vymenovaný typ
    • naučíme sa pracovať s pascalovskými množinami
    • ukážeme, ako si môžeme nasimulovať aj veľké množiny

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


© 2002 AB, KVI
blaho@fmph.uniba.sk