ALGORITMI PENTRU TABLOURI UNIDIMENSIONALE (VECTORI)
Declararea unui vector:
int v[101]; // vector cu maxim 100 de elemente numere intregi (numerotate 1..100);
vector cu maxim 101 de elemente numere intregi (numerotate 0..100);
float u[51];
Citirea unui vector
cin>>n;
for (i=1;i<=n;i++)
cin>>v[i];
// v[i]=elementul vectorului; i=pozitia sau indicele sau numarul de ordine pentru
elementul v[i] al vectorului
Afisarea unui vector
for (i=1;i<=n;i++)
cout<<v[i]<<' ';
Prelucrarea elementelor unui vector
for (i=1;i<=n;i++)
prelucrarea lui v[i];
1. Cautarea secventiala (se citesc un vector v, cu n elemente, si un numar x; sa se
afiseze mesajul "da", daca x exista in vector, "nu" in caz contrar)
ok=0; //pp ca x nu exista in vector
for (i=1;i<=n;i++)
if (v[i]==x)
ok=1;
if (ok)
cout<<"da";
else
cout<<"nu";
2. Cautarea binara (se citesc un vector v, ordonat crescator, cu n elemente, si un
numar x; sa se afiseze mesajul "da", daca x exista in vector, "nu" in caz contrar)
- algoritm eficient - complexitate O(log n)
1 2 3 4 5 6 7 8
n=8 v={2,4,7,9,11,12,15,23} x=11 => da
i=1 5
j=8 5
m=4 6 5
n=8 v={2,4,7,9,11,12,15,23} x=10 => nu
i=1 5
j=8 5 4
m=4 6 5
i=1;
j=n;
ok=0;
while (i<=j && ok==0)
{
m=(i+j)/2;
if (v[m]==x) ok=1;
else if (v[m]<x) i=m+1;
else j=m-1;
}
if (ok)
cout<<"da";
else
cout<<"nu";
Obs. In cazul in care vectorul este ordonat descrescator:
if (v[m]>x) i=m+1;
else j=m-1;
3. Sortarea crescatoare a elementelor unui vector - sortarea prin interschimbare
(selectie directa)
n=6 v={3,1,9,4,2,1}
i=1 v={1,3,9,4,2,1}
i=2 v={1,1,9,4,3,2}
i=3 v={1,1,2,9,4,3}...
se compara fiecare element cu toate elementele aflate dupa el in vector; in cazul
in care nu sunt asezate corespunzator, se interschimba
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if (v[i]>v[j])
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
Obs. Pentru sortarea descrescatoare: if (v[i]<v[j])
Complexitate: O(n*n)
Numarul de pasi: n*(n-1)/2
4. Sortarea crescatoare a elementelor unui vector - sortarea prin metoda bulelor
n=6 v={3,1,9,4,2,1}
i=1 v={1,3,4,2,1,9}
i=2 v={1,3,2,1,4,9}
i=3 v={1,2,1,3,4,9}
i=4 v={1,1,2,3,4,9}
i=5 v={1,1,2,3,4,9}
se compara elementele consecutive ca pozitie in vector si se interschimba daca este
cazul; se repeta aceasta operatie de parcurgere a vectorului, pana cand, la o
parcurgere, nu mai are loc nicio interschimbare
do
{
ok=1; //pp ca vectorul este ordonat
for (i=1;i<n;i++)
if (v[i]>v[i+1])
{
aux=v[i];
v[i]=v[i+1];
v[i+1]=aux;
ok=0; //daca am facut o interschimbare, vectorul nu era ordonat
}
}
while (ok==0);
4*. Sortarea prin selectie (la fiecare pas i al algoritmului se determina minimul
din elementele inca nesortate si se interschimba cu elementul de pe pozitia i)
n=6 v={3,1,9,4,2,1}
n=6 v={1,3,9,4,2,1}
n=6 v={1,1,9,4,2,3}
n=6 v={1,1,2,4,9,3}
n=6 v={1,1,2,3,9,4}
n=6 v={1,1,2,3,4,9}
for (i=1;i<n;i++)
{
mn=v[i]; poz=i;
for (j=i+1;j<=n;j++)
if (v[j]<mn)
{
mn=v[j];
poz=j;
}
aux=v[poz]; v[poz]=v[i]; v[i]=aux;
}
4**. Sortarea prin numarare
n=6 v={3,1,9,4,2,1}
nr={3,0,5,4,2,1}
b={1 1 2 3 4 9}
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if (v[i]>v[j])
nr[i]++;
else
nr[j]++;
for (i=1;i<=n;i++)
b[nr[i]+1]=v[i];
4***.Sortarea prin insertie
n=6 v={3,1,9,4,2,1}
a={1,1,2,3,4,9}
a[1]=v[1];
for (i=2;i<=n;i++)
{
j=1;
while (v[i]>a[j])
j++;
for (k=i-1;k>=j;k--)
a[k+1]=a[k];
a[j]=v[i];
}
5. Sortarea prin interclasare (se citesc doi vectori ordonati crescator, a cu n
elemente si b cu m elemente; sa se construiasca al treilea vector c, care sa
contina elementele din vectorii dati, de asemenea ordonate crescator) -
complexitate O(n+m)
n=5 a={3,5,8,9,12}
m=7 b={1,2,4,5,6,7,7}
i=1 2 3
j=1 2 3 4 5..8
k=0 1 2 3 4 5 6
c={1,2,3,4,5,5,6,7,7,8,9,12}
i=1; //parcurge vectorul a
j=1; //parcurge vectorul b
k=0; //memoreaza cate elemente am adaugat in vectorul c
while (i<=n && j<=m)
if (a[i]<b[j])
{
k++; c[k]=a[i];
i++;
}
else if (a[i]>b[j])
{
k++; c[k]=b[j];
j++;
} else {....i++;j++;}
if (j>m)
for (q=i;q<=n;q++)
{
k++; c[k]=a[q];
}
if (i>n)
for (q=j;q<=m;q++)
{
k++; c[k]=b[q];
}
6. Prelucrarea perechilor de elemente din vector
a) v[i], v[j] / 1<=i<j<=n (v[i] este pus in pereche cu oricare dintre v[j], aflate
dupa el (ca pozitie) in vector)
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
// prelucrarea perechii v[i], v[j]
v={1,1,2,9,4,3} n=6
(1,1) (1,2) (1,9) (1,4) (1,3) (1,2) (1,9)... (4,3) nr perechi: (n-1)+(n-
2)+...+1 = n*(n-1)/2
b) v[i], v[i+1] / 1<=i<n (perechi de elemente consecutive ca pozitie in vector)
for (i=1;i<n;i++)
//prelucrarea perechii v[i], v[i+1]
v={1,1,2,9,4,3}
(1,1) (1,2) (2,9) (9,4) (4,3) nr perechi: n-1 perechi
fara vector:
cin>>n>>a;
for (i=2;i<=n;i++)
{
cin>>b;
//prelucrarea perechii (a,b)
a=b;
}
c) v[i], v[j] egal departate de mijlocul vectorului (sau de capete)
v={1,1,2,9,4,3}
1 2 3 4 5 6 numarul de perechi este n/2
(1,3) (1,4) (2,9)
*
for (i=1;i<=n/2;i++)
//prelucrarea perechii v[i], v[n-i+1]
i=1 => n
i=2 => n-1
**
i=1; j=n;
while (i<j)
{
//prelucrarea perechii v[i], v[j]
i++; j--;
}
7. a) STERGEREA UNUI ELEMENT DE PE POZITIA k A UNUI VECTOR (1<=k<=n)
Ex. n=6 v={2,1,9,6,3,7} k=3
1 2 3 4 5 6
k k+1..n
for (i=k+1;i<=n;i++)
v[i-1]=v[i];
n--;
b) STERGEREA TUTUROR ELEMENTELOR CARE AU O PROPRIETATE (STERGEREA MULTIPLA)
Ex. n=6 v={2,1,4,6,3,7} => k=1 v={1,4,6,3,7} n=5 => k=2 v={1,6,3,7} n=4 => k=2
v={1,3,7} n=3 =>...
k=1;
while (k<=n)
{
testarea proprietatii lui v[k];
if (v[k] are proprietatea)
{
for (i=k+1;i<=n;i++)
v[i-1]=v[i];
n--;
}
else k++;
}
8. a) INSERAREA UNUI ELEMENT PE POZITIA k A UNUI VECTOR (1<=k<=n)
Ex. n=6 v={2,1,9,6,3,7} k=3
for (i=n;i>=k;i--)
v[i+1]=v[i];
n++; cin>>v[k];
b) INSERAREA A CATE UNUI ELEMENT DUPA FIECARE ELEMENT CARE ARE O PROPRIETATE
(INSERAREA MULTIPLA)
Ex. n=6 v={2,1,4,6,3,7} => k=1 v={2,x,1,4,6,3,7} n=7
k=1;
while (k<=n)
{
testarea proprietatii lui v[k];
if (v[k] are proprietatea)
{
for (i=n;i>=k+1;i--)
v[i+1]=v[i];
n++; cin>>v[k+1];
k=k+2;
}
else k++;