Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

1

Algoritmi cu vectori (continuare) R1. Enunul problemei: S se determine cte numere pozitive, negative, respectiv nule sunt ntr-un vector de n numere reale dat. Metoda de rezolvare: Algoritmul const n citirea dimensiunii vectorului i apoi a componentelor valorilor, dup care se analizeaz fiecare valoare a vectorului: dac este pozitiv aceasta se va contoriza la elementele pozitive, dac este negativ aceasta se va contoriza la elementele negative, respectiv dac este zero aceasta se va contoriza la elementele nule. Analiza componentelor se poate face dup ce se citesc efectiv toate elementele vectorului sau se poate face imediat dup citire evitndu-se astfel o a doua parcurgere a vectorului. Mai jos, n descrierea algoritmului n pseudocod analiza componentelor se face dupa citirea tuturor componentelor, dar n descrierea algoritmului n C++ analiza se face imediat dup citirea fiecrei componente. O descriere a algoritmului n pseudocod:

citete n,v1,...,vn *citim dimensiunea si elementele vectorului poz 0 *contorul numerelor pozitive se initializeaza cu 0 neg 0 *contorul numerelor pozitive se initializeaza cu 0 nule 0 *contorul zerourilor se initializeaza cu 0 pentru i = 1,n repeta *parcurgem vectorul daca vi > 0 atunci *daca curenta este pozitiva poz poz + 1 *se numara la contorul pozitivelor altfel *vi0

daca vi < 0 atunci *altfel daca curenta este pozitiva neg neg + 1 *se numara la contorul negativelor altfel

nule nule + 1 *se numara la contorul zerourilor scrie poz, neg, nule *se afiseaza valorile contoarelor O descriere a algoritmului n C++:

# include using namespace std; int main() { float v[20]; //disponibile: x[0], ..., x[19] int n,nule,neg,poz; //ocupate: x[0], ..., x[n-1] nule = poz = neg = 0; //initializam contoarele //datele de intrare = dimensiunea si elementele vectorului coutn; cout

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

2

R2.

Enunul problemei: Fie v = (v1, , vn). S se calculeze media vectorului =

=n

iivn 1

1m i

dispersia vectorului =

-=n

iivn 1

