Invatare Atomica

Operatii avansate cu matrice: inmultire, spirala, zone speciale, bordare

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei stapani cele patru operatii cu matrice care apar constant in subiectele de Bacalaureat la Informatica: identificarea zonelor delimitate de diagonale, inmultirea a doua matrice, parcurgerea in spirala si bordarea. Toate exemplele sunt scrise in C++, limbajul in care se sustine proba.

Dupa aceasta lectie vei putea:

  • Sa scrii conditia pe indici pentru orice zona a unei matrice patratice (diagonale, triunghiuri, zonele N, S, V, E)
  • Sa verifici cand se poate calcula produsul A*B si sa implementezi inmultirea in C++
  • Sa explici de ce inmultirea matricelor nu este comutativa si ce rol are matricea unitate
  • Sa calculezi A la puterea k prin inmultiri repetate, pornind de la matricea unitate
  • Sa parcurgi o matrice in spirala folosind cele patru margini (sus, jos, stanga, dreapta)
  • Sa bordezi o matrice cu un chenar si sa folosesti chenarul ca sa scapi de verificarile de margine

Incearca singur!

Provocare:

Ai matricea de mai jos. Porneste din coltul stanga-sus si mergi in spirala, in sensul acelor de ceasornic: intai tot randul de sus, apoi coloana din dreapta, apoi randul de jos invers, apoi coloana din stanga in sus — si tot asa, spre interior.

 1  2  3  4
 5  6  7  8
 9 10 11 12

Scrie ordinea completa a celor 12 numere.

💡 Indiciu

Dupa ce ai luat primul rand (1 2 3 4), randul acela nu mai exista: cobori pe ultima coloana de la 8 la 12, apoi mergi inapoi pe ultimul rand (11 10 9), apoi urci pe prima coloana (5). Ce a ramas nemarcat este un singur rand: 6 7.

Ordinea completa: 1 2 3 4 8 12 11 10 9 5 6 7.

1

1. Zone speciale intr-o matrice patratica

Intai exemplul: matricea de 5x5 cu numerele 1...25
       j=0  j=1  j=2  j=3  j=4
i=0  [  1    2    3    4    5 ]
i=1  [  6    7    8    9   10 ]
i=2  [ 11   12   13   14   15 ]
i=3  [ 16   17   18   19   20 ]
i=4  [ 21   22   23   24   25 ]

Diagonala principala: 1, 7, 13, 19, 25   (i creste odata cu j)
Diagonala secundara : 5, 9, 13, 17, 21   (cand i creste, j scade)
Pe diagonala principala linia si coloana sunt egale: i == j. Pe diagonala secundara suma indicilor este constanta: i + j == n - 1 (cu indici de la 0). Cele doua diagonale taie matricea in patru zone: nord (N), sud (S), vest (V) si est (E).
Conditia fiecarei zone — tabelul pe care il inveti pentru Bac
Diagonala principala .... i == j
Diagonala secundara ..... i + j == n - 1
Triunghi deasupra dp .... i < j
Triunghi dedesubt dp .... i > j

Zona N (sus)  .... i < j  si  i + j < n - 1
Zona S (jos)  .... i > j  si  i + j > n - 1
Zona V (stanga) .. i > j  si  i + j < n - 1
Zona E (dreapta) . i < j  si  i + j > n - 1

Fiecare zona este intersectia a doua conditii: una data de diagonala principala, cealalta de diagonala secundara. Elementele de pe diagonale nu apartin niciunei zone.

