Tablouri bidimensionale (matrice)

Elevii lucrează cu structuri de date bidimensionale și le prelucrează prin parcurgere pe linii și coloane.

Ce este o matrice și cum o declarăm

O matrice (tablou bidimensional) este un tabel de valori de același tip, organizat pe linii și coloane — exact ca un orar școlar sau ca o tablă de șah. Dacă vectorul avea un singur indice, matricea are doi: primul arată linia, al doilea arată coloana.

În C++, declararea arată așa: int a[20][30]; — o matrice cu cel mult 20 de linii și 30 de coloane, cu elemente întregi. Elementul de pe linia i și coloana j se accesează cu a[i][j] — și se comportă ca orice variabilă obișnuită.

Dimensiunile efectiv folosite se citesc separat: n (numărul de linii) și m (numărul de coloane). O matrice cu n linii și m coloane are în total n × m elemente.

Convenția de ordine este sfântă și trebuie repetată până devine reflex: întâi linia, apoi coloana. a[3][5] este elementul de pe linia 3, coloana 5 — nu invers! Inversarea indicilor este greșeala numărul unu la acest capitol: programul compilează, dar prelucrează cu totul alte elemente.

Ca și la vectori, indexarea în C++ începe de la 0 (prima linie este linia 0), dar multe probleme numerotează de la 1 — verifică mereu convenția din enunț. Și tot ca la vectori, accesarea unei poziții din afara matricei nu este semnalată de compilator, dar strică execuția.

Cazuri particulare cu nume proprii: matricea cu o singură linie sau o singură coloană seamănă cu un vector; matricea cu n = m se numește matrice pătratică și are proprietăți speciale, discutate mai jos.

Parcurgerea matricei: două bucle imbricate

Pentru a vizita toate elementele matricei ai nevoie de două bucle for imbricate — una pentru linii, una pentru coloane:

for (i = 0; i < n; i++) for (j = 0; j < m; j++) cin >> a[i][j];

Cu bucla exterioară pe i și cea interioară pe j, parcurgerea se face pe linii: se vizitează complet linia 0 (element cu element, de la stânga la dreapta), apoi linia 1 și așa mai departe. Este ordinea firească de citire și de afișare.

Dacă inversezi buclele — exteriorul pe j, interiorul pe i — parcurgerea se face pe coloane: întâi toată coloana 0, de sus în jos, apoi coloana 1... Elementele vizitate sunt aceleași, dar ordinea diferă, iar la afișare rezultatul arată complet altfel.

La afișarea sub formă de tabel, detaliul care face diferența este trecerea la rând nou: după fiecare linie completă (adică după terminarea buclei interioare) se afișează endl sau '\n'. Dacă pui rândul nou în interiorul buclei interioare, fiecare element apare pe rândul lui; dacă îl uiți complet, toată matricea se afișează pe un singur rând.

Numărul total de pași: bucla interioară face m pași pentru fiecare dintre cei n pași ai buclei exterioare, deci corpul se execută de n × m ori — regula generală a buclelor imbricate.

Greșeala clasică de imbricare rămâne valabilă: cele două bucle au contoare diferite (i și j); refolosirea aceluiași contor face parcurgerea haotică.

Operații pe linii și pe coloane

Multe cerințe se referă doar la o anumită linie sau o anumită coloană — și aici se vede dacă ai înțeles rolul celor doi indici:

• Suma elementelor de pe linia k: linia e fixă, coloana variază — s = 0; for (j = 0; j < m; j++) s += a[k][j]; Observă: o singură buclă, pentru că un indice e fixat;
• Suma elementelor de pe coloana k: coloana e fixă, linia variază — for (i = 0; i < n; i++) s += a[i][k];
• Maximul de pe fiecare linie: pentru fiecare i, aplici șablonul de maxim de la vectori pe linia i (inițializezi cu a[i][0], primul element al liniei — nu cu 0!);
• Suma pe fiecare linie: aici acumulatorul se reinițializează la începutul fiecărei linii, adică în interiorul buclei exterioare, dar înaintea celei interioare. Poziția inițializării este exact ce testează problemele: s = 0 pus înaintea ambelor bucle dă suma întregii matrice, nu suma fiecărei linii.

