Programare Competitivă

Matrici - noțiuni de bază

O matrice (sau tablou bidimensional) este un tabel de valori organizat pe linii și coloane. Este ca un vector, dar în loc de o singură dimensiune, are două.

Cum arată o matrice?

         Coloana 1  Coloana 2  Coloana 3  Coloana 4
Linia 1:    3          7          2          5
Linia 2:    1          4          8          6
Linia 3:    9          0          3          2

Aceasta este o matrice cu 3 linii și 4 coloane (3 x 4).

Elementul de pe linia i, coloana j se notează a[i][j]:

  • a[1][1] = 3
  • a[2][3] = 8
  • a[3][4] = 2

Declararea unei matrici

int a[101][101];

Aceasta creează o matrice de cel mult 100 x 100 elemente. Declarăm 101 pentru indexare de la 1.

Avem nevoie și de dimensiunile efective:

int n, m; // n = nr linii, m = nr coloane

Matrice pătratică: când n == m (același număr de linii și coloane), matricea se numește pătratică. Multe probleme lucrează doar cu matrici pătratice.

Citirea unei matrici

De obicei, pe prima linie primim n și m, apoi n linii cu câte m valori.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[101][101];
int n, m;

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fin >> a[i][j];

    return 0;
}

date.in:

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

Afișarea unei matrici

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++)
        fout << a[i][j] << " ";
    fout << endl;
}

date.out:

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

Parcurgerea pe linii

Aceasta este parcurgerea standard - linia cu linie, de la stânga la dreapta:

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        // procesăm a[i][j]

Ordinea elementelor: a[1][1], a[1][2], ..., a[1][m], a[2][1], a[2][2], ...

Parcurgerea pe coloane

Inversăm buclele - coloana exterioară, linia interioară:

for (int j = 1; j <= m; j++)
    for (int i = 1; i <= n; i++)
        // procesăm a[i][j]

Ordinea: a[1][1], a[2][1], a[3][1], ..., a[1][2], a[2][2], ...

Suma tuturor elementelor

int suma = 0;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        suma = suma + a[i][j];

fout << suma;

Maximul din matrice

int maxim = a[1][1];

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] > maxim)
            maxim = a[i][j];

fout << maxim;

Suma pe fiecare linie

for (int i = 1; i <= n; i++) {
    int suma = 0;
    for (int j = 1; j <= m; j++)
        suma = suma + a[i][j];
    fout << "Linia " << i << ": " << suma << endl;
}

Exemplu: pentru matricea de mai sus:

  • Linia 1: 3+7+2+5 = 17
  • Linia 2: 1+4+8+6 = 19
  • Linia 3: 9+0+3+2 = 14

Suma pe fiecare coloană

for (int j = 1; j <= m; j++) {
    int suma = 0;
    for (int i = 1; i <= n; i++)
        suma = suma + a[i][j];
    fout << "Coloana " << j << ": " << suma << endl;
}

Linia cu suma maximă

int maxSuma = 0;
int linieMax = 1;

for (int i = 1; i <= n; i++) {
    int suma = 0;
    for (int j = 1; j <= m; j++)
        suma = suma + a[i][j];
    if (suma > maxSuma) {
        maxSuma = suma;
        linieMax = i;
    }
}

fout << "Linia " << linieMax << " cu suma " << maxSuma;

Numărarea elementelor cu o proprietate

Câte elemente pare are matricea?

int cnt = 0;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] % 2 == 0)
            cnt++;

fout << cnt;

Matrice pătratică (n x n)

Când n == m, spunem că matricea este pătratică. Se citește doar n:

fin >> n;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        fin >> a[i][j];

Matricile pătratice au proprietăți speciale: diagonale, simetrie, zone - le vom studia în lecțiile următoare.

Exemplu complet

Citim o matrice și afișăm suma fiecărei linii și maximul global.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[101][101];
int n, m;

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fin >> a[i][j];

    int maxim = a[1][1];

    for (int i = 1; i <= n; i++) {
        int suma = 0;
        for (int j = 1; j <= m; j++) {
            suma = suma + a[i][j];
            if (a[i][j] > maxim)
                maxim = a[i][j];
        }
        fout << "Linia " << i << ": suma = " << suma << endl;
    }

    fout << "Maximul: " << maxim << endl;

    return 0;
}

date.in:

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

date.out:

Linia 1: suma = 17
Linia 2: suma = 19
Linia 3: suma = 14
Maximul: 9

Greșeli frecvente

1. Inversarea liniilor cu coloanele

fin >> a[j][i]; // GREȘIT - j e coloana, i e linia
fin >> a[i][j]; // CORECT - a[linie][coloana]

Mereu: primul indice = linia, al doilea = coloana.

2. Folosirea lui n în loc de m (sau invers)

for (int j = 1; j <= n; j++) // GREȘIT dacă matricea nu e pătratică
for (int j = 1; j <= m; j++) // CORECT - m e nr de coloane

3. Matricea declarată prea mică

Dacă n și m pot fi cel mult 100, declarăm a[101][101] (pentru indexare de la 1).

4. Declararea matricii locale

int main() {
    int a[1000][1000]; // PERICOL! Depășește stiva
}

Matricile mari se declară global.

Ce să reții

  • O matrice este un tabel cu linii și coloane: a[i][j].
  • Se citește cu două for-uri imbricate.
  • Parcurgerea pe linii: for i, for j. Pe coloane: for j, for i.
  • Suma pe linie: buclă interioară pe coloane. Suma pe coloană: buclă interioară pe linii.
  • Matricea pătratică: n == m.
  • Declarăm matricile global și suficient de mari.
Cuprins Inapoi Inainte