Cod C++ — sumele pe zone
#include <iostream>
using namespace std;
int main() {
    int n = 5, a[5][5];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            a[i][j] = i * n + j + 1;

    int dp = 0, ds = 0, sus = 0, jos = 0;
    int nord = 0, sud = 0, vest = 0, est = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (i == j) dp += a[i][j];
            if (i + j == n - 1) ds += a[i][j];
            if (i < j) sus += a[i][j];
            if (i > j) jos += a[i][j];
            if (i < j && i + j < n - 1) nord += a[i][j];
            if (i > j && i + j > n - 1) sud  += a[i][j];
            if (i > j && i + j < n - 1) vest += a[i][j];
            if (i < j && i + j > n - 1) est  += a[i][j];
        }
    cout << "diagonala principala = " << dp << endl;
    cout << "diagonala secundara  = " << ds << endl;
    cout << "triunghi de sus      = " << sus << endl;
    cout << "triunghi de jos      = " << jos << endl;
    cout << "zona N = " << nord << ", S = " << sud
         << ", V = " << vest << ", E = " << est << endl;
    return 0;
}
Output real (compilat cu g++ -std=c++17 si rulat)
diagonala principala = 65
diagonala secundara  = 65
triunghi de sus      = 90
triunghi de jos      = 170
zona N = 17, S = 87, V = 45, E = 59
Autoverificare care te salveaza in examen: 17 + 87 + 45 + 59 = 208 (cele patru zone), iar cele doua diagonale insumeaza 65 + 65 - 13 = 117, pentru ca elementul central 13 sta pe amandoua. Total 208 + 117 = 325, exact suma numerelor de la 1 la 25. Daca totalul nu se inchide, ai gresit o conditie.
2

2. Inmultirea a doua matrice

Intai exemplul: A de 2x3 inmultit cu B de 3x2
      A (2 x 3)            B (3 x 2)
   [ 1  2  3 ]          [  7   8 ]
   [ 4  5  6 ]          [  9  10 ]
                        [ 11  12 ]

Elementul C[0][0]: linia 0 din A cu coloana 0 din B
   1*7 + 2*9 + 3*11 = 7 + 18 + 33 = 58

Elementul C[1][1]: linia 1 din A cu coloana 1 din B
   4*8 + 5*10 + 6*12 = 32 + 50 + 72 = 154
Produsul A * B se poate calcula doar daca numarul de coloane ale lui A este egal cu numarul de linii ale lui B. Daca A este m x n si B este n x p, rezultatul C este m x p, iar
C[i][j] = suma dupa k, de la 0 la n-1, a produselor A[i][k] * B[k][j].

Cu alte cuvinte: fiecare element al rezultatului este produsul scalar dintre o linie din A si o coloana din B. Dimensiunile se citesc usor asa: (m x n) * (n x p) = m x p — dimensiunile din mijloc trebuie sa coincida si dispar.

Cod C++ — algoritmul clasic cu trei bucle
#include <iostream>
using namespace std;
int main() {
    int m = 2, n = 3, p = 2;
    int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int b[3][2] = {{7, 8}, {9, 10}, {11, 12}};
    int c[2][2];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < p; j++) {
            c[i][j] = 0;                       // ZERO inainte de a aduna
            for (int k = 0; k < n; k++)
                c[i][j] += a[i][k] * b[k][j];
        }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) cout << c[i][j] << " ";
        cout << endl;
    }
    return 0;
}
Output real (compilat cu g++ -std=c++17 si rulat)
58 64
139 154
Complexitate: O(m * n * p) inmultiri — pentru matrice patratice de ordin n inseamna O(n3). La n = 100 sunt un milion de inmultiri (instantaneu); la n = 1000 sunt un miliard, adica deja secunde bune.
Greseala numarul 1 la Bac
Uitarea liniei c[i][j] = 0;

Fara ea, c[i][j] contine gunoi din memorie si toate
sumele ies aiurea. Alternativa sigura: foloseste o
variabila locala   int s = 0;   aduni in s, apoi
c[i][j] = s;   la finalul buclei dupa k.
3

3. Matricea unitate, necomutativitatea si puterea Ak

Intai exemplul: aceleasi doua matrice, inmultite in ambele ordini
A = [ 1  2 ]      B = [ 1  0 ]
    [ 0  1 ]          [ 3  1 ]

A * B = [ 7  2 ]      B * A = [ 1  2 ]
        [ 3  1 ]              [ 3  7 ]

