Page 28 - MATINF Nr.2

˘
ARTICOLE SI NOTE DE INFORMATICA
,

Vectori de frecvente
,

Ion Alexandru Popescu 1

Acest articol ˆıs , i propune s˘a prezinte o not , iune important˘a ˆın programarea clasic˘a numit˘a
vector de frecvent , e s , i s˘a ofere cˆateva aplicat , ii ce pot fi considerate ,,clasice”, iar ˆın partea final˘a
s˘a dea s , ansa cititorului de a utiliza cele prezentate pentru rezolvarea unor probleme date la
examenul de bacalaureat ˆın ultima perioad˘a.

Notiuni preliminarii
,

Definit , ia 1. Fie Max s , i n dou˘a numere naturale, Max ≤ 1000, n ≤ 1000000 s , i M =
{0, 1, 2, . . . , Max}. Prin vector de dimensiune n cu elemente ˆın mult , imea M ˆınt , elegem un
element x din M × M × . . . × M. Produsul cartezian are n mult , imi.

Exemplul 1. Pentru Max = 10, n = 5, un exemplu de vector de dimensiune 5 este x =
(1, 6, 0, 9, 6).
ˆ
Observat ,ia 1. In continuare tot , i vectorii vor fi considerat , i cu elemente ˆın mult , imea M =
{0, 1, 2, . . . , Max}, Max fiind num˘ar natural fixat, Max ≤ 1000.

Definit , ia 2. Fie x un vector de dimensiune n cu elemente ˆın M. Definim vectorul de frecvent , e
asociat lui x ca fiind vectorul f x = (f x [0], f x [1], . . . , f x [Max]), unde f x [i] = num˘arul de compo-
nente din x egale cu i, 0 ≤ i ≤ Max.

Exemplul 2. Pentru Max = 6, n = 8, x = (1, 4, 0, 4, 5, 2, 5, 5) vectorul de frecvent , e este
f x = (1, 1, 1, 0, 2, 3, 0).

Definit , ia 3. Fie x s , i y doi vectori de dimensiuni m, respectiv n cu elemente ˆın M. Dac˘a
m = n s , i x[i] = y[i], pentru orice i, 1 ≤ i ≤ n, atunci x s , i y sunt egali (x = y).

Propozit , ia 1. Fie x un vector de dimensiune n cu elemente ˆın M. x reprezint˘a o mult , ime
dac˘a s , i numai dac˘a f x cont , ine numai elemente de 0 s , i 1.

Demonstrat¸ie. Vectorul x reprezint˘a o mult , ime dac˘a s , i numai dac˘a componentele sale sunt
distincte, proprietate echivalent˘a cu: frecvent , a fiec˘arei componente egal˘a cu 1. Dac˘a un num˘ar
din M nu este ˆın x, atunci are frecvent , a egal˘a cu 0 s , i astfel proprozit , ia este demonstrat˘a.

Propozit , ia 2. Fie x s , i y doi vectori de dimensiune n cu elemente ˆın M. x s , i y cont , in aceleas , i
elemente, eventual ˆın alt˘a ordine, dac˘a s , i numai dac˘a f x = f y .
1
Student, Universitatea din Pites , ti s , i A.S.E. Bucures , ti, alexionpopescu@gmail.com

28