Ce vei învăța astăzi?
După această lecție vei înțelege ce este o mulțime, de ce este un model conceptual neliniar și cum recunoaștem elementele distincte dintr-un șir de valori.
Ce este o mulțime?
Definiție: O mulțime este o colecție de elemente distincte, fără o ordine anume, considerate ca un singur obiect. Elementele care alcătuiesc mulțimea se numesc elementele mulțimii.
Mulțimea este un model conceptual neliniar: informațiile nu sunt stocate pe poziții (indecși), ca într-un șir, ci prin simpla prezență sau absență a fiecărui element.
Exemple reale de mulțimi
- Mulțimea elevilor unei clase: fiecare elev apare o singură dată, indiferent de ordinea în care i-am lista
- Mulțimea culorilor: culorile sunt distincte și nu au o ordine obligatorie
- Mulțimea literelor unui cuvânt: de exemplu, literele distincte din cuvântul „informatică"
Proprietățile unei mulțimi
O mulțime are două proprietăți esențiale:
- Elemente distincte: un element nu poate apărea de două ori într-o mulțime
- Fără ordine: mulțimea {1, 2, 3} este identică cu mulțimea {3, 2, 1}
Elemente pe poziții, pot exista dubluri, ordinea contează
Elemente distincte, fără poziții, ordinea nu contează
Observă diferența
Șirul 5 3 5 2 3 conține dubluri. Mulțimea corespunzătoare este {2, 3, 5}: fiecare valoare apare o singură dată, iar ordinea nu contează.
De la șir la mulțime în C++
Pentru a afișa elementele distincte dintr-un șir, verificăm pentru fiecare element dacă a mai apărut înainte. Dacă nu a mai apărut, înseamnă că este distinct și îl afișăm.
#include <iostream>
using namespace std;
int main() {
int n, a[100], i, j, distinct;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++) {
distinct = 1;
for (j = 1; j < i; j++)
if (a[j] == a[i])
distinct = 0;
if (distinct == 1)
cout << a[i] << " ";
}
return 0;
}
Observă: pentru fiecare element comparăm cu toate elementele dinaintea lui. Dacă nu găsim o egalitate, elementul este distinct și îl afișăm. În acest mod extragem mulțimea din șir.
Exercițiu de completare
Completează enunțul despre mulțimi cu cuvintele potrivite:
O mulțime este o colecție de elemente ______, fără o ______ anume. Spre deosebire de un ______ (vector), elementele unei mulțimi nu au ______.
Bancă de cuvinte:
Exercițiu de completare
Completează frazele despre elementele distincte:
În șirul 7 2 7 9 2, elementele distincte sunt ______, ______ și ______. Pentru a verifica dacă un element este distinct, îl comparăm cu elementele ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - mulțimi:
1. Care afirmație despre o mulțime este corectă?
2. Mulțimea {1, 2, 3} este identică cu:
3. În șirul 5 3 5 2 3, elementele distincte sunt:
Aprofundare
Modelul conceptual neliniar: spre deosebire de un șir (model liniar), unde fiecare element are o poziție (indice), mulțimea nu păstrează nici poziții, nici o ordine. Accesul la un element se face prin prezența sau absența lui, nu prin poziție. De aceea spunem că mulțimea este un model conceptual neliniar.
- Cardinalul mulțimii (notat |A|) este numărul de elemente distincte ale ei. Pentru mulțimea {2, 3, 5}, cardinalul este 3.
- Mulțimea vidă, notată ∅, nu conține niciun element și are cardinalul 0. Orice mulțime conține mulțimea vidă ca submulțime (o mulțime alcătuită numai din elemente ale altei mulțimi).
- Mulțimi finite și infinite: mulțimile pe care le prelucrăm în programe sunt finite; mulțimea numerelor naturale este un exemplu de mulțime infinită.
- Egalitatea mulțimilor nu depinde de ordinea de scriere: {1, 2, 3} = {3, 2, 1}, iar elementele nu pot fi repetate: {1, 1, 2} nu este o mulțime validă, ci un șir.
- Complexitate: algoritmul de afișare a elementelor distincte prin comparare directă are complexitate O(n), fiind potrivit pentru n ≤ 1000. Pentru valori într-un domeniu cunoscut, vectorul de prezență reduce timpul la O(n) (lecția următoare).
Pentru BAC: în subiectele de bacalaureat, noțiunea de mulțime apare în rezolvarea problemelor cu valori distincte și cu operații pe mulțimi; identifică întotdeauna întâi modelul (liniar sau neliniar), apoi alege reprezentarea.
PbInfo - Câte valori distincte
Enunț:
Cerință: Se citesc n și n numere naturale. Să se afișeze câte valori distincte conține șirul.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere naturale, separate prin spații.
Date de ieșire:
Programul va afișa pe ecran numărul de valori distincte din șir.
Restricții și precizări:
1 ≤ n ≤ 100; valorile citite sunt numere naturale între 1 și 100.
Exemplu:
Intrare:
7 4 2 4 1 2 3 4
Ieșire:
4
Cum gândim soluția:
- Citim n și cele n valori cu
cin - Pentru fiecare element verificăm dacă a mai apărut înainte
- Dacă nu a mai apărut, numărăm valoarea cu
nr++ - Afișăm numărul obținut cu
cout
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, a[100], i, j, distinct, nr = 0;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++) {
distinct = 1;
for (j = 1; j < i; j++)
if (a[j] == a[i])
distinct = 0;
if (distinct == 1)
nr++;
}
cout << nr;
return 0;
}
Ce învățăm: numărăm doar elementele care nu au mai apărut înainte. Astfel transformăm șirul într-o mulțime și îi aflăm cardinalul.
PbInfo - Elementele distincte
Enunț:
Cerință: Se citesc n și n numere naturale. Să se afișeze elementele distincte, în ordinea primei lor apariții în șir.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere naturale, separate prin spații.
Date de ieșire:
Programul va afișa pe ecran elementele distincte, separate prin spații.
Restricții și precizări:
1 ≤ n ≤ 100; valorile citite sunt numere naturale.
Exemplu:
Intrare:
6 7 2 7 9 2 3
Ieșire:
7 2 9 3
Cum gândim soluția:
- Citim n și valorile în vectorul
a - Parcurgem fiecare element și căutăm dacă mai există înaintea lui
- Dacă nu există, afișăm elementul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, a[100], i, j, distinct;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++) {
distinct = 1;
for (j = 1; j < i; j++)
if (a[j] == a[i])
distinct = 0;
if (distinct == 1)
cout << a[i] << " ";
}
return 0;
}
Ce învățăm: afișăm fiecare element care nu a mai apărut înainte. Rezultatul este mulțimea valorilor din șir, păstrând ordinea primei apariții.
Exercițiul Practic: De la șir la mulțime
Sarcini de lucru
Completează următoarele sarcini pentru a-ți consolida cunoștințele despre mulțimi
Sarcina 1: Identifică elementele distincte
Cerință: Pentru șirul 8 4 8 1 4 4 6, scrie elementele distincte și explică de ce mulțimea rezultată este un model neliniar.
Soluție pentru Sarcina 1:
Elementele distincte: 8, 4, 1, 6 Explicație: valorile nu sunt stocate pe poziții (indecși), ci doar prin prezența lor; ordinea și dublurile nu contează, de aceea mulțimea este un model conceptual neliniar.
Sarcina 2: Scrie programul
Cerință: Scrie un program C++ care citește n și n numere naturale, apoi afișează elementele distincte, în ordinea primei apariții.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n, a[100], i, j, distinct;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++) {
distinct = 1;
for (j = 1; j < i; j++)
if (a[j] == a[i])
distinct = 0;
if (distinct == 1)
cout << a[i] << " ";
}
return 0;
}