Aceleasi matrice, rezultate diferite.
Inmultirea matricelor nu este comutativa: in general A * B este diferit de B * A. Uneori nici nu are sens sa le inmultesti in cealalta ordine — A de 2x3 cu B de 3x2 da un rezultat de 2x2, iar B * A da unul de 3x3. Inmultirea este insa asociativa: (A * B) * C = A * (B * C), si de asta are sens sa vorbim despre Ak.
Matricea unitate In are 1 pe diagonala principala si 0 in rest. Ea joaca la matrice rolul pe care il joaca numarul 1 la numere: A * I = I * A = A. De aceea, cand calculezi Ak prin inmultiri repetate, pornesti cu P = I si inmultesti de k ori — exact ca la rezultat = 1; inainte de o ridicare la putere obisnuita.
Cod C++ — A la puterea k, pornind de la matricea unitate
#include <iostream>
using namespace std;
const int N = 2;

void inmulteste(int A[N][N], int B[N][N], int C[N][N]) {
    int T[N][N];                      // matrice temporara: A sau B pot fi
    for (int i = 0; i < N; i++)       // chiar C, si le-am strica pe parcurs
        for (int j = 0; j < N; j++) {
            T[i][j] = 0;
            for (int k = 0; k < N; k++) T[i][j] += A[i][k] * B[k][j];
        }
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) C[i][j] = T[i][j];
}

int main() {
    int F[N][N] = {{1, 1}, {1, 0}};
    int P[N][N] = {{1, 0}, {0, 1}};   // matricea unitate I2
    for (int pas = 1; pas <= 5; pas++) {
        inmulteste(P, F, P);
        cout << "F^" << pas << " = [" << P[0][0] << " " << P[0][1]
             << " ; " << P[1][0] << " " << P[1][1] << "]" << endl;
    }
    return 0;
}
Output real (compilat cu g++ -std=c++17 si rulat)
F^1 = [1 1 ; 1 0]
F^2 = [2 1 ; 1 1]
F^3 = [3 2 ; 2 1]
F^4 = [5 3 ; 3 2]
F^5 = [8 5 ; 5 3]

Uita-te la numerele care apar: 1, 1, 2, 3, 5, 8 — sirul lui Fibonacci. Nu e o coincidenta amuzanta, ci proprietatea acestei matrice: in coltul stanga-sus al lui Fk sta termenul Fibonacci de rang k+1 (cu conventia F(1) = F(2) = 1). Verifica pe output: F5 are in coltul stanga-sus 8, care este chiar al saselea termen din 1, 1, 2, 3, 5, 8.

Capcana de implementare: daca scrii rezultatul direct peste una dintre matricele pe care le inmultesti, stricti valorile de care mai ai nevoie in bucla. De aceea functia de mai sus aduna intr-o matrice temporara T si abia la final copiaza in C.
4

4. Parcurgerea in spirala

Intai exemplul: matricea de 3x4 din provocarea de la inceput
 1  2  3  4
 5  6  7  8
 9 10 11 12

Tur 1: 1 2 3 4   (randul de sus, stanga -> dreapta)
       8 12      (coloana din dreapta, in jos)
       11 10 9   (randul de jos, dreapta -> stanga)
       5         (coloana din stanga, in sus)
Tur 2: 6 7       (ce a mai ramas in interior)

