Zonele matricei la BAC: nord, est, sud și vest

Cele două diagonale ale unei matrice pătratice delimitează patru zone: nord, est, sud și vest. Pentru a selecta o zonă, combini două condiții asupra indicilor, câte una pentru fiecare diagonală. La BAC, schema te ajută să calculezi sume, numărări sau extreme fără să enumeri manual toate celulele.

Lecția despre tablouri bidimensionale se adresează profilului matematică-informatică; verifică programa specializării tale înainte să alegi exercițiile.

În această lecție, diagonalele nu fac parte din cele patru zone. Lucrăm cu indici de la zero, iar matricea are aceeași dimensiune pe linii și pe coloane. Convenția trebuie precizată înaintea formulelor, inclusiv când rezolvi un exercițiu din arhiva BAC.

Cele două repere de la care pornim

Pe diagonala principală, indicele liniei este egal cu indicele coloanei. Deasupra ei, indicele liniei este mai mic. Sub ea, indicele liniei este mai mare. Aceste relații se verifică ușor pe o celulă din colțul dreapta-sus și una din colțul stânga-jos.

Pe diagonala secundară, suma indicilor este egală cu dimensiunea minus unu. Deasupra ei, suma este mai mică, iar dedesubt este mai mare. Pentru colțul stânga-sus, suma este zero; pentru colțul dreapta-jos, suma este de două ori dimensiunea minus doi.

O singură inegalitate selectează o jumătate a matricei, nu una dintre cele patru zone. Pentru o zonă trebuie îndeplinite simultan două relații. Aceasta este ideea principală a schemei.

Tabelul celor patru zone

Notăm cu i indicele liniei, cu j indicele coloanei și cu n dimensiunea. Condițiile stricte exclud elementele diagonalelor.

Zonă	Față de diagonala principală	Față de diagonala secundară	Condiție combinată
Nord	Deasupra	Deasupra	i < j && i + j < n - 1
Est	Deasupra	Dedesubt	i < j && i + j > n - 1
Sud	Dedesubt	Dedesubt	i > j && i + j > n - 1
Vest	Dedesubt	Deasupra	i > j && i + j < n - 1

Conjuncția înseamnă că ambele condiții trebuie să fie adevărate. Dacă o înlocuiești cu disjuncția, vei accepta și celule care îndeplinesc doar una dintre relații, extinzând selecția dincolo de zona dorită.

Pentru o matrice de dimensiune cinci, celula de pe linia zero și coloana doi este în nord. Linia doi și coloana patru descriu o celulă din est. Linia patru și coloana doi sunt în sud, iar linia doi și coloana zero sunt în vest.

Exemplu numeric complet

Considerăm o matrice de dimensiune cinci, completată pe linii cu valorile de la unu la douăzeci și cinci. Prima linie conține unu până la cinci, a doua șase până la zece, iar ultima douăzeci și unu până la douăzeci și cinci.

Zonă	Valorile selectate	Sumă
Nord	2, 3, 4, 8	17
Est	10, 14, 15, 20	59
Sud	18, 22, 23, 24	87
Vest	6, 11, 12, 16	45

Valorile de pe diagonale nu apar în tabel. De exemplu, unu și cinci sunt în colțuri aflate pe diagonale, iar treisprezece este centrul comun. Faptul că o valoare este aproape vizual de o zonă nu o include automat în acea zonă.

Suma celor patru rezultate este 208. Poți verifica și prin scăderea sumei reuniunii diagonalelor din suma tuturor elementelor. Această verificare independentă este utilă pentru a descoperi o zonă omisă sau numărată de două ori.

Program C++ pentru sumele zonelor

Programul citește o dimensiune între unu și o sută, apoi matricea linie cu linie. Elementele sunt întregi de cel mult un miliard în valoare absolută. Afișează sumele în ordinea nord, est, sud, vest.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long nord = 0, est = 0, sud = 0, vest = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long x;
            cin >> x;
            if (i < j && i + j < n - 1) nord += x;
            else if (i < j && i + j > n - 1) est += x;
            else if (i > j && i + j > n - 1) sud += x;
            else if (i > j && i + j < n - 1) vest += x;
        }
    }
    cout << nord << ' ' << est << ' ' << sud << ' ' << vest;
    return 0;
}

