Vectori caracteristici. Vectori de frecvență

de Gareth618 | 11/05/2018 | Algoritmică și structuri de date | 17 comentarii

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 și 1000. Pentru fiecare dintre următoarele q 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;
}

#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;
}

#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;
}

#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 maxim 8 cifre. Să se afișeze cel mai mic și cel mai mare număr de 3 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;
}

#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 maxim 3 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;
}

#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 maxim 3 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;
}

#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;
}

#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 maxim 8 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;
}

#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 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație!

Similare

17 Comentarii

Prisecariu Cristian pe 06/05/2020 la 18:05

Bună seara,
Vă mai pot ruga cu o problemă cu limita de timp mică…?

Cu stimă,
Cristian
Răspuns
- Gareth618 pe 06/05/2020 la 18:56
  
  Bună seara. Desigur!
- Prisecariu Cristian pe 07/05/2020 la 08:39
  
  Mulțumesc frumos.
  https://pastebin.com/xP8kWTcN
- Gareth618 pe 07/05/2020 la 11:45
  
  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
- Prisecariu Cristian pe 07/05/2020 la 13:13
  
  Mulțumesc frumos de răspuns.
  Înseamnă că vector<bool> e mai „compact” decât bool 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
- Gareth618 pe 08/05/2020 la 13:14
  
  Da, vector<bool> ocupă de 8 ori mai puțină memorie decât bool[], 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?
Prisecariu Cristian pe 13/04/2020 la 09:20

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
Răspuns
- Gareth618 pe 13/04/2020 la 15:03
  
  Bună dimineața, da, mă puteți întreba.
Prisecariu Cristian pe 09/04/2020 la 15:21

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
Răspuns
- Gareth618 pe 09/04/2020 la 21:15
  
  Construiești vectorul c greșit. Tu ar trebui să-l parcurgi pe b din 2 în 2, și să bagi în c cifra (b[i - 1]), nu frecvența (b[i]). Problema la codul tău apare când cifra 0 are o frecvență nenulă, pentru că vei ieși din while prea devreme. Desigur, dacă faci cum am zis, pe c o să-l parcurgi din 1 în 1. În plus, ar mai apărea o problemă atunci când unul dintre numerele citite este 0, pentru că n-o să se actualizeze frecvența cifrei 0. Cel mai ușor mod de a rezolva asta este să înlocuiești while-ul cu do 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 în b pe cel de-al doilea. Sau, cel mai bine, faci un struct cu două câmpuri și sortezi un vector de structuri.
- Prisecariu Cristian pe 10/04/2020 la 08:19
  
  Bună dimineața,
  Mulțumesc frumos pentru răspuns.
  O zi bună.
Prisecariu Cristian pe 07/04/2020 la 12:28

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 de 10 poziții fiecare având valoarea 0… Probabil la fel de bine pot scrie v[10], q[10] etc…

Apoi intru în main. frq[n % 10]++…? Ce înseamnă asta? Răspuns posibil: Că vectorului frq care pe poziția 1 a lui frq care corespunde ultimei cifre a numărului inițial n, de exemplu 3… va lua valoarea 1 (Adică era 0 și acum ia valoarea 1… 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ția 1…?

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!
Răspuns
- Gareth618 pe 07/04/2020 la 12:46
  
  Salut!
  Instrucțiunea frq[n % 10]++ funcționează așa: n % 10 calculează ultima cifră a lui n, frq[n % 10] accesează poziția din vectorul frq corespunzătoare ultimei cifre a lui n (de exemplu, dacă ultima cifră a lui n este 3, atunci frq[n % 10] se va referi la frq[3]), iar ++ incrementează valoarea din vector de pe poziția respectivă. Astfel, la final, în frq[i] vei avea frecvența cifrei i în numărul n (de câte ori apare i în n). De asta se și cheamă vector de frecvență.
  Sper că acum ai înțeles! 🙂
- Prisecariu Cristian pe 07/04/2020 la 13:29
  
  Am găsit răspunsul: Pe poziția i este stocată o informație despre numărul i. Asta înseamnă că dacă vreau să analizez un vector de 10 elemente, dar măcar unul dintre elemente are o valoare de 3 cifre, trebuie să fac un vector de frecvență de 1000 elemente… 1000 > 999… Așa este? Mulțumesc…
- Gareth618 pe 07/04/2020 la 21:04
  
  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.
- Prisecariu Cristian pe 07/04/2020 la 22:30
  
  Mulțumesc frumos pentru răspunsuri…
  Sunt la începutul procesului de înțelegere…
- Gareth618 pe 08/04/2020 la 01:03
  
  You’re welcome 🙂

Vectori caracteristici. Vectori de frecvență

Vectori caracteristici

Problema 1.

Problema 2.

Problema 3.

Vectori de frecvență

Problema 1.

Problema 2.

Problema 3.

Îți place conținutul acestui site?

Partajează asta:

Similare

17 Comentarii

Introdu Comentariu Anulează răspunsul