Rezultat: 1 2 3 4 8 12 11 10 9 5 6 7
Parcurgerea in spirala se scrie cel mai curat cu patru margini: sus, jos, st (stanga) si dr (dreapta). Fiecare tur consuma cate o margine si o strange spre interior. Bucla merge cat timp sus <= jos si st <= dr, adica atat timp cat mai exista dreptunghi neparcurs.
Cod C++ — parcurgere in spirala pentru o matrice m x n
#include <iostream>
using namespace std;
int main() {
    int m = 3, n = 4, a[3][4];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            a[i][j] = i * n + j + 1;

    int sus = 0, jos = m - 1, st = 0, dr = n - 1;
    while (sus <= jos && st <= dr) {
        for (int j = st; j <= dr; j++) cout << a[sus][j] << " ";
        sus++;
        for (int i = sus; i <= jos; i++) cout << a[i][dr] << " ";
        dr--;
        if (sus <= jos) {                       // mai exista rand de jos?
            for (int j = dr; j >= st; j--) cout << a[jos][j] << " ";
            jos--;
        }
        if (st <= dr) {                         // mai exista coloana stanga?
            for (int i = jos; i >= sus; i--) cout << a[i][st] << " ";
            st++;
        }
    }
    cout << endl;
    return 0;
}
Output real (compilat cu g++ -std=c++17 si rulat)
1 2 3 4 8 12 11 10 9 5 6 7
Acelasi program cu m = 4 si n = 4 (matrice 4x4 cu 1...16)
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Cele doua verificari din mijloc nu sunt decor. Ele conteaza cand ultimul tur al spiralei ramane un singur rand (matrice mai lata decat inalta) sau o singura coloana. Exemplu masurat pe matricea 3x4 de mai sus: cu verificari se afiseaza 12 valori, fara ele se afiseaza 13 — apare un 6 in plus la final, pentru ca randul din ultimul tur este parcurs si invers. Atentie: pe o matrice patratica (3x3, 4x4, 5x5) rezultatul iese identic si fara verificari, asa ca un test facut doar pe patrat nu prinde niciodata bug-ul. Complexitate: O(m * n) — fiecare element este atins exact o data.
5

5. Bordarea unei matrice

Intai exemplul: matricea de 2x3 bordata cu un chenar de 0
Initiala (2 x 3)      Bordata (4 x 5)
  1  2  3               0  0  0  0  0
  4  5  6               0  1  2  3  0
                        0  4  5  6  0
                        0  0  0  0  0

Elementul care era pe pozitia (0,0) este acum pe (1,1):
fiecare indice a crescut cu 1.
A borda o matrice inseamna a-i adauga un chenar de o linie sus, o linie jos, o coloana la stanga si o coloana la dreapta. O matrice m x n devine (m+2) x (n+2), iar elementul care era la (i, j) ajunge la (i+1, j+1).

Bordarea apare la Bacalaureat in doua feluri. Ca cerinta in sine („bordati matricea cu un chenar avand o valoare data si afisati matricea obtinuta”) si, mult mai des, ca truc de implementare: daca lucrezi cu vecinii unui element, un chenar de zerouri scapa de toate verificarile de tipul if (i > 0 && j < n - 1 && ...), unde se pierd de obicei punctele.

Cod C++ — bordare si suma celor 8 vecini
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    int m = 2, n = 3;
    int b[10][10] = {0};        // totul 0, deci chenarul e deja pus
    int v[2][3] = {{1, 2, 3}, {4, 5, 6}};
    for (int i = 1; i <= m; i++)            // datele intra de la (1,1)
        for (int j = 1; j <= n; j++)
            b[i][j] = v[i - 1][j - 1];

    cout << "Matricea bordata (" << m + 2 << " x " << n + 2 << "):" << endl;
    for (int i = 0; i <= m + 1; i++) {
        for (int j = 0; j <= n + 1; j++) cout << setw(2) << b[i][j] << " ";
        cout << endl;
    }
    cout << "Suma celor 8 vecini (fara verificari de margine):" << endl;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int s = 0;
            for (int di = -1; di <= 1; di++)
                for (int dj = -1; dj <= 1; dj++)
                    if (di || dj) s += b[i + di][j + dj];   // sare peste el insusi
            cout << setw(3) << s;
        }
        cout << endl;
    }
    return 0;
}
Output real (compilat cu g++ -std=c++17 si rulat)
Matricea bordata (4 x 5):
 0  0  0  0  0
 0  1  2  3  0
 0  4  5  6  0
 0  0  0  0  0
Suma celor 8 vecini (fara verificari de margine):
 11 19 13
  8 16 10
