Ce vei învăța astăzi?
După această lecție vei învăța cum verificăm în C++ apartenența unui element la o mulțime, incluziunea A ⊆ B și egalitatea A = B.
Apartenența x ∈ A
Definiție: Elementul x aparține mulțimii A, notat x ∈ A, dacă x este un element al mulțimii A.
În reprezentarea cu vector de prezență, x ∈ A este adevărat dacă frecA[x] == 1.
Exemplu
Pentru A = {2, 4, 6}: 4 ∈ A este adevărat (frecA[4] == 1), iar 5 ∈ A este fals (frecA[5] == 0).
Incluziunea A ⊆ B și egalitatea A = B
Incluziunea: A ⊆ B (A este inclusă în B) dacă fiecare element al lui A se află și în B.
Egalitatea: A = B dacă A ⊆ B și B ⊆ A, adică cele două mulțimi au exact aceleași elemente.
x ∈ A: elementul x este în mulțimea A
A ⊆ B: toate elementele lui A sunt în B
A = B: aceleași elemente în ambele mulțimi
Reține: pentru incluziune, verificăm ca niciun element al lui A să nu lipsească din B, adică frecA[i] == 1 && frecB[i] == 0 să nu apară.
Apartenența, incluziunea și egalitatea în C++
#include <iostream>
using namespace std;
int main() {
int n, m, x, i, frecA[101] = {0}, frecB[101] = {0};
bool ok;
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;
}
cin >> x;
if (frecA[x] == 1)
cout << x << " apartine lui A" << endl;
else
cout << x << " nu apartine lui A" << endl;
ok = true;
for (i = 1; i <= 100; i++)
if (frecA[i] == 1 && frecB[i] == 0)
ok = false;
if (ok)
cout << "A este inclusa in B" << endl;
else
cout << "A nu este inclusa in B" << endl;
ok = true;
for (i = 1; i <= 100; i++)
if (frecA[i] != frecB[i])
ok = false;
if (ok)
cout << "A este egala cu B" << endl;
else
cout << "A nu este egala cu B" << endl;
return 0;
}
Observă: folosim o variabilă ok inițializată cu true; dacă găsim o excepție, o setăm pe false. La egalitate comparăm cei doi vectori element cu element.
Exercițiu de completare
Completează enunțul despre apartenență:
Elementul x ______ mulțimii A, notat x ∈ A, dacă x este un element al lui A. În C++, verificăm condiția frecA[x] == ______.
Bancă de cuvinte:
Exercițiu de completare
Completează enunțul despre incluziune:
Spunem că A este ______ în B, notat A ⊆ B, dacă toate elementele lui A se află și în ______. Dacă A ⊆ B și B ⊆ A, atunci A este ______ cu B.
Bancă de cuvinte:
Test de înțelegere
Test rapid - apartenență, incluziune, egalitate:
1. Pentru A = {2, 4, 6}, afirmația 4 ∈ A este:
2. Dacă A = {1, 2} și B = {1, 2, 3}, atunci A ⊆ B este:
3. Mulțimile A = {2, 3} și B = {3, 2} sunt:
frecA[i] != frecB[i]), nu doar cardinalii — două mulțimi cu același număr de elemente pot fi diferite.Aprofundare
Proprietăți ale incluziunii și egalității: mulțimea vidă (mulțimea fără niciun element) este inclusă în orice mulțime (∅ ⊆ A), iar orice mulțime este inclusă în ea însăși (A ⊆ A).
- Egalitatea prin dublă incluziune: A = B dacă și numai dacă A ⊆ B și B ⊆ A; aceasta este definiția formală a egalității între mulțimi.
- Incluziune strictă: A ⊂ B (inclusă strict) dacă A ⊆ B și A ≠ B, adică B mai conține cel puțin un element care nu este în A.
- Relația cu operațiile: A ⊆ B este echivalent cu A ∪ B = B și cu A ∩ B = A; aceste echivalențe pot fi folosite pentru verificări încrucișate.
- Verificarea egalității pe vectori: comparăm element cu element (
frecA[i] != frecB[i]); compararea cardinalilor nu este suficientă. - Pentru BAC: variabila
ok(steag boolean) este un model clasic de verificare; dacă găsești o excepție, o setezi pefalseși poți opri bucla.
PbInfo - Apartenența la o mulțime
Enunț:
Cerință: Se citește o mulțime de numere naturale, apoi k numere. Pentru fiecare număr x, să se afișeze DA dacă x aparține mulțimii, altfel NU.
Date de intrare:
Programul citește n, apoi n elemente ale mulțimii, apoi k și cele k numere de verificat.
Date de ieșire:
Programul va afișa, pentru fiecare număr verificat, DA sau NU, câte unul pe linie.
Restricții și precizări:
1 ≤ n, k ≤ 100; valorile sunt numere naturale între 1 și 100.
Exemplu:
Intrare:
3 2 4 6 4 4 5 6 7
Ieșire:
DA NU DA NU
Cum gândim soluția:
- Marcăm prezența elementelor mulțimii
- Pentru fiecare x verificat, testăm frec[x] == 1
- Afișăm DA sau NU corespunzător
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, k, x, i, frec[101] = {0};
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
frec[x] = 1;
}
cin >> k;
for (i = 1; i <= k; i++) {
cin >> x;
if (frec[x] == 1)
cout << "DA" << endl;
else
cout << "NU" << endl;
}
return 0;
}
Ce învățăm: testul de apartenență este o simplă verificare a vectorului de prezență: frec[x] == 1.
PbInfo - Incluziunea mulțimilor
Enunț:
Cerință: Se citesc două mulțimi de numere naturale. Să se afișeze DA dacă prima mulțime este inclusă în a doua (A ⊆ B), altfel NU.
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 DA sau NU, în funcție de incluziune.
Restricții și precizări:
1 ≤ n, m ≤ 100; elementele sunt numere naturale între 1 și 100.
Exemplu:
Intrare:
2 1 2 3 1 2 3
Ieșire:
DA
Cum gândim soluția:
- Marcăm prezența elementelor din A și din B
- Verificăm dacă există un element în A care nu este în B
- Dacă nu există, afișăm DA, altfel NU
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};
bool ok;
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;
}
ok = true;
for (i = 1; i <= 100; i++)
if (frecA[i] == 1 && frecB[i] == 0)
ok = false;
if (ok)
cout << "DA";
else
cout << "NU";
return 0;
}
Ce învățăm: A ⊆ B este adevărată dacă niciun element al lui A nu lipsește din B.
Exercițiul Practic: Verificări cu mulțimi
Sarcini de lucru
Completează următoarele sarcini pentru a aplica apartenența, incluziunea și egalitatea
Sarcina 1: Stabilește relațiile
Cerință: Pentru A = {3, 5, 7} și B = {3, 5, 7, 9}, stabilește: 5 ∈ A? A ⊆ B? A = B?
Soluție pentru Sarcina 1:
5 ∈ A: adevărat (5 este în mulțimea A) A ⊆ B: adevărat (3, 5, 7 sunt toate în B) A = B: fals (9 este în B, dar nu în A)
Sarcina 2: Scrie programul
Cerință: Scrie un program C++ care citește o mulțime A, apoi un element x și afișează DA dacă x ∈ A, altfel NU.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n, x, i, frec[101] = {0};
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
frec[x] = 1;
}
cin >> x;
if (frec[x] == 1)
cout << "DA";
else
cout << "NU";
return 0;
}