Vectori de frecvență (de apariții) în C++

Ce este un vector de apariții (de frecvență)?

Vectorul de frecvență este un vector care reține numărul de apariții al fiecărei valori dintr-un șir. Mai exact, un astfel de vector de apariții ne ajută să determinăm pentru orice valoare, de câte ori apare în șirul nostru (chestie care ne poate ajuta în cazul unor probleme mai dificile).

Să luăm un exemplu — dacă avem vectorul (1, 4, 4, 5, 2, 4, 5, 7, 4, 1) cu valori între 0 și 9, atunci putem să aflăm de câte ori apare fiecare număr în parte.

În exemplul de mai sus am implementat un vector de frecvențe pe care l-am numit intuitiv fr[]. Acest vector are lungimea 10 (cuprinde elemente de la 0 la 9), iar elementul fr[i] reține numărul de apariții al numărului i în șirul dat, unde 0 ≤ i ≤ 9.

Implementarea unui vector de frecvență în C++

Să zicem că avem un șir cu elemente mai mici decât 100. Atunci, vectorul nostru de frecvență (pe care noi îl vom numi fr) trebuie să aibă lungimea de cel puțin 100, astfel încât toate valorile posibile din șir să aibă o poziție în vectorul fr.

Cum se adaugă un element în vectorul de apariții

Să zicem că vrem să adăugăm un număr x în vectorul nostru de frecvență fr. Atunci, va trebui să marcăm faptul că numărul de apariții ale numărului x crește cu 1; așadar, fr[x]++.

Algoritm

Citim numerele pe rând și le adăugăm în vectorul de frecvență, urmând să afișăm pe ecran numărul de apariții al fiecărui număr în parte.

#include <iostream>

using namespace std;

int n, fr[101]; //Pentru ca vectorul să rețină numerele de la 1 la 100, trebuie să aibă lungimea minimă 101

int main()
{
    //Citim n și n numere naturale între 1 și 100
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        fr[x]++; //Îl adăugăm pe x, incrementând numărul său de apariții cu 1
    }

    //Afișăm numărul de apariții ale fiecărui element
    for(int i = 1; i <= 100; i++) {
        if(fr[i] > 0) { //Dacă numărul i apare în șir (de mai mult de 0 ori)
            cout << i << " apare de " << fr[i] << " ori in sir\n";
        }
    }
    return 0;
}

Ce este un vector caracteristic?

Similar cu vectorul de frecvență, vectorul caracteristic reține, pentru fiecare valoare în parte, doar dacă aceasta apare sau nu în șir. Mai precis, vectorul caracteristic reține:

• 0, dacă elementul nu apare în șir;
• 1, dacă elementul apare în șir.

Implementarea unui vector caracteristic în C++

Vom adapta codul de mai devreme. Adăugarea unui element în vectorul caracteristic constă în transformarea valorii sale în vector în 1, pentru a marca faptul că există. De asemenea, am numit vectorul carac pentru a avea un nume mai intuitiv.

#include <iostream>

using namespace std;

int n, carac[101]; //Pentru ca vectorul să rețină numerele de la 1 la 100, trebuie să aibă lungimea minimă 101

int main()
{
    //Citim n și n numere naturale între 1 și 100
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        carac[x] = 1; //Îl adăugăm pe x, marcând în vector cu 1 faptul că există
    }

    //Afișăm elementele care apar în șir
    for(int i = 1; i <= 100; i++) {
        if(carac[i] > 0) { //Dacă numărul i apare în șir
            cout << i << " apare in sir\n";
        }
    }
    return 0;
}

Probleme rezolvate

#525 Numere1 (PbInfo)

Se dau n numere naturale. Determinați cele mai mari două numere cu trei cifre care nu apar printre numerele date. Puteți să vedeți enunțul complet și să vă testați soluția pe această pagină.