Verifica un numar cu mana: elementul 5 are ca vecini pe 1, 2, 3, 4, 6 si trei zerouri din chenar — 1+2+3+4+6 = 16, exact ce a afisat programul. Singurul if ramas in bucla este if (di || dj), care sare peste elementul insusi; verificarile de margine au disparut complet.
Atentie la declarare
Daca matricea initiala are cel mult 100 x 100,
declara b[102][102], nu b[100][100]: chenarul
cere doua linii si doua coloane in plus.

Rezervarea unei margini in plus e mai ieftina
decat o depasire de indice la corectare.
6

6. Recapitulare operationala si capcanele de la Bac

Tabel de complexitati — ce inveti pe de rost
Operatie                          Complexitate
--------------------------------  -------------
Parcurgere completa (m x n)       O(m * n)
Sume pe zone / diagonale          O(n^2)
Doar diagonala (o singura bucla)  O(n)
Inmultire A(m x n) * B(n x p)     O(m * n * p)
Inmultire matrice patratice       O(n^3)
Putere A^k prin inmultiri         O(k * n^3)
Parcurgere in spirala             O(m * n)
Bordare                           O(m * n)
Capcane care costa puncte la proba
1. Indici de la 0 sau de la 1?
   Diagonala secundara e i + j == n - 1 cu indici
   de la 0, dar i + j == n + 1 cu indici de la 1.
   Scrie pe ciorna un exemplu mic si verifica.

2. c[i][j] = 0 uitat inainte de suma la inmultire.

3. Conditia de compatibilitate neverificata:
   A(2x3) * B(2x3) nu se poate calcula.

4. Spirala fara cele doua if-uri din mijloc:
   duplica randul (sau coloana) din ultimul tur la
   matricele dreptunghiulare, de exemplu 3 x 4.
   Pe matrice patratice iese corect si fara ele,
   deci testul facut doar pe 4 x 4 nu prinde nimic.

5. Bordare fara loc rezervat in declarare:
   b[100][100] nu incape o matrice bordata 102x102.

6. Zonele N, S, V, E: fiecare cere DOUA conditii,
   una pe fiecare diagonala. Cu una singura obtii
   triunghiul, nu zona.
Metoda de control in 30 de secunde: aplica algoritmul pe o matrice de 3x3 sau 4x4 scrisa cu numerele 1, 2, 3, ... si compara cu ce ai calculat mental. Aproape toate greselile de indice se vad pe un exemplu atat de mic — nu ai nevoie de calculator ca sa le prinzi.

Exercitii practice

Exercitiul 1 (Nivel minim) — Zone si diagonale, pe hartie

Se da matricea de 5x5 de mai jos. Calculeaza: (a) suma elementelor de pe diagonala secundara; (b) lista elementelor din zona de nord si suma lor.

 4  7  2  9  1
 3  8  5  6  0
 1  2  7  4  3
 9  5  0  8  6
 2  1  4  3  7

Indiciu: diagonala secundara are i + j = 4, iar zona de nord cere i < j SI i + j < 4 (indici de la 0).

Vezi rezolvarea

(a) Diagonala secundara: i + j = n - 1 = 4.

  1. (0,4) = 1
  2. (1,3) = 6
  3. (2,2) = 7
  4. (3,1) = 5
  5. (4,0) = 2

Suma = 1 + 6 + 7 + 5 + 2 = 21.

(b) Zona de nord: i < j SI i + j < 4. Iau pozitiile de deasupra diagonalei principale si le pastrez doar pe cele cu suma indicilor sub 4:

  1. (0,1) = 7 — suma indicilor 1, trece
  2. (0,2) = 2 — suma indicilor 2, trece
  3. (0,3) = 9 — suma indicilor 3, trece
  4. (0,4) — suma indicilor 4, NU trece (e chiar pe diagonala secundara)
  5. (1,2) = 5 — suma indicilor 3, trece
  6. (1,3) — suma indicilor 4, NU trece
  7. (2,3), (2,4), (3,4) — toate au suma indicilor peste 4, NU trec (sunt in zona de est)

