Question

Să presupunem că lucrați pentru o companie care dezvoltă software pentru procesarea algebrică.
Sarcina dvs. este de a dezvolta un program pentru a face calcule cu seturi de numere întregi. Seturile tale ar putea avea
până la 10000 de elemente în care un element este un număr întreg în intervalul -108 ... 108
.

A. Este important să se proiecteze o reprezentare pentru seturi care să permită o implementare eficientă a setului
operațiuni. Să presupunem că alegeți să reprezenta un set de numere întregi ca o pereche formată din: (i) un număr întreg
reprezintă numărul de elemente stabilite; (ii) o matrice care stochează elementele setate.
Sarcina ta la acest pas este de a proiecta algoritmi O (m + n) pentru calculul uniunii și intersecției a
două seturi X și Y, cu m,respectiv n elemente.

Answer 1

Pentru uniune:

int frecv[218];

signed char rezultat[10000];

signed char* uniune(unsigned short int n, signed char* set1, unsigned short int m, signed char* set2){

for(unsigned short int i = 0; i < n; i++)// n iteratii

frecv[set1[i] + 108]++;

for(unsigned short int i = 0; i < m; i++)// m iteratii

frecv[set2[i] + 108]++;

int k = 0;

for(short int i = -108; i <= 108; i++){// 217 iteratii - constant

if(frecv[i+108])

rezultat[k++] = i;

}

return rezultat;

//Complexitate: O(n+m)

}

Pentru intersectie:

int frecv[218];

signed char rezultat[10000];

signed char* intersectie(unsigned short int n, signed char* set1, unsigned short int m, signed char* set2){

for(unsigned short int i = 0; i < n; i++)// n iteratii

frecv[set1[i] + 108] = 1;

for(unsigned short int i = 0; i < m; i++)// m iteratii

if(frecv[set2[i] + 108] == 1)

frecv[set2[i] + 108]++;

int k = 0;

for(short int i = -108; i <= 108; i++){// 217 iteratii - constant

if(frecv[i+108] == 2)

rezultat[k++] = i;

}

return rezultat;

//Complexitate: O(n+m)

}