Diagonalele matricei la BAC: indici și sume în C++

Într-o matrice pătratică, diagonala principală conține elementele al căror indice de linie este egal cu indicele de coloană. Diagonala secundară are o sumă constantă a celor doi indici, în funcție de convenția de numerotare. La BAC, aceste condiții permit selectarea elementelor fără să desenezi de fiecare dată matricea completă.

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

Vom folosi indici de la zero și o matrice cu același număr de linii și coloane. Vom calcula separat sumele diagonalelor și suma elementelor aflate pe cel puțin una dintre ele, numărând intersecția o singură dată. Această precizare evită o eroare frecventă în problemele de BAC.

Convenția indicilor

Pentru o matrice cu trei linii și trei coloane, indicii valizi sunt zero, unu și doi. Elementul din colțul stânga-sus are ambii indici zero. Elementul din colțul dreapta-jos are ambii indici doi.

Pe diagonala principală, pozițiile sunt zero–zero, unu–unu și doi–doi. Condiția este egalitatea indicilor. Pe diagonala secundară, pozițiile sunt zero–doi, unu–unu și doi–zero. Suma indicilor este doi, adică dimensiunea micșorată cu unu.

Convenție	Diagonala principală	Diagonala secundară
Indici de la zero	i == j	i + j == n - 1
Indici de la unu	i == j	i + j == n + 1

Nu memora condiția diagonalei secundare fără convenție. Verifică un colț: pe prima linie, diagonala secundară trebuie să treacă prin ultima coloană. Dacă formula nu acceptă această poziție, ai amestecat numerotările.

Un exemplu numeric

Considerăm matricea cu liniile unu–doi–trei, patru–cinci–șase și șapte–opt–nouă. Diagonala principală conține unu, cinci și nouă, iar suma este cincisprezece. Diagonala secundară conține trei, cinci și șapte, cu aceeași sumă.

Elementul cinci aparține ambelor diagonale. Dacă aduni cele două sume, îl numeri de două ori. Suma elementelor aflate pe cel puțin una dintre diagonale este douăzeci și cinci, nu treizeci.

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

Pozițiile, nu valorile numerice, decid apartenența la diagonală. Dacă ai înlocui cinci cu minus o sută, elementul ar rămâne la intersecție. Algoritmul trebuie să compare indicii, nu să caute un tipar în valorile matricei.

Când se intersectează diagonalele într-o celulă

O celulă comună trebuie să respecte simultan egalitatea indicilor și suma lor egală cu dimensiunea minus unu. Prin înlocuire, dublul indicelui trebuie să fie dimensiunea minus unu.

Există un indice întreg potrivit atunci când dimensiunea este impară. Pentru dimensiunea cinci, centrul are indicii doi și doi. Pentru dimensiunea patru, diagonalele se încrucișează geometric între celule, dar nu au un element comun.

De aceea, adunarea sumelor diagonalelor cere scăderea centrului numai pentru dimensiune impară, dacă vrei reuniunea fără repetare. O alternativă mai directă este să selectezi fiecare celulă prin condiția „pe diagonala principală sau pe diagonala secundară” și să o aduni o singură dată.

Program C++ complet

Programul citește dimensiunea între unu și o sută, apoi elementele matricei linie cu linie. Valorile sunt întregi, de cel mult un miliard în valoare absolută. Afișează suma diagonalei principale, suma diagonalei secundare și suma reuniunii lor.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long principala = 0, secundara = 0, reuniune = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long x;
            cin >> x;
            if (i == j) principala += x;
            if (i + j == n - 1) secundara += x;
            if (i == j || i + j == n - 1) reuniune += x;
        }
    }
    cout << principala << ' ' << secundara << ' ' << reuniune;
    return 0;
}

Pentru sumele separate, cele două condiții sunt independente. Centrul trebuie să intre în ambele sume, fiindcă aparține fiecărei diagonale. Pentru reuniune, disjuncția duce la o singură adunare, chiar dacă ambele condiții sunt adevărate.