Zona de nord = {7, 2, 9, 5}, suma = 23.

Autocontrol: zona de nord a unei matrice 5x5 are exact 4 pozitii (le poti numara pe desen: 3 pe primul rand plus 1 pe al doilea), si tot atatea am gasit. Daca iti ies 6 elemente, ai uitat a doua conditie si ai luat tot triunghiul de deasupra diagonalei principale.

Exercitiul 2 (Nivel standard) — Inmultirea a doua matrice, cu verificare

Scrie un program C++ care citeste m, n, p, apoi matricea A (m x n) si matricea B (n x p), si afiseaza produsul C = A * B. Programul trebuie sa afiseze mesajul imposibil daca numarul de coloane citit pentru A nu coincide cu numarul de linii citit pentru B.

Testeaza pe datele din lectie: A = 1 2 3 / 4 5 6 si B = 7 8 / 9 10 / 11 12. Rezultatul corect este 58 64 / 139 154.

Vezi rezolvarea

Structura, pas cu pas:

  1. Citeste m, n1 pentru A si n2, p pentru B. Daca n1 != n2, afiseaza imposibil si iesi din program — asta e chiar conditia de compatibilitate din Atomul 2.
  2. Citeste cele doua matrice in doua bucle duble.
  3. Pentru fiecare pereche (i, j) cu i de la 0 la m-1 si j de la 0 la p-1: pune int s = 0;, apoi aduna in s toate produsele a[i][k] * b[k][j] pentru k de la 0 la n-1, si abia la final scrie c[i][j] = s;.
  4. Afiseaza matricea C, cate un rand pe linie.

De ce variabila locala s si nu direct c[i][j] += ...? Ca sa nu poti uita initializarea cu zero: int s = 0; se afla exact langa bucla care aduna, deci se vede dintr-o privire. Este acelasi algoritm ca in lectie, doar mai greu de gresit.

Rezultat asteptat pe datele de test:

58 64
139 154

Autocontrol rapid, fara sa rulezi: verifica un singur element cu mana, de exemplu C[1][0] = 4*7 + 5*9 + 6*11 = 28 + 45 + 66 = 139. Daca acel numar iese, restul algoritmului este aproape sigur corect; daca iese altceva, ai gresit ordinea indicilor la b[k][j] (o greseala frecventa este sa scrii b[j][k]).

Criterii de evaluare: (1) compatibilitatea e verificata inainte de calcul, (2) fiecare element al lui C porneste de la zero, (3) rezultatul are dimensiunea m x p, (4) programul da 58 64 / 139 154 pe datele de test.

Exercitiul 3 (Nivel performanta) — Completarea unei matrice in spirala

Scrie un program C++ care citeste n si completeaza o matrice n x n cu numerele de la 1 la n*n, asezate in spirala pornind din coltul stanga-sus, in sensul acelor de ceasornic. Afiseaza matricea.

Pentru n = 4 rezultatul trebuie sa fie:

  1   2   3   4
 12  13  14   5
 11  16  15   6
 10   9   8   7

Apoi fa un mic experiment: ruleaza programul si cu, si fara cele doua verificari din mijlocul buclei, pentru n = 3, n = 4 si n = 5, si dupa aceea pentru o matrice dreptunghiulara de 3 linii si 4 coloane. Scrie in comentariu ce ai observat.

Vezi rezolvarea

Ideea: este exact algoritmul cu patru margini din Atomul 4, dar in locul lui cout pui o atribuire. In loc sa citesti pozitiile in ordinea spiralei, le scrii in aceeasi ordine, cu un contor val care creste de la 1.

  1. Initializezi sus = 0, jos = n - 1, st = 0, dr = n - 1, val = 1.
  2. Cat timp sus <= jos si st <= dr, in aceeasi ordine ca la parcurgere: randul de sus stanga-dreapta cu a[sus][j] = val++, apoi sus++; coloana din dreapta in jos, apoi dr--; daca sus <= jos, randul de jos dreapta-stanga, apoi jos--; daca st <= dr, coloana din stanga in sus, apoi st++.
  3. Afisezi matricea cu setw(3) ca sa se alinieze coloanele.

