Ce vei învăța astăzi?
După această lecție vei învăța ce este reuniunea a două mulțimi și cum o calculăm în C++, folosind doi vectori de prezență.
Ce este reuniunea?
Definiție: Reuniunea mulțimilor A și B, notată A ∪ B, este mulțimea elementelor care aparțin lui A sau lui B (sau ambelor).
Cu alte cuvinte, reuniunea adună toate elementele distincte din cele două mulțimi.
Exemplu
Dacă A = {1, 2, 3} și B = {3, 4, 5}, atunci A ∪ B = {1, 2, 3, 4, 5}. Elementul 3 aparține ambelor mulțimi, dar apare o singură dată în reuniune.
Analogie
Reuniunea este ca o listă de invitați formată din lista A și lista B a unei petreceri: dacă o persoană este în ambele liste, o trecem o singură dată.
Reuniunea cu vectori de prezență
Reprezentăm fiecare mulțime printr-un vector de prezență: frecA[x] = 1 dacă x ∈ A, frecB[x] = 1 dacă x ∈ B.
Un element x aparține reuniunii dacă frecA[x] == 1 sau frecB[x] == 1.
Simboluri folosite
Reține: în C++, reuniunea se testează cu operatorul logic || (sau).
Reuniunea a două mulțimi în C++
Citim cele două mulțimi, marcăm prezența fiecărui element, apoi parcurgem vectorii și afișăm valorile care apar în cel puțin unul dintre ei.
#include <iostream>
using namespace std;
int main() {
int n, m, x, i, frecA[101] = {0}, frecB[101] = {0};
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
frecA[x] = 1;
}
cin >> m;
for (i = 1; i <= m; i++) {
cin >> x;
frecB[x] = 1;
}
for (i = 1; i <= 100; i++)
if (frecA[i] == 1 || frecB[i] == 1)
cout << i << " ";
return 0;
}
Observă: condiția frecA[i] == 1 || frecB[i] == 1 selectează exact elementele din reuniune, iar parcurgerea crescătoare le afișează sortate.
Exercițiu de completare
Completează enunțul despre reuniune:
Reuniunea mulțimilor A și B, notată A ______ B, este mulțimea elementelor care aparțin lui A ______ lui B. Elementele comune apar în reuniune o ______ dată.
Bancă de cuvinte:
Exercițiu de completare
Completează fraza despre codul C++:
Pentru a afișa reuniunea, verificăm condiția frecA[i] == 1 ______ frecB[i] == 1. Operatorul ______ înseamnă „sau" în limbajul C++.
Bancă de cuvinte:
Test de înțelegere
Test rapid - reuniunea:
1. Dacă A = {1, 2, 3} și B = {3, 4}, atunci A ∪ B este:
2. Care operator C++ testează reuniunea?
3. Elementul 5 aparține reuniunii A ∪ B dacă:
|| (sau), nu concatenarea celor două șiruri de valori.Aprofundare
Proprietățile reuniunii: reuniunea este comutativă (A ∪ B = B ∪ A), asociativă (A ∪ (B ∪ C) = (A ∪ B) ∪ C) și idempotentă (A ∪ A = A).
- Cardinalul (numărul de elemente) reuniunii: |A ∪ B| = |A| + |B| - |A ∩ B|. De exemplu, pentru A = {1, 2, 3} și B = {3, 4, 5}: 3 + 3 - 1 = 5, ceea ce corespunde lui A ∪ B = {1, 2, 3, 4, 5}.
- Mulțimi disjuncte: dacă A ∩ B = ∅, atunci |A ∪ B| = |A| + |B|; elementele comune nu se numără de două ori.
- Reuniunea și incluziunea: A ⊆ A ∪ B și B ⊆ A ∪ B; reuniunea este cea mai mică mulțime care conține atât A, cât și B.
- În C++: reuniunea nu se calculează prin concatenarea celor două șiruri, ci prin combinarea vectorilor de prezență cu operatorul
||. - Pentru BAC: întrebări frecvente: cardinalul reuniunii, elementele comune numărate o singură dată, afișarea reuniunii sortate.
PbInfo - Reuniunea a două mulțimi
Enunț:
Cerință: Se citesc două mulțimi de numere naturale. Să se afișeze reuniunea lor, sortată crescător.
Date de intrare:
Programul citește n, apoi n elemente ale primei mulțimi, apoi m, apoi m elemente ale celei de-a doua mulțimi.
Date de ieșire:
Programul va afișa elementele reuniunii, în ordine crescătoare, separate prin spații.
Restricții și precizări:
1 ≤ n, m ≤ 100; elementele sunt numere naturale între 1 și 100.
Exemplu:
Intrare:
3 1 2 3 3 3 4 5
Ieșire:
1 2 3 4 5
Cum gândim soluția:
- Marcăm prezența elementelor din A și din B
- Parcurgem vectorii de la 1 la 100
- Afișăm valorile cu frecA == 1 sau frecB == 1
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, m, x, i, frecA[101] = {0}, frecB[101] = {0};
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
frecA[x] = 1;
}
cin >> m;
for (i = 1; i <= m; i++) {
cin >> x;
frecB[x] = 1;
}
for (i = 1; i <= 100; i++)
if (frecA[i] == 1 || frecB[i] == 1)
cout << i << " ";
return 0;
}
Ce învățăm: reuniunea pune împreună elementele ambelor mulțimi, eliminând dublurile prin vectorii de prezență.
PbInfo - Cardinalul reuniunii
Enunț:
Cerință: Se citesc două mulțimi de numere naturale. Să se afișeze câte elemente are reuniunea lor (cardinalul reuniunii).
Date de intrare:
Programul citește n, apoi n elemente ale primei mulțimi, apoi m, apoi m elemente ale celei de-a doua mulțimi.
Date de ieșire:
Programul va afișa pe ecran numărul de elemente ale reuniunii.
Restricții și precizări:
1 ≤ n, m ≤ 100; elementele sunt numere naturale între 1 și 100.
Exemplu:
Intrare:
3 1 2 3 3 3 4 5
Ieșire:
5
Cum gândim soluția:
- Marcăm prezența elementelor din ambele mulțimi într-un singur vector
- Numărăm valorile cu frec == 1
- Afișăm numărul obținut
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, m, x, i, frec[101] = {0}, nr = 0;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
frec[x] = 1;
}
cin >> m;
for (i = 1; i <= m; i++) {
cin >> x;
frec[x] = 1;
}
for (i = 1; i <= 100; i++)
if (frec[i] == 1)
nr++;
cout << nr;
return 0;
}
Ce învățăm: folosind un singur vector de prezență pentru ambele mulțimi, numărul de valori marcate este chiar cardinalul reuniunii.
Exercițiul Practic: Calculăm reuniunea
Sarcini de lucru
Completează următoarele sarcini pentru a aplica reuniunea mulțimilor
Sarcina 1: Calculează reuniunea
Cerință: Pentru A = {2, 4, 6, 8} și B = {4, 5, 8, 9}, scrie A ∪ B și explică de ce elementele 4 și 8 apar o singură dată.
Soluție pentru Sarcina 1:
A ∪ B = {2, 4, 5, 6, 8, 9}
Explicație: 4 și 8 aparțin ambelor mulțimi, dar într-o mulțime
fiecare element apare o singură dată, deci în reuniune
apar o singură dată.
Sarcina 2: Scrie programul
Cerință: Scrie un program C++ care citește două mulțimi (n, elemente, m, elemente) și afișează reuniunea lor, sortată crescător.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n, m, x, i, frecA[101] = {0}, frecB[101] = {0};
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
frecA[x] = 1;
}
cin >> m;
for (i = 1; i <= m; i++) {
cin >> x;
frecB[x] = 1;
}
for (i = 1; i <= 100; i++)
if (frecA[i] == 1 || frecB[i] == 1)
cout << i << " ";
return 0;
}