Introducere
Tipul mulţime este un tip structurat, total diferit de celelalte tipuri structurate; el corespunde noţiunii de mulţime din matematică. Mulţimea este o totalitate de obiecte distincte. Obiectele mulţimii se numesc elemente. O mulţime se caracterizează prin următoarele proprietăţi:
- toate elementele mulţimii aparţin unui domeniu. De exemplu, mulţimea tuturor numerelor naturale reprezintă domeniu pentru orice mulţime de numere întregi;
- orice element al mulţimii are numai două alternative: aparţine sau nu mulţimii date. Un element al mulţimii se include în mulţime o singură dată. Din aceste considerente mulţimile {1,2,7} şi {1,1,2,7,7} sunt echivalente;
- nu este importantă ordinea enumerării elementelor mulţimii. De exemplu, mulţimile {1,2,7}, {7,1,2} şi {7,2,2,1,7,2} sunt echivalente.
Mulţimile pot fi finite şi infinite.
Mulţimile infinite cuprind o infinitate de elemente. De exemplu, mulţimea numerelor pare formează o mulţime infinită, deoarece nu există cel mai mare număr par.
Mulţimile finite cuprind un număr finit de elemente. De exemplu, mulţimea numerelor naturale pare din intervalul 0..10 este o mulţime finită.
În programare se folosesc numai mulţimile finite, deoarece memoria operativă, unde se reprezintă ele, este limitată.
Reprezentarea datelor ca mulţime
Deseori, informaţia despre lumea înconjurătoare se reprezintă sub formă de mulţimi. De exemplu, medicii lucrează cu mulţimi de bolnavi, elevii unei clase reprezintă o mulţime. În program mulţimile de obiecte pot fi reprezentate sub diferite forme de structuri de date: tablouri, structuri de date dinamice, fişiere, mulţimi. Datele pot fi reprezentate ca date de tip mulţime numai dacă se respectă cele trei proprietăţi ale mulţimii.
Tipul mulţime
Un tip mulţime se defineşte în raport cu un tip de bază care trebuie să fie un tip ordinal (deci poate fi char, boolean, enumerare, interval de cardinal, interval de integer, interval de char şi nu poate fi real sau string sau vre-un tip structurat (array sau record). Fiind dat un asemenea tip de bază, tipul mulţime reprezintă mulţimea tuturor submulţimilor tipului de bază, inclusiv şi mulţimea vidă. Dacă tipul de bază are n valori, atunci tipul mulţime reprezintă 2n valori.
În limbajele de programare tipul de bază este limitat. De exemplu, în limbajul Pascal tipul de bază al mulţimii nu are voie să aibă mai mult de 256 valori.El se reprezintă în memoria operativă pe un octet.
Reprezentarea în memorie a variabilelor de tip mulţime
Variabilele de tip mulţime sunt reprezentate în memorie pe n biţi, ocupând
(n div 8 + 1) octeţi. Fiecărei valori admise de tipul de bază îi corespunde bitul al cărui număr de ordine coincide cu cel al valorii. Dacă elementul aparţine mulţimii, atunci bitul care î-l reprezintă va fi poziţionat în 1, în caz contrar – pe 0.
De exemplu, fie mulţimea M={10,13,18,22,23,24}, care reprezintă numere naturale din intervalul 10 .. 30. Pentru reprezentarea acestei mulţimi în memoria operativă sunt necesari 22 biţi. Reprezentarea internă a mulţimii va fi următoare:
1000100001000111000000.
Datorită acestui mod de reprezentare, operaţiile cu datele de tip mulţime se execută extrem de rapid. Este avantajoasă şi alocarea lor în memoria operativă.
Definirea tipului mulţime
Un tip mulţime se defineşte astfel:
Type
De exemplu,
Type
Oras = (Balti,Floresti,Soroca)
M_oras = set of oras
Var
X: m_oras;
Variabila X este o variabilă de tip mulţime a tipului de bază Oras, care este un tip enumerare cu trei valori. Deci, variabila X poate primi 23 = 8 valori. Valorile posibile sunt:
X = []
X = [Balti]
X = [Floresti]
X = [Soroca]
X = [Balti,Floresti]
X = [Balti, Soroca]
X = [Floresti,Soroca]
X = [Balti,Floresti,Soroca]
Putem defini mulţimi pentru cifrele di baza zece:
Type
Cifre1 = set of 0 ..9
Sau
Cifre2 = set of ‘0’ ..’9’
Putem defini mulţimea cifrelor binare:
Type
Cifre_bin = set of 0..1
Vom defini
Type
Semne = set of char
Fie:
Var
Par: cifre1
Impar: cifre1
Cifre: cifre1
Cifra : cifre2
Litere: semne
Operaţiile posibile cu datele de tip mulţime
1. Atribuirea
Variabilele de tip mulţime pot fi iniţializate doar prin atribuire. Operaţia de citire a acestor variabile este interzisă. O mulţime poate fi specificată enumerându-i-se elementele.
Par := []
Par := [0,2,4,6,8]
Impar :=[1,3,5,7,9]
Cifra := [‘0’,’1’ ..’5’,’9’]
Liter :=[‘a’..’z’]
2. reuniunea a două mulţimi
Este mulţimea formată din elementele comune şi necomune ale celor două mulţimi.
Cifre:= par+impar
Mulţimea Cifre va conţine elementele [0,1,2,3,4,5,6,7,8,9]
3. intersecţia a două mulţimi
Este mulţimea formată din elementele comune a două mulţimi.
Cifre:= [2,5,8,9] * [4,2,9]. Rezultatul va fi mulţimea [2,9]
Cifre:= [2,5,7] * [4,6,9]. Rezultatul va fi mulţimea [], deoarece în mulţimile opreand nu sunt elemente comune.
4. diferenţa a două mulţimi
Este mulţimea formată dim elementele primei mulţimi, care nu aparţin celei de-a doua mulţimi
Cifre_impare:=[‘1’ ..’9’] – cifre_pare
5. datele de tip mulţime pot să apară în expresii relaţionale
Două mulţimi sunt egale numai atunci când sunt formate din aceleaşi elemente (de obicei se foloseşte smnul =). Dacă cele două mulţimi diferă măcar cu un element, ele sunt diferite (#). Se permite verificarea dacă o mulţime este inclusă în altă mulţime(<=) sau dacă o mulţime include pe altă mulţime (>=)
6. selectarea unei componente prin testul de apartenenţă.
Elementele unei date de tip mulţime nu pot fi accesatwe direct, dar se permite verificarea apartenenţei unui element la data respectivă folosind operatorul relaţionmal in
E in A,
Unde A este o mulţime, iar e este o expresie de acelaşi tip ordinal cu tipul de bază al mulţimii A. Această expresie are valoarea TRUE dacă valoarea expresiei reprezintă un element din A şi valoarea FALSE în caz contrar. Folosirea testului de apartenenţă permite transcrierea eficientă a unor teste complicate. De exemplu, construcţia
If (c=’A’) or (c=’B’) or (c=’C’) or (c=’D’) or (c=’E’) or (c=’F’) then …
Se poate scrie mai simplu
If c in [‘A’ …’F’] then …
Întroducera mulţimilor
Datele de tip mulţime nu pot fi nici citite, nici scrise.
Pentru a întroduce o mulţime concretă se citesc elementele care formeză mulţmea şi reunind aceste elemente, se construeşte mulţimea dorită.
Fie,
Var
A: set of [1..100]
X: [1..100]
Begin
A:=[]
Readcard(x)
A:=a+[x]
End.
Sau
Var
b: set of [‘a’ ..’f’]
y: char
Begin
b:=[]
Readchar(y)
b:=b+[y]
End.
Afişarea mulţimilor
Pentru a afişa o mulţime e necesar să se determine elementele care aparţin mulţimii. Pentru a determina care elemente aparţin mulţimii se organizează un ciclu care verifică dacă fiecare element posibil aparţine cu siguranţă mulţimii.
For i:=’a’ to ‘f’ step 1
If y in B then
Write(i)
Endif
Endfor
Exemple
1. Se citesc n cuvinte. Se cere să se afişeze literele distincte din fiecare cuvînt citit şi literele distincte întîlnite în toate cele n cuvinte.
Rezolvare:
Se vor declara două variabile de tip mulţime cu tipul de bază litere: cuvint şi total. Iniţial aceste mulţimi vor fi vide.
Type
Litere=set of ‘a’.. ‘z’
Var
Cuvint: litere
Total: litere
N: cardinal
I: integer
X: ‘a’ .. ‘z’
Begin
Total:=[]
For i:=1 to n step 1
Cuvint:=[]
While not eoln do
Readchar(x)
Cuvint:=cuvint + [litera]
Enddo
Writecard(n)
Total:=total+cuvint
For x:=’a’ to z’ step 1
If litera in cuvint then
Writechar(x)
Endif
Endfor
Endfor
For x:=’a’ to z’ step 1
If litera in total then
Writechar(x)
Endif
Endfor
2. Se dau numerele a şi b. Să se determine divizorii comuni ai celor două numere date folosind tipul mulţime.
Rezolvare:
Dacă numerele sunt de tip interval cu cel mult 256 elemente problema se rezolvă în felul următor:
Type
Interval = 1..255
M=set of interval
var
Da: m
Db: m
Dc: m
A: interval
B: interval
I: cardinal
Begin
Writestring(‘A-?’)
Readcard(a)
Writeln
;
Writestring(‘B-?’)
Readcard(b)
Writeln
;
Da:=[]
For i:=1 to a step 1
If a mod i = 0 then
Da:=da+[i]
Endif
Endfor
;
Db:=[]
For i:=1 to b step 1
If b mod i = 0 then
Db:=db+[i]
Endif
Endfor
;
dc:=da * db
;
For i:=1 to a step 1
If i in dc then
Writecard(i)
Endif
Endfor
var x1,x2,x3:array[0..255] of set of byte; i,j:word; a,b:word; n1,n2:byte; begin for i:=0 to 255 do x1[i]:=[]; endfor
readln(a); i:=1; while i<=a do if a mod i =0 then
n1:=i div 255;
n2:=i mod 255;
x1[n1]:=x1[n1]+[n2];
endif
i:=i+1
enddo
for i:=0 to 255 do
x2[i]:=[];
endfor
read(b);
i:=1;
while i<=b do
if b mod i =0 then
n1:=i div 255;
n2:=i mod 255;
x2[n1]:=x2[n1]+[n2];
endif
i:=i+1;
enddo
for i:=0 to 255 do
x3[i]:=x1[i]*x2[i];
writeln('tyy');
for i:=0 to 255 do
for j:=1 to 255 do
if j in x3[i] then
writeln(j+(i)*255);
end.
Niciun comentariu:
Trimiteți un comentariu