Rezultatul experimentului (verificat ruland ambele variante):

  • n = 3, n = 4, n = 5 (patratice): rezultatul este identic cu si fara verificari. La o matrice patratica, fiecare tur scoate o linie si o coloana din fiecare parte, deci blocul ramas este mereu patrat — ultimul tur are ori 2 x 2, ori o singura celula, si buclele neprotejate ies goale de la sine.
  • 3 linii x 4 coloane: rezultatul difera. Cu verificari se obtine 1 2 3 4 / 10 11 12 5 / 9 8 7 6; fara ele, celula din mijloc primeste 13 in loc de 11, adica o valoare este suprascrisa si alta lipseste.

Concluzia care conteaza: testul pe matrice patratice nu poate demonstra ca algoritmul e corect — ascunde exact eroarea pe care ar trebui sa o gaseasca. Un algoritm pe matrice se testeaza obligatoriu si pe un caz dreptunghiular, si pe cazurile-limita cu o singura linie sau o singura coloana.

Verificare a rezultatului, fara sa numeri tot: ultimul numar asezat trebuie sa fie n*n (la n = 4, valoarea 16). Daca in matrice apar doua valori egale sau lipseste o valoare, ai omis o verificare de margine.

Criterii de evaluare: (1) programul da exact matricea din enunt pentru n = 4, (2) merge corect si pentru n = 1, n = 3 si n = 5 (nicio valoare dublata, nicio valoare lipsa), (3) sunt folosite cele patru margini, nu patru bucle scrise separat pentru fiecare dimensiune, (4) comentariul spune concret ce s-a schimbat si ce nu, la fiecare dimensiune incercata.

Ce ai invatat astazi

  • Zonele unei matrice patratice: diagonala principala i == j, diagonala secundara i + j == n - 1, iar zonele N, S, V, E cer cate doua conditii
  • Inmultirea A(m x n) * B(n x p): se poate doar daca dimensiunile din mijloc coincid, rezultatul e m x p, complexitate O(m * n * p)
  • Fiecare element al produsului porneste de la zero — uitarea initializarii e greseala numarul 1
  • Inmultirea nu e comutativa, dar e asociativa; matricea unitate I este neutrul, deci Ak se calculeaza pornind cu P = I
  • Parcurgerea in spirala cu patru margini (sus, jos, st, dr) si cele doua verificari care evita duplicarea ultimului tur — O(m * n)
  • Bordarea: m x n devine (m+2) x (n+2), elementul (i, j) trece la (i+1, j+1), iar chenarul de zerouri elimina verificarile de margine la lucrul cu vecinii

Vrei mai mult?

  • Provocare: scrie parcurgerea in spirala invers, dinspre centru spre exterior si in sens trigonometric. Nu porni de la zero — ia algoritmul cu patru margini, colecteaza elementele intr-un vector si apoi afiseaza-l de la coada spre cap. Compara cu varianta in care schimbi direct ordinea buclelor: care dintre cele doua e mai usor de demonstrat ca este corecta?
  • De gandit: la inmultirea a doua matrice patratice de ordin n faci n3 inmultiri. Daca dublezi n, de cate ori creste timpul de calcul? Verifica raspunsul masurand efectiv, cu matrice de ordin 200 si 400 generate aleator.
  • Deschidere: puterea unei matrice, pe care ai calculat-o azi prin inmultiri repetate, se poate calcula si in O(log k) pasi, combinand-o cu exponentierea rapida din Lectia 2 — se ridica matricea la patrat in loc sa se inmulteasca de k ori. Asa se calculeaza al miliardul termen Fibonacci modulo un numar prim, in cateva zeci de inmultiri de matrice 2x2.

Urmatoarea lectie

Continua cu Factorizare n! pentru formula Legendre.

Continua →