Ramurile sunt exclusive, deoarece o celulă din afara diagonalelor aparține unei singure zone. O celulă de pe o diagonală nu trece niciuna dintre condiții și nu este adunată. Nu este necesară o ramură care să adune automat tot ce a rămas într-o anumită zonă.

Tipul sumelor trebuie să acopere acumularea mai multor elemente. Alegerea lui se face din dimensiune și limita valorilor, nu doar din tipul unui singur element. Programul folosește un tip suficient pentru domeniul declarat.

Cum verifici o formulă fără să o memorezi

Alege o celulă reprezentativă din zona dorită și înlocuiește indicii în cele două relații. Pentru nord într-o matrice de dimensiune cinci, poziția zero–doi verifică atât faptul că zero este mai mic decât doi, cât și faptul că suma doi este mai mică decât patru.

Apoi testează o celulă de pe fiecare diagonală. Ea trebuie respinsă dacă enunțul exclude diagonalele. În final, testează o celulă dintr-o zonă vecină, care îndeplinește numai una dintre condițiile tale.

Acești trei pași verifică interiorul, frontiera și exteriorul selecției. Ei sunt mai puternici decât verificarea unei singure celule favorabile și pun în practică învățarea prin înțelegere.

Dacă diagonalele trebuie incluse

Înlocuirea unei inegalități stricte cu una care permite egalitatea include o frontieră. Dar dacă vrei să aduni separat mai multe zone închise, celulele de pe frontiere pot ajunge în mai multe sume.

Nu există o singură convenție obligatorie pentru asemenea cerințe. Enunțul trebuie să spună dacă frontierele sunt incluse și dacă o celulă comună se numără de mai multe ori sau o singură dată. Programul se adaptează acelei definiții.

Centrul unei matrice de dimensiune impară merită verificat separat, fiindcă aparține ambelor diagonale. Dacă ai înlocuit mecanic toate comparațiile stricte cu unele nestricte, poți ajunge să îl accepți în toate cele patru zone.

Numărarea și extremele dintr-o zonă

Pentru numărarea elementelor unei zone, înlocuiești adunarea valorii cu mărirea unui contor. Pentru suma doar a elementelor pozitive din nord, adaugi și condiția asupra valorii. Condiția geometrică și proprietatea numerică trebuie ambele respectate.

Pentru minim sau maxim, verifică dacă zona poate fi goală. La dimensiunea unu sau doi, zonele stricte din această lecție nu conțin elemente. Nu poți inițializa o extremă cu un element arbitrar al matricei, deoarece acela poate fi pe diagonală și exclus.

Un indicator pentru existența primului candidat rezolvă această problemă. Inițializezi extrema când întâlnești prima celulă acceptată și o compari cu celelalte. La final, tratezi absența conform cerinței.

Exerciții cu răspunsuri

Într-o matrice de dimensiune șapte, celula unu–trei este în nord? Da. Primul indice este mai mic, iar suma patru este mai mică decât șase.

În aceeași matrice, celula doi–patru este în est? Nu. Suma indicilor este șase, deci celula aparține diagonalei secundare și este exclusă din zonele stricte.

Într-o matrice de dimensiune trei, câte celule are fiecare zonă? Câte una: mijlocul fiecărei laturi. Colțurile și centrul sunt pe diagonale.

Dacă toate elementele sunt unu, ce reprezintă sumele zonelor? Numărul celulelor din fiecare zonă. Acesta este un test util pentru condițiile de selecție, deoarece valorile nu complică verificarea.

Întrebări frecvente

Pot folosi formulele cu indici de la unu?

Da, dar limita pentru suma indicilor devine dimensiunea plus unu. Relațiile dintre indicele liniei și cel al coloanei rămân aceleași. Verifică din nou colțurile după schimbarea convenției.

De ce nu există o ramură finală simplă pentru vest?

O asemenea ramură ar primi și celulele diagonalelor, dacă nu au fost excluse anterior. Condiția explicită păstrează definiția exactă a zonei și face verificarea mai ușoară.

Cum exersez eficient?

Desenează o matrice mică, marchează diagonalele și clasifică fiecare celulă rămasă. Abia apoi calculează sume. Pentru feedback pe condițiile tale, poți lucra la meditații de informatică.