Vectorul de Frecvență: “Contorul Secret” al Programatorului – Materie BAC

Bun, hai să vorbim despre unul dintre cele mai elegante și utile trucuri din programare: VECTORUL DE FRECVENȚĂ. Nu e doar despre numărare (cuvânt simplu) și statistică. E despre cum transformi o problemă complexă de căutare într-o operație instantanee. E un concept atât de puternic încât dacă ai înțelege-l bine, ai rezolva multe probleme care altfel par grele.

1. Ce este un Vector de Frecvență? “O Tablă de Scor” pentru Numere

Gândește-te la el ca la un tabel unde notezi de câte ori ai văzut fiecare număr:

Dacă ai numerele: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3

Număr	0	1	2	3	4	5	6	7	8	9
De câte ori apare	0	2	1	2	1	2	1	0	0	1

Asta e vectorul de frecvență!

De ce e atât de util?

• Căutare instantanee: “Numărul 3 apare?” → Verifici poziția 3 în vector
• Numărări rapide: “Câte numere pare sunt?” → Aduni frecvențele numerelor pare
• Statistici: Care e cel mai frecvent număr? → Cauți maximul în vector

2. Cum Funcționează? “Index Direct”

#include <iostream>
using namespace std;

int main() {
    // Vector cu numere între 0 și 9
    int numere[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n = 10;

    // Vector de frecvență pentru numere 0-9
    int frecventa[10] = {0};  // Toate elementele 0

    cout << "Numerele noastre: ";
    for(int i = 0; i < n; i++) {
        cout << numere[i] << " ";
    }
    cout << endl;

    // Construim vectorul de frecvență
    for(int i = 0; i < n; i++) {
        int numar = numere[i];
        frecventa[numar]++;  // Crește contorul pentru acel număr
    }

    // Afișăm rezultatele
    cout << "\n=== VECTORUL DE FRECVENȚĂ ===\n";
    for(int i = 0; i < 10; i++) {
        if(frecventa[i] > 0) {  // Afișăm doar numerele care apar
            cout << "Numarul " << i << " apare de " << frecventa[i] << " ori\n";
        }
    }

    return 0;
}

Ce se întâmplă în spate:

Când întâlnește 3: frecventa[3] devine 1
Când întâlnește 1: frecventa[1] devine 1  
Când întâlnește 4: frecventa[4] devine 1
Când întâlnește 1: frecventa[1] devine 2 (a doua apariție)
... și așa mai departe

3. Aplicații Practice Simple

Aplicația 1: Verifică dacă toate numerele sunt unice

#include <iostream>
using namespace std;

int main() {
    int numere[] = {3, 1, 4, 2, 5, 6};
    int n = 6;

    int frecventa[10] = {0};
    bool toateUnice = true;

    for(int i = 0; i < n; i++) {
        int numar = numere[i];

        if(frecventa[numar] > 0) {
            // Am mai văzut acest număr!
            toateUnice = false;
            cout << "Numarul " << numar << " se repeta!\n";
            break;
        }

        frecventa[numar]++;
    }

    if(toateUnice) {
        cout << "Toate numerele sunt unice!\n";
    }

    return 0;
}

Aplicația 2: Găsește elementul care apare cel mai mult

#include <iostream>
using namespace std;

int main() {
    int numere[] = {2, 3, 2, 4, 3, 2, 5, 2, 3};
    int n = 9;

    // Presupunem numere între 0 și 10
    int frecventa[11] = {0};

    // Calculează frecvențele
    for(int i = 0; i < n; i++) {
        frecventa[numere[i]]++;
    }

    // Găsește maximul
    int maxFrecventa = 0;
    int numarMax = -1;

    for(int i = 0; i < 11; i++) {
        if(frecventa[i] > maxFrecventa) {
            maxFrecventa = frecventa[i];
            numarMax = i;
        }
    }

    cout << "Numarul " << numarMax << " apare de cele mai multe ori: " 
         << maxFrecventa << " ori\n";

    return 0;
}

4. Cum Decizi Dimensiunea Vectorului de Frecvență?

Regula importantă: Vectorul trebuie să aibă cel puțin (valoare_maximă + 1) elemente!

#include <iostream>
using namespace std;

int main() {
    // Exemplu: Note la un test (nota maximă posibilă este 10)
    int note[] = {9, 7, 10, 5, 8, 9, 7, 6, 10, 8};
    int n = 10;

    // Dimensiunea corectă: nota_maxima + 1 = 10 + 1 = 11
    int frecventaNote[11] = {0};  // Indici de la 0 la 10

    for(int i = 0; i < n; i++) {
        int nota = note[i];
        frecventaNote[nota]++;  // Corect: nota 10 merge în frecventaNote[10]
    }

    cout << "Distributia notelor:\n";
    for(int i = 0; i < 11; i++) {
        if(frecventaNote[i] > 0) {
            cout << "Nota " << i << ": " << frecventaNote[i] << " elevi\n";
        }
    }

    // GREȘIT: int frecventaGresita[10] - nota 10 ar da eroare!

    return 0;
}

5. Vector de Frecvență pentru Caractere (Litere)

#include <iostream>
using namespace std;

int main() {
    string text = "abracadabra";

    // Vector de frecvență pentru litere mici (a-z)
    // Literele au coduri ASCII: 'a'=97, 'b'=98, ..., 'z'=122
    int frecventaLitere[26] = {0};  // 26 de litere

    for(int i = 0; i < text.length(); i++) {
        char litera = text[i];
        // Transformă din caracter în index 0-25
        int index = litera - 'a';  // 'a'-'a'=0, 'b'-'a'=1, etc.
        frecventaLitere[index]++;
    }

    cout << "Frecventa literelor in \"" << text << "\":\n";
    for(int i = 0; i < 26; i++) {
        if(frecventaLitere[i] > 0) {
            char litera = 'a' + i;  // Transformă înapoi în caracter
            cout << litera << ": " << frecventaLitere[i] << " aparitii\n";
        }
    }

    return 0;
}

Cum funcționează conversia:

char litera = 'c';
int index = litera - 'a';  // 'c' - 'a' = 99 - 97 = 2

// Pentru a transforma înapoi:
char literaOriginala = 'a' + index;  // 'a' + 2 = 'c'

6. Comparație: Vector de Frecvență vs Căutare Tradițională

#include <iostream>
#include <ctime>
using namespace std;

int main() {
    const int n = 10000;
    int numere[n];

    // Generează numere aleatoare între 0 și 100
    srand(time(0));
    for(int i = 0; i < n; i++) {
        numere[i] = rand() % 101;  // 0-100
    }

    int numarCautat = 42;

    // METODA 1: Căutare liniară (tradițională)
    clock_t start = clock();

    int aparitiiMetoda1 = 0;
    for(int i = 0; i < n; i++) {
        if(numere[i] == numarCautat) {
            aparitiiMetoda1++;
        }
    }

    clock_t end = clock();
    double timpMetoda1 = double(end - start) / CLOCKS_PER_SEC;

    // METODA 2: Vector de frecvență (inteligentă)
    start = clock();

    int frecventa[101] = {0};
    for(int i = 0; i < n; i++) {
        frecventa[numere[i]]++;
    }
    int aparitiiMetoda2 = frecventa[numarCautat];

    end = clock();
    double timpMetoda2 = double(end - start) / CLOCKS_PER_SEC;

    // Rezultate
    cout << "Caut numarul " << numarCautat << " in " << n << " numere:\n";
    cout << "Metoda liniara: " << aparitiiMetoda1 << " aparitii, " 
         << timpMetoda1 << " secunde\n";
    cout << "Vector frecventa: " << aparitiiMetoda2 << " aparitii, " 
         << timpMetoda2 << " secunde\n";

    if(timpMetoda1 > 0) {
        cout << "Vectorul de frecventa este de " 
             << timpMetoda1/timpMetoda2 << "x mai rapid!\n";
    }

    return 0;
}

7. Probleme Practice cu Vector de Frecvență

Problema 1: Verifică dacă un șir este anagramă

#include <iostream>
using namespace std;

int main() {
    string cuvant1 = "listen";
    string cuvant2 = "silent";

    // Vector de frecvență pentru ambele cuvinte
    int frecventa1[26] = {0};
    int frecventa2[26] = {0};

    // Calculează frecvențele pentru primul cuvânt
    for(int i = 0; i < cuvant1.length(); i++) {
        char c = cuvant1[i];
        frecventa1[c - 'a']++;
    }

    // Calculează frecvențele pentru al doilea cuvânt
    for(int i = 0; i < cuvant2.length(); i++) {
        char c = cuvant2[i];
        frecventa2[c - 'a']++;
    }

    // Compară vectorii de frecvență
    bool suntAnagrame = true;
    for(int i = 0; i < 26; i++) {
        if(frecventa1[i] != frecventa2[i]) {
            suntAnagrame = false;
            break;
        }
    }

    if(suntAnagrame) {
        cout << "\"" << cuvant1 << "\" si \"" << cuvant2 << "\" sunt anagrame!\n";
    } else {
        cout << "NU sunt anagrame!\n";
    }

    return 0;
}

Problema 2: Elementul lipsă dintr-un șir de numere

#include <iostream>
using namespace std;

int main() {
    // Avem numerele de la 1 la 10, dar lipsește unul
    int numere[] = {1, 2, 3, 4, 6, 7, 8, 9, 10};
    int n = 9;  // Ar trebui să fie 10

    // Vector de frecvență pentru numere 1-10
    int frecventa[11] = {0};  // Indici 0-10, dar folosim doar 1-10

    // Marchează numerele pe care le avem
    for(int i = 0; i < n; i++) {
        int numar = numere[i];
        frecventa[numar] = 1;  // 1 = prezent, 0 = lipsă
    }

    // Caută numărul lipsă (cel cu frecvența 0)
    cout << "Numerele noastre: ";
    for(int i = 0; i < n; i++) {
        cout << numere[i] << " ";
    }
    cout << "\n\n";

    cout << "Numarul/e lipsa: ";
    for(int i = 1; i <= 10; i++) {
        if(frecventa[i] == 0) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

8. Limitări și Soluții

Problema: Dacă numerele sunt foarte mari (ex: 1.000.000.000), nu putem face vector de frecvență!

Soluție 1: Folosește vector de bool (dacă doar vrei să știi dacă există)

#include <iostream>
using namespace std;

int main() {
    const int MAX = 1000;  // Dacă știm valoarea maximă
    bool exista[MAX] = {false};

    int numere[] = {150, 450, 300, 150, 750};
    int n = 5;

    for(int i = 0; i < n; i++) {
        exista[numere[i]] = true;
    }

    int numarCautat = 300;
    if(exista[numarCautat]) {
        cout << numarCautat << " exista in sir\n";
    }

    return 0;
}

Soluție 2: Normalizează numerele (dacă nu sunt prea împrăștiate)

#include <iostream>
using namespace std;

int main() {
    // Numere mari dar consecutive
    int numere[] = {1001, 1002, 1003, 1005, 1002};
    int n = 5;

    // Găsește minimul
    int minim = numere[0];
    for(int i = 1; i < n; i++) {
        if(numere[i] < minim) {
            minim = numere[i];
        }
    }

    // Normalizează (scade minimul)
    int frecventa[10] = {0};  // Presupunem că nu sunt mai mult de 10 numere diferite

    for(int i = 0; i < n; i++) {
        int index = numere[i] - minim;  // 1001-1001=0, 1002-1001=1, etc.
        frecventa[index]++;
    }

    cout << "Frecventa numerelor (normalizate):\n";
    for(int i = 0; i < 10; i++) {
        if(frecventa[i] > 0) {
            int numarReal = minim + i;
            cout << numarReal << ": " << frecventa[i] << " aparitii\n";
        }
    }

    return 0;
}

9. PROIECT INTEGRAT: Analizor de Text

#include <iostream>
using namespace std;

int main() {
    string text;

    cout << "Introdu un text: ";
    getline(cin, text);

    // Vectori de frecvență pentru diferite analize
    int litere[26] = {0};      // Litere mici a-z
    int cifre[10] = {0};       // Cifre 0-9
    int spatii = 0;
    int vocale = 0;
    int consoane = 0;

    // Analizează fiecare caracter
    for(int i = 0; i < text.length(); i++) {
        char c = text[i];

        if(c >= 'a' && c <= 'z') {
            // Literă mică
            litere[c - 'a']++;

            // Verifică dacă e vocală
            if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                vocale++;
            } else {
                consoane++;
            }
        }
        else if(c >= 'A' && c <= 'Z') {
            // Literă mare - transformă în mică pentru uniformitate
            char literaMica = c + 32;  // 'A'+32='a'
            litere[literaMica - 'a']++;

            if(literaMica == 'a' || literaMica == 'e' || 
               literaMica == 'i' || literaMica == 'o' || literaMica == 'u') {
                vocale++;
            } else {
                consoane++;
            }
        }
        else if(c >= '0' && c <= '9') {
            // Cifră
            cifre[c - '0']++;
        }
        else if(c == ' ') {
            // Spațiu
            spatii++;
        }
    }

    // Afișează rezultatele
    cout << "\n=== REZULTATE ANALIZA TEXT ===\n";
    cout << "Lungime text: " << text.length() << " caractere\n";
    cout << "Spatii: " << spatii << "\n";
    cout << "Vocale: " << vocale << "\n";
    cout << "Consoane: " << consoane << "\n\n";

    // Literele care apar cel puțin o dată
    cout << "Distributia literelor:\n";
    for(int i = 0; i < 26; i++) {
        if(litere[i] > 0) {
            char litera = 'a' + i;
            cout << litera << ": " << litere[i] << "  ";
            if((i+1) % 8 == 0) cout << endl;  // 8 pe linie
        }
    }
    cout << "\n\n";

    // Cifrele care apar
    cout << "Cifre gasite: ";
    bool areCifre = false;
    for(int i = 0; i < 10; i++) {
        if(cifre[i] > 0) {
            cout << i << "(" << cifre[i] << ") ";
            areCifre = true;
        }
    }
    if(!areCifre) cout << "niciuna";
    cout << endl;

    // Cea mai frecventă literă
    int maxFrecventa = 0;
    char literaComuna = ' ';

    for(int i = 0; i < 26; i++) {
        if(litere[i] > maxFrecventa) {
            maxFrecventa = litere[i];
            literaComuna = 'a' + i;
        }
    }

    if(maxFrecventa > 0) {
        cout << "Litera cea mai comuna: '" << literaComuna 
             << "' (" << maxFrecventa << " aparitii)\n";
    }

    return 0;
}

10. Exerciții de Înțelegere

Exercițiul 1: Completează codul

#include <iostream>
using namespace std;

int main() {
    int numere[] = {5, 2, 8, 5, 9, 2, 5, 1, 8};
    int n = 9;

    // TODO: Crează vector de frecvență pentru numere 0-10
    int frecventa[11] = {0};

    // TODO: Calculează frecvențele
    for(int i = 0; i < n; i++) {
        // Scrie codul aici
    }

    // TODO: Afișează numerele care apar de exact 2 ori
    cout << "Numere care apar de 2 ori: ";
    for(int i = 0; i < 11; i++) {
        // Scrie codul aici
    }

    return 0;
}

Soluție:

// În bucla de calcul:
frecventa[numere[i]]++;

// În bucla de afișare:
if(frecventa[i] == 2) {
    cout << i << " ";
}

Exercițiul 2: Probleme rapide de rezolvat

1. Ai numerele: 3, 7, 3, 2, 7, 3, 1. Ce va afișa frecventa[3]?
2. Cum afli câte numere unice sunt într-un vector?
3. Cum verifici dacă un vector are doar numere pare folosind frecvența?

Răspunsuri:

1. frecventa[3] va fi 3 (numărul 3 apare de 3 ori)
2. Numări câte elemente din vectorul de frecvență au valoarea 1
3. Verifici dacă frecventa[1] + frecventa[3] + frecventa[5] + ... sunt 0

În concluzie, să-ți spun ceva practic:

Vectorul de frecvență e ca o “memorie cache” pentru datele tale. În loc să cauți de fiecare dată în vectorul mare, întrebi direct memoria cache “de câte ori am văzut acest număr?”.

Dar folosirea lui pentru numere foarte mari sau foarte împrăștiate poate fi, paradoxal, o pierdere enormă de memorie dacă aloci 1.000.000.000 de elemente pentru 10 numere.

Așa că ai grijă când îl folosești. Cunoștințe-ti datele: care e intervalul? Câte valori diferite sunt? Merită să aloci atâta memorie? Pentru că puterea de a răspunde instant la întrebări este goală fără înțelegerea costurilor memoriei. Și această putere vine cu o responsabilitate: să fii eficient și practic.

Vectorul de frecvență e unealta perfectă pentru multe probleme – când știi să o folosești corespunzător. Ai grijă de ea cu aceeași seriozitate.