Množina

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'];
...
  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;   // 1..100
begin
  write('[');
  for i:=low(baza) to high(baza) do
    if i in m then write(i,',');
end;

výpis prvkov množiny do súboru tak, aby sa za poslednym číslom nevypisovala čiarka:

procedure vypis(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(',');
      write(i); b:=true;
    end;
  write(']');
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:Text;
  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;

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

Úloha

Na vstupe je v prvom riadku párne číslo N a potom v ďalších riadkoch sú dvojice čísel A,B (200>A>B>0) označujúce intervaly <A;B>. Zisti a vypíš čísla:

ležiace vo všetkých intervaloch
neležiace v žiadnom intervale a je z intervalu 1-200
čísla ležiace v niektorom intervale, ale nie vo všetkých.
čísla ležiace len v prvom zadanom intervale a v ostatných už nie.
čísla ležiace v prvej polovici zo zadaných intervaloch a vo zvyšných intervaloch sa nenachádzajú.