2)(1 ms . De exemplu, pentru v = (1 2 3 6):

= (1 +2+3+6) / 4 = 12 / 4 = 3, iar = ( )4

14)36()33()32()31(41 2222 =-+-+-+- = 3.5.

Metoda de rezolvare: Media vectorului reprezint chiar media aritmetic a componentelor vectorului (adic suma componentelor mprit la numrul componentelor) , iar dispersia reprezint de asemenea o sum mprit la numrul componentelor. nti calculm suma componentelor n variabila , apoi mprim rezultatul din la n i actualizm . Similar pentru , nti calculm suma ptratelor diferenei dintre valoarea curent i n variabila , apoi mprim rezultatul din la n i actualizm . O descriere a algoritmului n pseudocod:

citete n,v1,...,vn *citim dimensiunea si elementele vectorului 0 *media vectorului pentru i = 1,n repeta *parcurgem vectorul + vi *adaugam la miu componenta curenta / n *se imparte rezultatul la n

0 *dispersia vectorului pentru i = 1,n repeta *parcurgem vectorul + (vi-)2 *adaugam la miu componenta curenta / n *se imparte rezultatul la n scrie ,

O descriere a algoritmului n C++: # include # include using namespace std; int main() { int n,i; float v[15],miu,sigma; //se citesc dimensiunea si elementele vectorului coutn; cout

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

3

R3. Enunul problemei: Fie vectorii u = (u1, , un) i v = (v1, , vn). S se calculeze produsul scalar dintre cei doi vectori i normele ambilor vectori. De exemplu, pentru u = (-1 1 2 0) i v = (1 2 3 6), produsul scalar dintre cei doi vectori este < u, v > = (-1)1 + 12 + 23 + 06 = 7,

norma vectorului u este ||u|| = 2222 021)1( +++- = 6 ~ 2.45, norma vectorului v este

||v|| = 2222 6321 +++ = 50 ~7.07. Metoda de rezolvare: Pentru u = (u1, , un) i v = (v1, , vn):

- produsul scalar dintre cei doi vectori este ==

n

iiivu

1

- norma vectorului u este ||u|| = ( )=

n

iiu

1

2

- norma vectorului v este ||v|| = ( )=

n

iiv

1

2 .

Aadar, produsul scalar este o sum, iar normele pot fi vzute iniial ca fiind sumele de sub radicali, apoi se corecteaz prin calcularea radicalului din sumele calculate anterior. O descriere a algoritmului n pseudocod:

citete n,u1,...,un,v1,...,vn *am citit dimensiunea comuna si elementele celor 2 vectori ps 0 *media vectorului pentru i = 1,n repeta *parcurgem vectorul ps ps + uivi *adaugam la miu componenta curenta Nu 0 *norma vectorului u, initial 0 pentru i = 1,n repeta *parcurgem vectorul u Nu Nu + (ui)2 *se adauga patratul compon.curente Nu Nu *se corecteaza valoarea variabilei Nu Nv 0 *norma vectorului u, initial 0 pentru i = 1,n repeta *parcurgem vectorul u Nv Nv + (vi)2 *se adauga patratul compon.curente Nv Nv *se corecteaza valoarea variabilei Nv scrie ps, Nu, Nv

O descriere a algoritmului n C++:

# include # include # include using namespace std; int main() { int n,i; float u[20],v[20],ps=0,Nu=0,Nv=0; //se citesc dimensiunea comuna si elementele vectorilor coutn; cout

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

4

for (i=0;i

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

5

v[2] = 2 v[3] = 3 v[4] = 6 Produsul scalar dintre u si v = 7 Norma vectorului u = 2.45 Norma vectorului v = 7.07

R3. Enunul problemei: S se inverseze ordinea elementelor unui vector. De exemplu, pentru v = (1 2 3 4 5) => v = (5 4 3 2 1) Metoda de rezolvare: Pentru c se dorete inversarea efectiv a ordinii elementelor, nu doar afiarea (cnd se putea parcurge vectorul de la final spre sfrit), putem parcurge elementele pn la jumtatea vectorului i s interschimbm elementul curent cu simetricul su fa de jumtatea vectorului: pentru un vector memorat ca n C/C++ v[0],...,v[n-1], acest lucru presupune parcurgerea cu i=0,1,...,[n/2]-1 i interschimbarea componentelor v[i] i v[n-1-i] (acesta se poate realiza prin intermediul unei variabile auxiliare de acelai tip cu elementele vectorului: aux = v[i]; v[i] = v[n-1-i]; v[n-1-i] = aux;). O descriere a algoritmului n C++:

# include using namespace std; int main() { float v[20]; int n,i; //se citesc dimensiunea si elementele vectorului coutn; cout

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

6

R4. Scriei un algoritm pentru a stabili dac un vector de numere reale este cresctor (vi vi+1, pentru orice i = 1,, n-1) sau nu. Metoda de rezolvare: O metod de descriere a algortitmului ar fi aceea n care la nceput se presupune c vectorul v = (v1, v2, , vn) este cresctor, apoi se parcurge vectorul cu i = 1,, n-1 i n cazul n care vi / vi+1, atunci nu este cresctor. n C/C++ apare decalajul de indici: pentru vectorul v[0], , v[n-1], se parcurge vectorul cu i=0,,n-2 i n cazul n care dou componente vecine nu sunt corespunztoare, adic v[i] > v[i+1], atunci nu este cresctor (pentru aceasta putem folosi o variabil care va avea valoarea 1 n cazul n care vectorul este cresctor i valoarea 0 n cazul n care vectorul nu este cresctor). O descriere a algoritmului n pseudocod:

citete n,v1,...,vn *citim dimensiunea si elementele vectorului crescator adevarat *presupunem ca vect. este crescator pentru i = 1,n-1 repeta *parcurgem vectorul daca v[i]>v[i+1] atunci *daca doua elemente vecine

crescator fals *atunci vectorul nu este crescator daca crescator = adevarat atunci *testam valoarea finala

scrie "Este vector crescator" altfel

scrie "Nu este vector crescator" O descriere a algoritmului n C++:

#include using namespace std; int main() { float v[20]; int n,i,crescator; coutn; cout

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

7

int main() { float v[20]; int n,i; coutn; cout

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

8

R5. Scriei un algoritm pentru a stabili dac un vector de numere reale are componentele n progresie aritmetic sau nu. Metoda de rezolvare: Un vector v = (v1, v2, , vn) are elementele n progresia aritmetic dac

(2

11 +- += iiivvv pentru orice i = 2,, n-1 acele elemente care au vecini n stnga i n

dreapta). O metod de descriere a algoritmului ar fi aceea n care la nceput se presupune c vectorul v = (v1, v2, , vn) are elementele n progresie aritmetic, apoi se parcurge vectorul cu

i = 2,, n-1 i n cazul n care 2

11 +- +=/ iiivvv , atunci nu are elemntele n progresie

aritmetic. n C/C++ apare decalajul de indici: pentru vectorul v[0], , v[n-1], se parcurge vectorul cu i=1,,n-2 i n cazul n care v[i] !=(v[i-1]+v[i+1])/2, atunci vectorul nu are elementele n proresie aritmetic (pentru aceasta putem folosi o variabil care va avea valoarea 1 n cazul n care vectorul are elementele n progresie aritmetic i valoarea 0 n cazul n care vectorul nu are elementele n progresie aritmetic).

#include using namespace std; int main() { int n,i,p_a; float v[20]; coutn; cout

Algoritmi si structuri de date (19-20.11.2014) Informatica&Matematic, anul 1 ASD17AlgVectLab

9

sau folosind funcii #include using namespace std; int EsteProgresieAritmetica(float v[20], int n) { for (int i=1; i