Page 29 - MATINF Nr.2

Vectori de frecvent , e 29

Demonstrat¸ie. Demonstrat , ia este imediat˘a, pentru c˘a ordinea elementelor ˆıntr-un vector nu
afecteaz˘a vectorul de frecvent , e.

Propozit , ia 3. Fie x un vector de dimensiune n cu elemente ˆın M. Num˘arul de componente
distincte din x este egal cu card{i|i ∈ M s , i f x [i] > 0}.

Demonstrat¸ie. Num˘arul de componente distincte din x este egal cu num˘arul de elemente k din
M care se g˘asesc ˆın x, lucru echivalent cu f x [k] > 0, astfel rezult˘a afirmat , ia din propozit , ie.

Observat ,ia 2. Dac˘a pentru un vector x, ˆın loc de frecvent , a de aparit , ie a lui i ˆın x (0 ≤ i ≤ Max),
ret , inem pentru f x [i] valoarea 1 dac˘a i este ˆın x s , i 0, ˆın caz contrar, atunci f x se va numi vectorul
caracteristic asociat lui x.

Exemplul 3. Pentru Max = 6, n = 8, x = (1, 4, 0, 4, 5, 2, 5, 5) vectorul caracteristic asociat lui x
este f x = (1, 1, 1, 0, 1, 1, 0).

Observat ,ia 3. Vectorii caracteristici pot fi folosit , i pentru memorarea mult , imilor s , i efectuarea
operat , iilor specifice, obt , inˆand astfel algoritmi eficient , i.

Tipuri standard de probleme ce pot fi rezolvate cu vectori de frecvent˘a
,

1. Ordonarea unui vector

Se d˘a n s , i componentele unui vector x, valori mai mici sau egale cu 1000. Se cere s˘a se
afis , eze componentele vectorului x ˆın ordine cresc˘atoare.

Exemplu
Intrare

7

3 12 4 3 9 3 9

Ies , ire
3 3 3 4 9 9 12

Solut , ie

I. Max = 0

II. Citim n s , i componentele vectorului ˆın variabila k. Pentru fiecare k actualiz˘am Max (cea
mai mare component˘a din x) s , i f x [k] = f x [k]+1. Astfel x are elementele ˆın M = {0, 1, . . . , Max}
s , i f x este vectorul de frecvent , e.

III. Afis , ˘am componentele lui x ordonate cresc˘ator folosind vectorul de frecvent , e f x , astfel:
pentru orice k din mult , imea M, afis , ˘am k de f x [k] ori.
Pentru exemplul considerat: Max = 12, f x [3] = 3, f x [4] = 1, f x [9] = 2, f x [12] = 1, iar
celelalte componente ale lui f x sunt 0. Se va afis , a 3 de 3 ori, 4 o dat˘a, 9 de dou˘a ori s , i 12 o dat˘a.

2. Determinarea componentelor distincte dintr-un vector

Se d˘a n s , i componentele unui vector x, valori mai mici sau egale cu 1000. Se cere s˘a se
afis , eze componentele distincte din x ˆın ordine cresc˘atoare.