👤
HAPPYMARRA4556ID
a fost răspuns

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.

Răspuns :

CINEVAFARANUMEID

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)

}

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari