
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:
Vectorul carac
reține dacă un număr apare sau nu într-un șir. Să se verifice
dacă există cel puțin un element nul în șir:
if(carac[???] == 1)
cout << "Da";
else
cout << "Nu";
Vectorul ani
reține numărul de evenimente înregistrate pentru fiecare an în
parte. Care este cel mai mare an care poate fi reținut în vector?
int ani[10000];
cout << ani[???];
Probleme propuse
Setul de probleme 147 nu a fost găsit.
Alte resurse sau bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0