RSS

Vectori de frecventa

13 Jan

Vectori de frecventa

Utilizarea unui vector de frecventa este oportuna cand trebuie sortate (crescator/descrescator) valori din domenii inguste (litere, numere de cateva cifre:1,2,3,4).

Metoda presupune numararea (stabilirea frecventei) fiecarei valori in parte.

Studiu de caz:

Fişierul text NR.TXT conţine pe o singură linie, separate prin câte un singur spaţiu, cel mult 100 de numere naturale, fiecare număr având cel mult 4 cifre. Scrieţi un program C/C++ care citeşte numerele din fişierul NR.TXT şi afişează pe ecran, separate prin câte un spaţiu, în ordine descrescătoare, toate numerele din fişier care au cel mult 2 cifre. Dacă fişierul nu conţine astfel de numere se va afişa pe ecran mesajul NU EXISTA.

Varianta 1. Ordonare

int nv=0, vf[101],x;
//adaug in vector orice valoare care respecta conditiile
while (fin>>x) if (x<100) {nv++; v[nv]=x;} 

if (nv==0) fout>>"NU EXISTA";
else {sortare (v,nv;); afisare_desc (v,nv);}

Complexitatea algoritmului este data de sortare. Probabil cea mai buna varianta pe care o folosit este O(n^2). Daca toate cele 100 numere se califica, ajungem la o complexitate de 10000 de operatii.

Varianta 2. Vector de frecventa

int vf[100], x;
//marchez aparitia fiecarei valori de maxim 2 cifre
while (fin>>x) if (x<100) vf[x]++; 

for(x=99;x>=0;x--) //am in vedere valorile de la 99..0
for(k=1;k<=vf[x];k++) //de vf[x] ori , adica de numarul de aparitii a lui X ori
      fout<<x;  //afisez X

Presupunand ca sunt n valori (maxim 100), complexitatea algoritmului este 100+n=200 , adica O(n) operatii.

 

 

 

 
Leave a comment

Posted by on 13/01/2017 in C2_2 Limbajul C/C++

 

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: