Vectorii caracteristici și vectorii de frecvență reprezintă două aplicații foarte simple ale vectorilor, ce se bazează pe accesul indexat la elementele lor (faptul că orice element poate fi accesat în timp constant știind poziția sa în vector). În acest articol voi prezenta la ce se referă cele două tipuri de vectori, precum și câteva tehnici de utilizare a lor.
Vectori caracteristici
Într-un vector caracteristic, pe poziția i
este stocată o informație despre numărul i
. De cele mai multe ori, pe poziția i
se va găsi o valoare booleană (true
sau false
) care indică, spre exemplu, dacă i
se află într-o listă dată de întregi sau nu. Asta e tot Acum, iată câteva probleme simple cu vectori caracteristici:
Problema 1.
Se citesc
n
numere întregi cuprinse între-1000
și1000
. Pentru fiecare dintre următoareleq
numere date (din același interval), să se afișeze dacă acesta se regăsește în șirul dat.
O soluție naivă este să reținem cele n
numere într-un vector auxiliar, iar pentru fiecare interogare să căutăm numărul dat în acel vector. Complexitatea algoritmului este $O(q \cdot n)$, foarte proastă pentru valori mari ale celor două variabile. Putem sorta vectorul ca apoi să folosim căutare binară, reducând complexitatea la $O((n + q) \log n)$, dar tot nu e cine știe ce.
#include <iostream>
using namespace std;
const int VMAX = 1000;
int n, q;
int v[VMAX];
int main() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> v[i];
cin >> q;
for (int i = 0; i < q; i++) {
int x; cin >> x;
bool ok = false;
for (int j = 0; j < n; j++)
if (v[j] == x) {
ok = true;
break;
}
cout << (ok ? "DA\n" : "NU\n");
}
return 0;
}
Ce ar fi să încercăm să răspundem la interogări în $O(1)$? Dacă tot vorbim despre vectori caracteristici, putem memora un vector caracteristic chr
în care pe poziția i
vom reține dacă i
se găsește printre numerele date sau nu. Astfel, nici nu este nevoie să reținem numerele citite. La final, vom afișa pentru fiecare număr x
pe chr[x]
.
#include <iostream>
using namespace std;
const int VMAX = 1000;
int n, q;
bool chr[VMAX];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
chr[x] = true;
}
cin >> q;
for (int i = 0; i < q; i++) {
int x; cin >> x;
cout << (chr[x] ? "DA\n" : "NU\n");
}
return 0;
}
Defectul acestui algoritm este că programul va crăpa pentru numere negative, deoarece C++ nu suportă vectori statici indexați negativ. Putem folosi o constantă MASK = 1000
, iar atunci când vrem să accesăm informația despre x
, vom scrie chr[x + MASK]
. Astfel, vom accesa doar elemente de pe poziții pozitive. Pentru -1000
vom accesa chr[0]
, pentru 618
chr[1618]
etc. Atenție la dimensiunea maximă a vectorului! Aceasta trebuie să fie minim 2001
(1000
de numere strict negative, 1000
strict pozitive, un 0
).
#include <iostream>
using namespace std;
const int VMAX = 2001;
const int MASK = 1000;
int n, q;
bool chr[VMAX];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
chr[x + MASK] = true;
}
cin >> q;
for (int i = 0; i < q; i++) {
int x; cin >> x;
cout << (chr[x + MASK] ? "DA\n" : "NU\n");
}
return 0;
}
Problema 2.
Se dau
n
numere naturale de maxim8
cifre. Să se afișeze cel mai mic și cel mai mare număr de3
cifre care nu apar în șirul dat. Se garantează că există întotdeauna soluție.
Reținem numerele prezente în șir printr-un vector caracteristic chr
. O idee de optimizare este să ignorăm de la citire numerele cu mai mult sau mai puțin de 3
cifre. Altfel, vectorul caracteristic ar trebui să aibă minim 1 miliard
de elemente – cam mult.
O altă idee este să folosim o mască negativă (ca mai sus), astfel încât în loc de chr[100]
să accesăm chr[0]
, în loc de chr[999]
chr[899]
etc. În acest mod, vom reține cu 100
de elemente mai puțin, însă la fiecare accesare vom fi nevoiți să efectuăm o scădere. Din această cauză, nu-și are rost această „optimizare”, însă ideea poate fi utilă în alte contexte.
După etapa citirii, va trebui doar să parcurgem vectorul caracteristic de la primul index de 3
cifre până la ultimul și să ne oprim la primul element cu valoarea false
. Apoi vom face același lucru, dar în sens invers.
#include <iostream>
using namespace std;
const int VMAX = 1000;
int n;
bool chr[VMAX];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
if (100 <= x && x <= 999)
chr[x] = true;
}
for (int i = 100; chr[i]; i++); cout << i << '\n';
for (int i = 999; chr[i]; i--); cout << i << '\n';
return 0;
}
Problema 3.
Se citesc
n
numere naturale de maxim3
cifre. Să se afișeze, fără repetiții, în ordine crescătoare, numerele pare ce se regăsesc printre numerele date, iar apoi cele impare, în ordine descrescătoare.
Reținem numerele într-un vector caracteristic, iar apoi facem exact ce scrie în enunț… În general, problemele cu vectori caracteristici și cu vectori de frecvență, după citirea datelor, se rezumă doar la parcurgerea vectorilor.
#include <iostream>
using namespace std;
const int VMAX = 1000;
int n;
bool chr[VMAX];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
chr[x] = true;
}
for (int i = 0; i <= 998; i += 2)
if (chr[i])
cout << i << ' ';
cout << '\n';
for (int i = 999; i >= 1; i -= 2)
if (chr[i])
cout << i << ' ';
cout << '\n';
return 0;
}
Vectori de frecvență
Vectorii de frecvență seamănă izbitor de bine cu cei caracteristici, singura diferență fiind că pe poziția i
aceștia rețin numărul de apariții ale lui i
(frecvența lui i
).
Problema 1.
Se citesc
n
numere naturale de maxim3
cifre. Să se determine numerele prime ce aparțin acestui șir, cât și frecvențele lor.
Reținem un vector de frecvență frq
cu numărul de apariții ale tuturor numerelor posibile ce pot aparține șirului dat. Apoi îl parcurgem, iar pentru indecșii i
primi și cu frecvența nenulă (cei care apar în șir), afișăm i
și frq[i]
.
#include <iostream>
using namespace std;
const int VMAX = 1000;
int n;
int frq[VMAX];
bool isPrime(int x) {
if (x == 2)
return true;
if (x % 2 == 0)
return false;
for (int i = 3; i * i <= x; i += 2)
if (x % i == 0)
return false;
return true;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
frq[x]++;
}
for (int i = 2; i <= 997; i++)
if (frq[i] && isPrime(i))
cout << i << ' ' << frq[i] << '\n';
return 0;
}
Problema 2.
Se citesc
n
numere naturale. Să se determine numărul cu cea mai mare frecvență. Dacă sunt mai multe soluții, se va afișa cea maximă.
După ce formăm vectorul de frecvență, calculăm frecvența maximă, reținând în același timp și numărul ce o deține.
#include <iostream>
using namespace std;
const int VMAX = 100;
int n;
int frq[VMAX];
int sol;
int frqMax;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x; cin >> x;
frq[x]++;
if (frq[x] > frqMax) {
frqMax = frq[x];
sol = x;
}
else if (frq[x] == frqMax && x > sol)
sol = x;
}
cout << sol << '\n';
return 0;
}
Problema 3.
Se dă un număr natural
n
de maxim8
cifre. Să se afișeze de câte ori apare fiecare cifră în acesta.
Citim numărul, îi eliminăm pe rând ultima cifră și actualizăm cu ajutorul ei vectorul de frecvență. La final afișăm elementele vectorului.
#include <iostream>
using namespace std;
int n;
int frq[10];
int main() {
cin >> n;
do {
frq[n % 10]++;
n /= 10;
} while (n);
for (int i = 0; i <= 9; i++)
cout << frq[i] << ' ';
cout << '\n';
return 0;
}
Doi algoritmi importanți ce se folosesc de vectori caracteristici și respectiv de vectori de frecvență sunt Ciurul lui Eratostene și Sortarea prin numărare. Puteți găsi exerciții ce se folosesc de aceste tipuri de vectori și pe PbInfo. Nu uitați să lăsați un comentariu dacă aveți vreo problemă cu vectori caracteristici sau vectori de frecvență pe care nu reușiți să o rezolvați
Bună seara,
Vă mai pot ruga cu o problemă cu limita de timp mică…?
Cu stimă,
Cristian
Bună seara. Desigur!
Mulțumesc frumos.
https://pastebin.com/xP8kWTcN
E un pic mai ciudat că iei time limit în loc de memory limit exceeded, pentru că problema e de la memorie. Asta e o altă problemă în care trebuie folosit un vector caracteristic pe biți.
https://pastebin.com/akD8s0LY
Mulțumesc frumos de răspuns.
Înseamnă că
vector<bool>
e mai „compact” decâtbool v[i]
…?În ce capitol afli despre
vector
…? Sper să nu vă deranjeze întrebarea asta? În definitiv există și Google… Eu sunt mai interesat de pașii de urmat… Până acum am parcurs algoritmii elementari, tablouri unidimensionale (mai am), ceva din funcții, operațiile pe biți și căutarea binară…Care ar fi următorul pas de urmat?
Cu stimă,
Cristian
Da,
vector<bool>
ocupă de8
ori mai puțină memorie decâtbool[]
, pentru că folosește un singur bit (în loc de byte) pentru fiecare valoare. Ca să poată face asta, implementarea sa folosește operații pe biți, cum am arătat și în articolul respectiv.Clasa
vector
face parte din biblioteca STL (Standard Template Library); până acolo mai ai multe de parcurs… Ce zici să continui cu niște algoritmi de sortare?Bună dimineața,
Dacă nu abuzez de timpul dvs… Aș putea să vă mai trimit o problemă…?
Pe cealaltă am rezolvat-o…
Mulțumesc anticipat.
Cu stimă,
Cristian
Bună dimineața, da, mă puteți întreba.
Vă salut,
Dacă nu abuzez de timpul și bunăvoința dvs… Și luându-mă după textul de pe site, vă rog să mă ajutați cu următoarea problemă.
„Nu uitați să lăsați un comentariu dacă aveți vreo problemă cu vectori caracteristici sau vectori de frecvență pe care nu reușiți să o rezolvați
”
Problema #529 Cifre4 de pe PbInfo…
https://pastebin.com/LkzqpGAR
Construiești vectorul
c
greșit. Tu ar trebui să-l parcurgi peb
din2
în2
, și să bagi înc
cifra (b[i - 1]
), nu frecvența (b[i]
). Problema la codul tău apare când cifra0
are o frecvență nenulă, pentru că vei ieși dinwhile
prea devreme. Desigur, dacă faci cum am zis, pec
o să-l parcurgi din1
în1
. În plus, ar mai apărea o problemă atunci când unul dintre numerele citite este0
, pentru că n-o să se actualizeze frecvența cifrei0
. Cel mai ușor mod de a rezolva asta este să înlocuieștiwhile
-ul cudo while
. Dar se pare că printre testele de pe PbInfo nu apare cazul ăsta, sau cel puțin netratarea lui se întâmplă să nu afecteze răspunsul.Oricum, te-ai cam complicat ținând cifrele și frecvențele pe poziții pare și impare. Când mai ai de sortat vectori ale căror elemente sunt perechi de numere, poți să ții într-un vector
a
primul element din pereche, iar înb
pe cel de-al doilea. Sau, cel mai bine, faci unstruct
cu două câmpuri și sortezi un vector de structuri.Bună dimineața,
Mulțumesc frumos pentru răspuns.
O zi bună.
Nu prea am înțeles…
Să o luăm simplu…
La problema 3 de la vectori de frecvență… cu un număr natural de maxim
8
cifre…int frq[10]
… Asta înseamnă un vector de10
poziții fiecare având valoarea0
… Probabil la fel de bine pot scriev[10]
,q[10]
etc…Apoi intru în
main
.frq[n % 10]++
…? Ce înseamnă asta? Răspuns posibil: Că vectoruluifrq
care pe poziția1
a luifrq
care corespunde ultimei cifre a numărului inițialn
, de exemplu3
… va lua valoarea1
(Adică era0
și acum ia valoarea1
… Asta înseamnă++
)…? ș.a.m.d… Și obțin ce…? Și dacă mai găsește o dată3
(n % 10
), cum știe să-l așeze pe poziția1
…?Ce se întâmplă exact?
Rog să scuzați necunoașterea mea și să-mi explicați mecanismul. Mecanismul există sigur, eu nu-l pot interpreta în scrierea lui formală…
Cu stimă, Cristian.
Felicitări pentru acest site.
Toate cele bune!
Salut!
Instrucțiunea
frq[n % 10]++
funcționează așa:n % 10
calculează ultima cifră a luin
,frq[n % 10]
accesează poziția din vectorulfrq
corespunzătoare ultimei cifre a luin
(de exemplu, dacă ultima cifră a luin
este3
, atuncifrq[n % 10]
se va referi lafrq[3]
), iar++
incrementează valoarea din vector de pe poziția respectivă. Astfel, la final, înfrq[i]
vei avea frecvența cifreii
în număruln
(de câte ori aparei
înn
). De asta se și cheamă vector de frecvență.Sper că acum ai înțeles!
Am găsit răspunsul: Pe poziția
i
este stocată o informație despre număruli
. Asta înseamnă că dacă vreau să analizez un vector de10
elemente, dar măcar unul dintre elemente are o valoare de3
cifre, trebuie să fac un vector de frecvență de1000
elemente…1000 > 999
… Așa este? Mulțumesc…Dacă am înțeles bine întrebarea, da. Nu contează câte numere introduci în vectorul de frecvență, ci cât de mari sunt numerele respective.
Mulțumesc frumos pentru răspunsuri…
Sunt la începutul procesului de înțelegere…
You’re welcome