Construirea unei matrice după o regulă dată

Una dintre cerințele care revin des la BAC informatică sună cam așa: „Scrieți un program C++ care citește un număr natural n și construiește în memorie o matrice cu n linii și n coloane, astfel încât…”, urmată de un exemplu pentru n=4 sau n=5. Enunțul îți descrie regula în cuvinte, dar adevărata cheie e exemplul. Dacă știi să „citești” exemplul și să găsești formula lui a[i][j], programul are de obicei mai puțin de 15 rânduri.

Mai jos ai metoda pe care o poți aplica la orice astfel de cerință, plus tiparele care apar cel mai des.

Metoda în 4 pași

1. Scrie indicii lângă exemplu. Notează numărul liniei în stânga și al coloanei deasupra. Hotărăște de la început dacă numeri de la 1 sau de la 0 — formula diferă.
2. Caută ce rămâne constant. Valorile sunt egale pe linii? Pe coloane? Pe diagonale paralele cu diagonala principală? Pe „rame” concentrice? Fiecare răspuns te duce la o anumită expresie în i și j.
3. Scrie formula și verific-o pe 3 elemente, dintre care măcar unul de la margine și unul de pe diagonală. Cele mai multe greșeli apar exact acolo.
4. Dacă nu există o formulă directă, vezi dacă fiecare element se obține din vecinii deja calculați (cel de sus, cel din stânga) sau dacă matricea se umple cu valori consecutive într-o anumită ordine.

Tiparele care apar cel mai des

Cu indici de la 1 la n, iată ce să cauți în exemplu și ce formulă îi corespunde:

Exemplul 1: valori constante pe diagonale

Pentru n=4 se cere matricea:

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

Observi că pe fiecare paralelă la diagonala secundară valorile sunt egale, deci totul depinde de i + j. Primul element, a[1][1], este 1, iar i+j=2, deci formula e a[i][j] = i + j - 1. Verificare: a[1][4] = 1+4-1 = 4 (corect), a[4][4] = 7 (corect), a[3][2] = 4 (corect).

Matricea de distanțe față de diagonala principală arată așa, pentru n=4:

0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0

Aici formula e a[i][j] = |i - j|, adică abs(i - j) în C++. Pe diagonala principală i=j, deci valoarea e 0.

Exemplul 2: min(i, j) și ramele concentrice

Matricea de mai jos (n=4) are forma unor „L”-uri: prima linie și prima coloană conțin 1, apoi restul liniei și coloanei a doua conțin 2 și așa mai departe.

1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4

Valoarea e cea mai mică dintre linie și coloană: a[i][j] = min(i, j). Dacă „L”-urile ar fi fost întoarse (cu n pe prima linie și prima coloană), formula ar fi fost max(i, j), cu ordinea valorilor inversată.

Pentru rame concentrice, exemplul pentru n=5 este:

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

Valoarea unui element este „la câți pași de margine se află” plus 1. Distanța până la sus este i-1, până jos n-i, până la stânga j-1, până la dreapta n-j. Luând minimul și adunând 1 obții min(i, j, n-i+1, n-j+1). Programul complet:

#include <iostream>
using namespace std;

int a[21][21];

int main()
{
    int n, i, j, d;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            d = i;
            if (j < d) d = j;
            if (n - i + 1 < d) d = n - i + 1;
            if (n - j + 1 < d) d = n - j + 1;
            a[i][j] = d;
        }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

Pentru n=5 programul afișează exact matricea de mai sus. Observă că minimul e calculat cu if-uri simple — nu ai nevoie de nicio funcție de bibliotecă.

Exemplul 3: zone separate de diagonală

Uneori regula e pe zone: „elementele de pe diagonala principală sunt 0, cele de deasupra ei sunt 1, iar cele de sub ea sunt 2”. Aici nu cauți o formulă, ci o condiție pe indici: i == j pe diagonală, i < j deasupra, i > j dedesubt. Pentru diagonala secundară condiția e i + j == n + 1 (cu indici de la 1).

if (i == j) a[i][j] = 0;
else if (i < j) a[i][j] = 1;
else a[i][j] = 2;

Exemplul 4: elemente calculate din vecini

Unele enunțuri spun direct: „elementele primei linii și ale primei coloane sunt egale cu 1, iar oricare alt element este egal cu suma dintre elementul aflat deasupra lui și cel aflat în stânga lui”. Pentru n=4 rezultă:

1 1  1  1
1 2  3  4
1 3  6 10
1 4 10 20

Aici nu există o formulă simplă în i și j pe care să o scrii direct, dar nici nu ai nevoie: parcurgi matricea linie cu linie, de la stânga la dreapta, așa că vecinii de sus și din stânga sunt deja calculați când ajungi la a[i][j]:

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
        if (i == 1 || j == 1) a[i][j] = 1;
        else a[i][j] = a[i - 1][j] + a[i][j - 1];

Ordinea parcurgerii contează. Dacă regula ar fi spus „suma dintre elementul de dedesubt și cel din dreapta”, ar fi trebuit să parcurgi de jos în sus și de la dreapta la stânga.

Exemplul 5: umplere „în șerpuire”

O altă cerință clasică: matricea cu n linii și m coloane se umple cu numerele 1, 2, …, n·m, pe liniile impare de la stânga la dreapta, iar pe cele pare de la dreapta la stânga. Pentru n=3, m=4:

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

Ai două variante. Prima: un contor k care crește de la 1 și o parcurgere care schimbă sensul în funcție de paritatea liniei. A doua: formula directă — pe liniile impare a[i][j] = (i-1)*m + j, pe cele pare a[i][j] = (i-1)*m + m - j + 1. Verifică: a[2][1] = 4 + 4 - 1 + 1 = 8, corect.

Detalii care costă puncte

• Indici de la 0 vs. de la 1. Dacă parcurgi de la 0, formula i + j - 1 devine i + j + 1. Alege o convenție și ține-te de ea în tot programul.
• Dimensiunea tabloului. Dacă n ≤ 20 și folosești indici de la 1, declară cel puțin a[21][21].
• Afișarea. Enunțul cere de obicei câte o linie a matricei pe fiecare rând al ecranului, cu elementele separate prin spațiu. Nu uita cout << '\n' după fiecare linie.
• Construirea „în memorie”. Când enunțul cere explicit construirea matricei în memorie, umple întâi tabloul și abia apoi afișează-l, chiar dacă ai putea afișa direct valorile calculate.