Ce vei învăța astăzi?
După această lecție vei învăța cum marcăm elementele unei mulțimi în C++, folosind vectorul de prezență și vectorul de frecvență.
Vectorul de prezență
Definiție: Un vector de prezență este un vector în care frec[x] = 1 dacă valoarea x aparține mulțimii și frec[x] = 0 dacă nu aparține.
Este cea mai simplă reprezentare a unei mulțimi în C++: prezența valorii x se marchează cu frec[x] = 1, indiferent de câte ori apare x în datele de intrare.
Exemplu: mulțimea {4, 2, 4, 1, 2, 3, 4}
| Valoare x | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| frec[x] | 1 | 1 | 1 | 1 |
Valorile prezente sunt marcate cu 1; celelalte rămân 0.
Vectorul de frecvență
Definiție: Un vector de frecvență numără de câte ori apare fiecare valoare: frec[x]++ pentru fiecare apariție a valorii x.
Pentru o mulțime ne interesează doar prezența, de aceea folosim de regulă valoarea 1. Vectorul de frecvență este util când vrem și numărul de apariții.
frec[x] = 1 dacă x există, altfel 0
frec[x] = de câte ori apare x
Reține: vectorul se inițializează cu 0 la declarare (frec[101] = {0}), apoi se marchează fiecare element.
Construirea și afișarea unei mulțimi în C++
Algoritmul are trei pași: citim valorile și le marcăm, apoi parcurgem vectorul de prezență și afișăm valorile marcate. Afișarea rezultă sortată crescător, pentru că parcurgem vectorul în ordinea indicilor.
#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;
}
for (i = 1; i <= 100; i++)
if (frec[i] == 1)
cout << i << " ";
return 0;
}
Observă: parcurgerea vectorului de la 1 la 100 afișează automat mulțimea în ordine crescătoare. Dublurile nu afectează rezultatul, pentru că marcarea se face o singură dată.
Exercițiu de completare
Completează enunțul despre reprezentarea mulțimilor:
Pentru a reprezenta o mulțime folosim un vector de ______, în care frec[x] = ______ dacă x aparține mulțimii și frec[x] = ______ dacă nu. La declarare, vectorul se inițializează cu ______.
Bancă de cuvinte:
Exercițiu de completare
Completează frazele despre marcarea elementelor:
După citirea valorii x, marcăm prezența ei cu instrucțiunea frec[x] = ______. La final, afișăm valorile i pentru care frec[i] == ______. În acest fel obținem mulțimea în ordine ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - reprezentarea mulțimilor:
1. Cum marchem prezența valorii x într-o mulțime?
2. Ce valoare are frec[5] dacă valoarea 5 nu apare în mulțime?
3. Afișând valorile i cu frec[i] == 1, parcurgând vectorul crescător, obținem:
frec[101] pentru valori 1..100) și inițializează-l cu {0}; altfel vei citi valori întâmplătoare din memorie.Aprofundare
Vector de prezență vs. vector de frecvență: vectorul de prezență marchează doar dacă o valoare apare (0 sau 1), pe când vectorul de frecvență numără de câte ori apare fiecare valoare. Pentru o mulțime ne interesează doar prezența.
- Limitarea metodei: vectorul de prezență cere valori întregi într-un domeniu cunoscut (de exemplu 1-100). Dacă apar valori mari sau negative, nu putem indexa direct; ne restrângem la restricțiile problemei sau normalizăm valorile.
- Sortare prin frecvență (counting sort): afișarea valorilor parcurgând vectorul de prezență sortează automat mulțimea crescător, fără un algoritm de sortare propriu-zis, în O(maxVal).
- Dublurile nu contează: marcarea cu
frec[x] = 1se poate repeta, dar nu modifică rezultatul; mulțimea rămâne identică. - Complexitate: construirea mulțimii cu vector de prezență se face în O(n), iar afișarea în O(V), unde V este domeniul valorilor.
- Pentru BAC: multe probleme din subiecte (numere distincte, litere distincte, elemente comune) se rezolvă direct cu vector de prezență; declară vectorul cu o poziție în plus (
frec[101]pentru valori până la 100).
PbInfo - Mulțimea
Enunț:
Cerință: Se citesc n și n numere naturale. Să se construiască mulțimea valorilor din șir și să se afișeze elementele ei în ordine crescătoare.
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 mulțimii, în ordine crescătoare, separate prin spații.
Restricții și precizări:
1 ≤ n ≤ 100; valorile citite sunt numere naturale între 1 și 100.
Exemplu:
Intrare:
6 3 1 3 2 1 5
Ieșire:
1 2 3 5
Cum gândim soluția:
- Citim n și valorile, marcând prezența fiecăreia
- Parcurgem vectorul de prezență de la 1 la 100
- Afișăm valorile marcate cu 1
Scrie soluția în C++:
Soluție corectă:
#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;
}
for (i = 1; i <= 100; i++)
if (frec[i] == 1)
cout << i << " ";
return 0;
}
Ce învățăm: vectorul de prezență elimină automat dublurile, iar parcurgerea crescătoare produce mulțimea sortată.
PbInfo - Frecvența valorilor
Enunț:
Cerință: Se citesc n și n numere naturale. Pentru fiecare valoare distinctă, să se afișeze valoarea și numărul de apariții.
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, în ordine crescătoare, fiecare valoare distinctă și frecvența ei.
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:
1 1 2 2 3 1 4 3
Cum gândim soluția:
- Citim n și valorile, incrementând frecvența fiecăreia
- Parcurgem vectorul de frecvență
- Afișăm valoarea și frecvența pentru frec[i] > 0
Scrie soluția în C++:
Soluție corectă:
#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]++;
}
for (i = 1; i <= 100; i++)
if (frec[i] > 0)
cout << i << " " << frec[i] << endl;
return 0;
}
Ce învățăm: cu frec[x]++ numărăm aparițiile fiecărei valori; condiția frec[i] > 0 identifică valorile din mulțime.
Exercițiul Practic: Construim mulțimi în C++
Sarcini de lucru
Completează următoarele sarcini pentru a reprezenta mulțimi în C++
Sarcina 1: Construiește mulțimea
Cerință: Pentru șirul 2 9 2 5 9 9 3, scrie mulțimea valorilor (distincte, sortate) și completează tabelul de prezență pentru valorile 1-9.
Soluție pentru Sarcina 1:
Mulțimea: {2, 3, 5, 9}
Prezență: frec[2]=1, frec[3]=1, frec[5]=1, frec[9]=1,
celelalte valori din 1..9 au frec = 0.
Sarcina 2: Scrie programul
Cerință: Scrie un program C++ care citește n și n numere naturale (1-100) și afișează mulțimea valorilor, sortată crescător, folosind vectorul de prezență.
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;
}
for (i = 1; i <= 100; i++)
if (frec[i] == 1)
cout << i << " ";
return 0;
}