Alte prelucrări frecvente:

• interschimbarea a două linii p și q: interschimbi a[p][j] cu a[q][j] pentru fiecare j — element cu element, cu variabilă auxiliară;
• numărarea elementelor cu o proprietate dintr-o linie, coloană sau din toată matricea — același șablon de numărare de la vectori, cu una sau două bucle după caz.

Regula practică de citire a enunțului: „pe linia k” → k e primul indice, fix; „pe coloana k” → k e al doilea indice, fix. Cine fixează indicele greșit calculează pe coloană în loc de linie și pierde toate punctele cerinței.

Matricea pătratică și diagonalele

Matricea pătratică are numărul de linii egal cu numărul de coloane (n = m). Doar la matrice pătratice vorbim despre diagonale:

• Diagonala principală unește colțul stânga-sus cu colțul dreapta-jos și conține elementele cu indicii egali: a[0][0], a[1][1], ..., a[n-1][n-1]. Condiția de apartenență: i == j. Suma ei se calculează cu o singură buclă: for (i = 0; i < n; i++) s += a[i][i];
• Diagonala secundară unește colțul dreapta-sus cu colțul stânga-jos. Cu indexare de la 0, condiția este i + j == n - 1, iar elementele sunt a[0][n-1], a[1][n-2], ..., a[n-1][0]. (Cu indexare de la 1, condiția devine i + j == n + 1 — încă un motiv să verifici convenția enunțului.)

Diagonalele împart matricea pătratică în zone care apar des în cerințe:

• elementele de deasupra diagonalei principale: i < j;
• elementele de sub diagonala principală: i > j;
• pentru diagonala secundară: deasupra înseamnă i + j < n - 1, dedesubt i + j > n - 1.

Capcană de numărare: cele două diagonale au câte n elemente fiecare, dar dacă n este impar, ele se intersectează în elementul din centru (a[n/2][n/2]), care aparține amândurora — la „suma elementelor de pe ambele diagonale” acest element nu trebuie adunat de două ori.

Tot la matrice pătratice se definește transpusa: matricea obținută prin transformarea liniilor în coloane, adică interschimbarea lui a[i][j] cu a[j][i]. O matrice egală cu transpusa ei (a[i][j] == a[j][i] peste tot) se numește simetrică față de diagonala principală.

Probleme aplicative tipice

Tiparele de probleme cu matrice combină șabloanele de la vectori cu geometria tabelului:

• Suma/maximul/numărarea pe toată matricea: două bucle imbricate plus acumulatorul cunoscut. Maximul se inițializează cu a[0][0], primul element al matricei;
• Prelucrări pe zone: „elementele pare de sub diagonala principală” → două bucle plus if cu condiție compusă (i > j && a[i][j] % 2 == 0). Enunțurile de acest tip testează dacă știi să combini condiția de zonă cu condiția de valoare;
• Marginile matricei (chenarul): un element este pe margine dacă i == 0 sau i == n-1 sau j == 0 sau j == m-1. Interiorul este exact opusul: toate cele patru condiții false;
• Linia cu suma maximă: calculezi suma fiecărei linii (acumulator resetat pe linie), apoi aplici șablonul de maxim pe aceste sume, memorând indicele liniei câștigătoare;
• Verificări cu steag: „matricea este simetrică?” — pornești cu ok = 1 și îl faci 0 la prima pereche cu a[i][j] != a[j][i];
• Generarea matricelor: unele probleme cer construirea matricei după o regulă, fără citire — de exemplu a[i][j] = i + j, sau matricea unitate (1 pe diagonala principală, 0 în rest: a[i][j] = (i == j)).

Strategia de rezolvare rămâne aceeași ca la vectori, cu un pas în plus: întâi stabilești ce zonă a matricei parcurgi (toată? o linie? o diagonală? sub diagonală?), apoi alegi numărul de bucle (două pentru zone bidimensionale, una singură pentru o linie, o coloană sau o diagonală) și abia apoi aplici șablonul de prelucrare. Multe greșeli vin din folosirea a două bucle acolo unde zona cere doar una.

Test — 6 întrebări ca la examen