Laborator 4: Tablouri. Particularizare - vectori și matrici

Obiectivele laboratorului:

În acest laborator vom studia:

tablouri in C - particularizare vectori și matrici
(alocare statică): declarare, reprezentare în memorie, inițializare, citire/afișare
algoritmi de bază pe vectori: parcurgeri, căutare liniară, sortare, cautare binară
algoritmi de bază pe matrici: parcurgeri, operații matriciale (adunare, scădere, înmultire, putere, transpusă)

De asemenea, vom exersa lucrul cu funcții. Vom încerca să modularizăm cât mai fin astfel să avem câte o funcție pentru fiecare operație.

HINT: Gândiți-vă cum organizați codul, astfel încât să reutilizați funcțiile implementate la exercițiile anterioare.

Materiale utile

Exerciții

a. Realizați o funcție care primește ca parametru un vector v. Funcția va citi de la tastatură numărul de elemente și elementele. Elementele vor fi salvate în vector și va întoarce numărul de elemente.

b. Realizati o funcție care primește ca parametru un număr întreg n și un vector v. Funcția va afișa pe ecran pe o singura linie toate elementele vectorului (despărțite prin spațiu).

int v[NMAX];
int n = read_array(v);      // userul introduce numărul 5
                            // apoi 5 elemente - spre exemplu 10 30 -1 4 5
                            // functia returneaza cate elemente a citit
                            // elementele citite se salvează în vectorul v
print_array(n, v);          // va afisa pe ecran fix linia "10 30 -1 4 5\n"

Realizați câte o funcție pentru fiecare din următoarele cerințe. Exemplele date se vor referi la vectorul cu elementele din exemplul de la exercițiul 1(n = 5, v = {10,30, -1, 4, 5}).

a. Calcularea sumei elementelor dintr-un vector v cu n elemente
```
int sum = sum_array(n, v); // sum = 48, pentru ca 10 + 30 - 1 + 4 + 5 = 48
```
b. Determinarea elementului minim dintr-un vector v cu n elemente
```
int min = min_array(n, v); // min == -1, pentru ca -1 e cel mai mic element
```
c. Poziția elementului maxim dintr-un vector v cu n elemente. Dacă elementul apare de mai multe ori, se va alege prima poziție a acestuia.
```
int posmax = posmax_array(n, v); // posmax == 1, pentru ca 30 e cel mai mare element
```
d. Calcularea mediei aritmetice a elementelor dintr-un vector cu n elemente

HINT: Ce funcție deja implementată e utilă? (Modularizare & reutilizare)
```
double avg = avg_array(n, v); // avg = 9.6
```
e. Găsirea unui element într-un vector v cu n elemente. Se va căuta liniar de la stanga la dreapta pentru prima apariție a elementului x în vector. Se va returna poziția lui dacă exista (număr între 0 și n - 1) sau -1 dacă elementul nu exista în șir.
```
int pos = find_array(n, v, 30) ; // pos == 1 (v[1] == 30)
int pos = find_array(n, v, 4) ;  // pos == 3 (v[3] == 4)
int pos = find_array(n, v, 13) ; // pos == -1 (elementul nu exista in sir)
```

Implementați și testați algoritmul de sortare selection sort.

sort_array(n, v);
print_array(n, v); // va afisa "-1 4 5 10 30"

Scrieți o funcție care să înmulțească 2 matrice a și b (dimensiuni n, m, p). Rezultatul se va stoca în matricea c, care are dimensiunile n x p.

void multiply_matrix(int n, int m, int p, int a[NMAX][NMAX],
    int b[NMAX][NMAX], int c[NMAX][NMAX]);

Atenție! a, b, c pot reprezenta în memorie aceeași matrice:

multiply_matrix(n, n, n, a, a, a);

Exemplu:

int a[NMAX][NMAX] = {
    { 0,  1,  1,  1},
    { 1,  1,  1,  1},
    { 0, 10,  0,  0},
    { 0, 10,  0,  0}
};

int b[NMAX][NMAX] = {
    { -1, 10,  1},
    { -2, 20,  2},
    { -3, 30,  3},
    { -4, 40,  4}
};

A * B =
-9        90         9
-10       100        10
-20       200        20
-20       200        20

[BONUS] Folosind funcția de la exercițiul anterior, să se scrie o funcție care ridica o matrice pătratică a (n x n) la puterea k, rezultatul fiind stocat în matricea b.

void power_matrix(int n, int a[NMAX][NMAX], int k, int b[NMAX][NMAX]);

Atenție! a, b pot reprezenta în memorie aceeași matrice:

void multiply_matrix(n, n, n, a, a);

Exemplu:

int n = 4;
int a[NMAX][NMAX] = {
    { 0,  1,  1,  1},
    { 1,  1,  1,  1},
    { 0, 10,  0,  0},
    { 0, 10,  0,  0}
};

a^2 =
n = 4, m = 4:
        1        21         1         1
        1        22         2         2
        10       10        10        10
        10       10        10        10

a^10 =
n = 4, m = 4:
1923434  11014355   2298075   2298075
2298075  12937789   2733889   2733889
4358140  22980750   5101950   5101950
4358140  22980750   5101950   5101950