Ce vei învăța astăzi?
După această lecție vei învăța cum eliminăm dublurile dintr-un șir și cum numărăm elementele distincte folosind vectorul de frecvență.
Problema dublurilor
Un șir poate conține valori repetate. Când vrem să lucrăm cu mulțimea valorilor, trebuie să ținem cont de fiecare valoare o singură dată.
De exemplu, în șirul 3 5 3 3 5 2, valorile distincte sunt {2, 3, 5}.
Două abordări
- Comparare directă: pentru fiecare element verificăm dacă a mai apărut înainte (lejer, dar lent)
- Vector de frecvență: marcăm valoarea la prima apariție și numărăm marcați (eficient)
Tehnica marcare-numărare
Ideea: când citim valoarea x, dacă frec[x] == 0, înseamnă că o vedem pentru prima dată. O marcăm (frec[x] = 1) și numărăm (nr++). Dacă frec[x] == 1, este un dublu și îl ignorăm.
Parcurgerea șirului 3 5 3 3 5 2
Rezultat: numărul de elemente distincte este 3.
Numărarea elementelor distincte în C++
#include <iostream>
using namespace std;
int main() {
int n, x, i, frec[101] = {0}, nr = 0;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
if (frec[x] == 0) {
frec[x] = 1;
nr++;
}
}
cout << nr;
return 0;
}
Observă: numărăm doar valorile întâlnite pentru prima dată. Astfel, fiecare valoare distinctă contribuie exact o dată la rezultat.
Exercițiu de completare
Completează enunțul despre eliminarea dublurilor:
În șirul 4 1 4 2 1, valorile distincte sunt ______: ______, 1 și 2. O valoare apare o singură dată în ______.
Bancă de cuvinte:
Exercițiu de completare
Completează fraza despre marcare:
Când întâlnim valoarea x, dacă frec[x] == ______, o vedem pentru prima dată: o marcăm cu frec[x] = 1 și incrementăm ______. Dacă frec[x] este deja 1, înseamnă că este un ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - eliminarea dublurilor:
1. Câte valori distincte are șirul 2 2 3 2 5 3?
2. Când numărăm elementele distincte, dublul unei valori:
3. Condiția care indică prima apariție a valorii x este:
frec[x] == 0, nu frec[x] == 1; altfel vei număra valorile greșit.Aprofundare
Tehnica marcare-numărare este o aplicație directă a vectorului de frecvență și reduce complexitatea eliminării dublurilor de la O(n) (comparare directă) la O(n).
- Condiția cheie: numărăm o valoare doar dacă o vedem pentru prima dată:
if (frec[x] == 0) { frec[x] = 1; nr++; }. - Valori mari: dacă valorile depășesc domeniul unui vector rezonabil, se poate sorta șirul și număra apoi valorile consecutive diferite, în O(n log n).
- Frecvență completă: dacă problema cere de câte ori apare fiecare valoare, folosim
frec[x]++în loc defrec[x] = 1; numărul de distincte devine numărul de poziții cufrec[i] > 0. - Legătura cu mulțimea: vectorul de prezență rezultat după marcare este exact reprezentarea mulțimii valorilor din șir, iar
nreste cardinalul (numărul de elemente) ei. - Pentru BAC: această tehnică apare în problemele "câte valori distincte", "de câte ori apare un element", "elemente care apar o singură dată".
PbInfo - Numărarea elementelor 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.
Restricții și precizări:
1 ≤ n ≤ 100; valorile citite sunt numere naturale între 1 și 100.
Exemplu:
Intrare:
8 4 1 4 2 1 4 2 3
Ieșire:
4
Cum gândim soluția:
- Marcăm fiecare valoare la prima apariție
- Numărăm valorile marcate
- Afișăm numărul obținut
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, x, i, frec[101] = {0}, nr = 0;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
if (frec[x] == 0) {
frec[x] = 1;
nr++;
}
}
cout << nr;
return 0;
}
Ce învățăm: metoda marcare-numărare elimină dublurile la citire, fără a mai fi nevoie să păstrăm întregul șir.
PbInfo - Afișarea fără dubluri
Enunț:
Cerință: Se citesc n și n numere naturale. Să se afișeze valorile distincte, în ordine crescătoare, fără dubluri.
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 valorile distincte, î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:
8 4 1 4 2 1 4 2 3
Ieșire:
1 2 3 4
Cum gândim soluția:
- Marcăm prezența fiecărei valori
- Parcurgem vectorul de prezență crescător
- Afișăm valorile marcate
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ă dublurile, iar parcurgerea crescătoare produce lista sortată fără repetiții.
Exercițiul Practic: Eliminăm dublurile
Sarcini de lucru
Completează următoarele sarcini pentru a elimina dublurile dintr-un șir
Sarcina 1: Numără distinctele
Cerință: Pentru șirul 7 1 7 2 1 7 3 3, scrie câte valori distincte există și enumeră-le.
Soluție pentru Sarcina 1:
Număr de valori distincte: 4 Valorile: 1, 2, 3, 7
Sarcina 2: Scrie programul
Cerință: Scrie un program C++ care citește n și n numere naturale, apoi afișează numărul de valori distincte folosind metoda marcare-numărare.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n, x, i, frec[101] = {0}, nr = 0;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> x;
if (frec[x] == 0) {
frec[x] = 1;
nr++;
}
}
cout << nr;
return 0;
}