Zonele unei matrice pătratice: diagonale, triunghiuri, margini

Într-o matrice pătratică (n linii și n coloane), aproape orice cerință de la BAC informatică se reduce la o zonă: elementele de pe diagonala principală, cele de deasupra diagonalei secundare, triunghiul de nord, marginea. Fiecare zonă se descrie printr-o condiție simplă pe indicii i și j. Dacă le știi pe de rost, rezolvi în câteva secunde grilele de la Subiectul I și construiești fără ezitare matricele de la Subiectul II sau III.

Peste tot în articol, liniile și coloanele sunt numerotate de la 1 la n. La final vezi ce se schimbă dacă numerotezi de la 0.

Diagonala principală

Diagonala principală merge din colțul stânga-sus în colțul dreapta-jos. Elementele ei au linia egală cu coloana: i == j.

• deasupra diagonalei principale: i < j;
• sub diagonala principală: i > j.

Diagonala secundară

Diagonala secundară merge din colțul dreapta-sus în colțul stânga-jos: (1, n), (2, n−1), …, (n, 1). Suma indicilor e mereu aceeași: i + j == n + 1.

• deasupra diagonalei secundare: i + j < n + 1 (adică i + j <= n);
• sub diagonala secundară: i + j > n + 1.

Ca să ții minte de ce, gândește-te la colțul (1, 1): e deasupra diagonalei secundare și are i + j = 2, cea mai mică sumă posibilă. Colțul (n, n), cu suma 2n, e sub ea.

Cele patru triunghiuri: nord, sud, est, vest

Cele două diagonale împart matricea în patru zone triunghiulare. Fiecare se obține combinând câte o condiție de la fiecare diagonală (fără elementele de pe diagonale):

Iată harta pentru n = 5, unde \ e diagonala principală, / e diagonala secundară, iar X e elementul din centru, aflat pe amândouă:

\ N N N /
V \ N / E
V V X E E
V / S \ E
/ S S S \

Centrul există doar pentru n impar și este elementul a[(n + 1) / 2][(n + 1) / 2]. Pentru n par, diagonalele nu au niciun element comun.

Marginea (chenarul)

Un element e pe margine dacă se află pe prima sau ultima linie, ori pe prima sau ultima coloană:

i == 1 || i == n || j == 1 || j == n

Interiorul e negația: i > 1 && i < n && j > 1 && j < n (legile lui De Morgan în acțiune). Marginea are 4(n − 1) elemente pentru n ≥ 2.

Exemplu numeric complet, n = 4

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

Verificări rapide: diagonala principală + deasupra + dedesubt = 34 + 36 + 66 = 136, suma tuturor numerelor de la 1 la 16. Iar marginea (102) plus interiorul (6 + 7 + 10 + 11 = 34) dă tot 136.

Parcurgere eficientă: nu trece prin toată matricea

Poți calcula orice zonă cu două bucle pe toată matricea și un if cu condiția zonei — e corect și ușor de scris. Dar pentru diagonale e risipă: elementele lor se obțin direct, cu o singură buclă.

#include <iostream>
using namespace std;

int a[101][101], n;

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

    int sp = 0, ss = 0;
    for (int i = 1; i <= n; i++)
    {
        sp = sp + a[i][i];            // diagonala principală
        ss = ss + a[i][n + 1 - i];    // diagonala secundară
    }
    cout << sp << " " << ss << endl;

    int sus = 0;                      // strict deasupra diagonalei principale
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            sus = sus + a[i][j];
    cout << sus;
    return 0;
}

Pentru matricea de 4 × 4 de mai sus, programul afișează 34 34 și apoi 36. Bucla for (int j = i + 1; …) pornește direct de la prima coloană aflată deasupra diagonalei, deci nu mai e nevoie de condiția i < j.

Dacă numerotezi de la 0

Cu indici de la 0 la n − 1, diagonala principală rămâne i == j, iar zonele față de ea nu se schimbă. Se schimbă doar diagonala secundară: i + j == n - 1, cu „deasupra” i + j < n - 1 și „sub” i + j > n - 1. Marginea devine i == 0 || i == n - 1 || j == 0 || j == n - 1. Alege o convenție și nu le amesteca în același program.