Un lanț care ar folosi numai o ramură alternativă pentru cele două sume separate ar putea omite centrul din una dintre ele. Structura condițiilor trebuie aleasă după rezultatul calculat, nu după aspectul vizual al diagonalelor.

De ce programul nu memorează matricea

Pentru aceste sume, fiecare valoare poate fi prelucrată imediat ce este citită. Indicii de linie și coloană sunt cunoscuți din bucle. După actualizarea sumelor, valoarea nu mai este necesară.

Prin urmare, programul folosește memorie suplimentară constantă. Timpul este pătratic în dimensiunea matricei, deoarece trebuie citite toate elementele oferite în intrare. Chiar dacă diagonalele conțin numai un număr liniar de elemente, datele complete ale matricei trebuie parcurse pentru a ajunge la ele în fluxul de citire.

Dacă matricea ar fi deja memorată, poți calcula fiecare sumă diagonală printr-o singură parcurgere a liniilor și accesarea coloanei potrivite. Atunci calculul sumelor, separat de citirea inițială, este liniar. Precizează ce etapă analizezi când discuți eficiența.

Zonele de lângă diagonale

Deasupra diagonalei principale, indicele de linie este mai mic decât cel de coloană. Sub diagonala principală, este mai mare. Pentru diagonala secundară, condițiile folosesc suma indicilor comparată cu dimensiunea minus unu.

În convenția de la zero, celulele de deasupra diagonalei secundare au suma indicilor mai mică decât acea limită, iar cele de dedesubt o au mai mare. Verifică afirmația pe colțul stânga-sus și pe colțul dreapta-jos.

Când se cere o zonă aflată simultan față de două diagonale, combini condițiile prin conjuncție. Pentru apartenența la cel puțin una dintre două linii sau zone, folosești disjuncția. Desenează o matrice mică înainte de cod, pentru a lega condițiile de înțelegerea selecției.

Exerciții cu răspunsuri

O matrice de dimensiune unu conține valoarea șapte. Ambele sume diagonale sunt șapte, iar suma reuniunii este tot șapte. Acest test verifică tratarea centrului fără dublare.

O matrice de dimensiune doi are liniile unu–doi și trei–patru. Suma principală este cinci, suma secundară este cinci, iar reuniunea are suma zece. Nu există element comun între diagonale.

Pentru dimensiunea cinci, ce coloană aparține diagonalei secundare pe linia de indice unu? Coloana de indice trei, deoarece suma trebuie să fie patru. Nu folosi coloana patru doar fiindcă este aproape de marginea dreaptă.

Celula cu indicii doi și patru într-o matrice de dimensiune șapte aparține diagonalei secundare? Da, fiindcă suma indicilor este șase. Nu aparține diagonalei principale, deoarece indicii diferă.

Câte elemente distincte se află pe cele două diagonale? Pentru dimensiune pară, de două ori dimensiunea. Pentru dimensiune impară, cu unu mai puțin, deoarece centrul este comun. Aceasta este o verificare a selecției, separată de suma valorilor.

Întrebări frecvente

Pot aplica aceleași formule unei matrice dreptunghiulare?

Lecția definește cele două diagonale complete pentru o matrice pătratică. Pentru o matrice dreptunghiulară, urmează exact definiția și limitele date de enunț; nu transfera automat toate proprietățile despre centru și intersecție.

De ce folosim un tip numeric mai larg pentru sume?

Suma poate depăși capacitatea tipului folosit pentru un singur element. Limitele dimensiunii și valorilor trebuie analizate împreună. În program, tipul ales acoperă domeniul declarat.

Cum verific rapid o condiție de diagonală?

Testează colțurile, centrul când există și o celulă vecină care nu trebuie acceptată. Pentru corectarea unor formule de indici, poți exersa pe tabele mici la meditații de informatică.