Exemplu: Pentru n = 10 numere: 10, 994, 1010, 999, 1010, 998, 1005, 994, 996, 995, cele mai mari două numere care nu apar printre numerele date sunt 993 și 997.

Rezolvare: Vom utiliza un vector caracteristic. Deoarece numerele date pot avea orice valoare, dar pe noi ne interesează doar numerele de trei cifre, vom lua în considerare, în citire, doar numerele cu exact trei cifre (între 100 și 999 inclusiv). La final, vom parcurge numerele de la 999 în jos, iar când întâlnim câte un număr care nu apare în vectorul caracteristic, îl luăm în considerare. Dacă am găsit ambele numere, atunci le afișăm, altfel, afișăm pe ecran mesajul NU EXISTA.

#include <iostream>

using namespace std;

int carac[1000]; //Elementele sunt între 100 și 999, așadar vectorul trebuie să fie de minimum 1000 de elemente pentru ca numerele să poată încăpea

int main()
{
    //Citim n și cele n numere naturale
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if(100 <= x && x <= 999) { //Ne interesează doar numerele cu exact trei cifre
            carac[x] = 1;
        }
    }
    int nr1 = -1, nr2 = -1; //Cele două numere căutate
    for(int i = 999; i >= 100; i--) {
        if(v[i] == 0) { //Am găsit un număr care nu apare în șir
            if(nr2 == -1) nr2 = i;
            else if(nr1 == -1) {
                nr1 = i;
                break; //Ne oprim după ce am găsit ambele numere
            }
        }
    }
    if(nr1 == -1) cout << "NU EXISTA";
    else cout << nr1 << " " << nr2;
    return 0;
}

#244 CifreOrd (PbInfo)

Se dau n cifre zecimale. Să se afișeze aceste cifre în ordine crescătoare. Puteți să vedeți enunțul complet și să vă testați soluția pe această pagină.

Exemplu: Pentru n = 25 și cifrele 1 1 2 7 3 5 1 5 3 6 7 8 0 1 0 5 6 3 8 2 9 7 9 5 7, cifrele în ordine crescătoare sunt 0 0 1 1 1 1 2 2 3 3 3 5 5 5 5 6 6 7 7 7 7 8 8 9 9.

Rezolvare: Deoarece vorbim de cifre, va trebui să formăm un vector de frecvență fr cu 10 poziții (de la 0 la 9). Citim cifrele și le adăugăm în vector, după care parcurgem cifrele de la 0 la 9. Pentru fiecare cifră i, știm că aceasta apare de fr[i] ori în șirul inițial, așadar va trebui să afișăm cifra i pe ecran de fr[i] de ori. Deoarece afișăm cifrele de la 0 la 9, se garantează faptul că le afișăm în ordine crescătoare. Nu în ultimul rând, deoarece așa specifică enunțul inițial al problemei, odată la 20 de numere afișate trebuie să trecem la un rând nou.

#include <fstream>

using namespace std;

ifstream fin("cifreord.in");
ofstream fout("cifreord.out");

int fr[10], nrafis; //nrafis reprezintă numărul de numere afișate

int main()
{
    //Citim n și cele n cifre
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        int cif;
        fin >> cif;
        fr[cif]++;
    }
    for(int i = 0; i <= 9; i++) {
        for(int j = 1; j <= fr[i]; j++) { //Afișăm cifra i de fr[i] ori (de atâtea ori apare)
            fout << i << " ";
            nrafis++;
            if(nrafis % 20 == 0) fout << "\n";
        }
    }
    return 0;
}

Exerciții propuse

Completează următoarele secvențe de cod:

if(carac[???] == 1)
    cout << "Da";
else
    cout << "Nu";

int ani[10000];
cout << ani[???];

Probleme propuse

Alte resurse sau bibliografie

• Vectori de frecvență 11A
• PbInfo: Vectori caracteristici și de frecvență
• UAIC: Lecția 9 — Vectori de frecvență