Informatica - Algoritmi fundamentali cu vectori

 

Informatica

Algoritmi fundamentali cu vectori

1. Calcule

intreg s←0, v[500], i, n, kneg←0, kpoz←0, knul←0, ma←0;

citeste n;

pentru (i←1,n)

citeste v[i];

pentru (i←1,n)

scrie s;

pentru (i←1,n)

pentru (i←1,n)

pentru (i←1,n)

pentru (i←1,n)

scrie kneg, knul, kpoz;

pentru (i←1,n)

scrie ma/2;

2. Determinarea maximului/minimului

intreg v[100], max, min;

citeste n;

pentru (i←1,n)

citeste v[i];

max←min←v[i];

pentru (i←1,n)

scrie max, min;

*Se considera primul element ca fiind max/min. Se parcurge vectorul, daca v[i] este mai mic decat min, min ia valoarea lui v[i], iar daca v[i] este mai mare decat max, max ia valoarea lui v[i].

3. Ordonarea unui vector

Metoda I - sortarea prin interschimbare

pentru (i←1,n)

}}

*Fiecare element v[i] se compara cu toate elementele de dupa el. Daca intalnim un v[j] mai mic decat v[i], atunci cele doua valori isi schimba pozitiile intre ele.

Metoda II - Bubble Sort

repeta

}}

cat timp (g=0);

*Se compara v[i] cu v[i+1] si se schimba intre ele daca e cazul. La fiecare interschimbare o variabila de control devine 0 (g este initializat cu 1). Parcurgerea vectorului se reia cat timp au loc interschimbari.

Metoda III

pentru (i←1,n)

aux←a[i];

a[i]←a[p];

a[p]←aux;}

Metoda IV - Sortarea prin numarare

Pentru (i←1,n)

b[k+1]←a[i];}

*a este vector initial nesortat, b este vector ce va contine elementele din a sortate. Pentru fiecare element a[i] numaram cate elemente sunt mai mici ca el (k). Se claseaza a[i] pe pozitia k+1 in vectorul b.

4. Cautarea unui element intr-un vector

Metoda I - cautarea secventiala

k←0;

pentru (i←1,n)

daca (k=1) scrie "apartine";

altfel scrie "nu apartine";

*Se da un vector si se compara elementul x cu toate elementele acestuia. Daca x este egal cu unul sau mai multe elemente, k ia valoarea 1. Daca la sfarsit k are valoarea 1 atunci x se gaseste printre elementele vectorului.

Metoda II - Cautarea binara

Li←1; Ls←n;

mij Li+Ls) div 2;

cat timp (v[mij]!=x && Li<=Ls)

*Se compara x cu un element din mijlocul vectorului. Daca x este mai mare decat elementul din mijloc, cautarea se reia in a doua jumatate a vectorului, altfel, se reia din prima jumatate pana cand x va fi egal cu elementele din mijlocul vectorului in care s-a efectuat cautarea sau vectorul in care nu se gaseste nimic.

5. Interplasarea a doi vectori

i←j←k←1;

cat timp (i<=n && j<=m)

altfel

pentru (l←i,n)

c[k+1]←a[l];

pentru (l←j,n)

c[k+1]←b[l];

pentru (i←1,m)

scrie c[i];}

*Se compara a[i] cu b[j] si se trece in c elementul mai mic, avansandu-se in vectorul in care s-a trecut elementul. Procedeul continua pana unul din cei 2 vectori se termina.

6. Eliminarea si adaugarea unui element intr-un vector

a) Eliminarea

pentru (i←k,n-1)

v[i]←v[i+1];

n←n-1;

b) Adaugarea

pentru (i←n+1,k+1)

n++;

7. Operatii cu multimi date sub forma de vectori

x←1;

pentru (i←1,n)

8. Determinarea frecventei de aparitie a cifrelor intr-un vector

citeste n;

cat timp (n)

*Vom utiliza un vector f cu 10 componente corespondente cifrelor de la 0 la 9. Acest vector se initializeaza cu 0. Se parcurg cifrele lui n si pentru fiecare cifra determinata f[n] creste cu 1. Parcurgem vectorul f si pentru fiecare element nenul din el afisam indicele (cifra) si valoarea (frecventa cifrei).