Transpusa și simetria matricei la BAC: C++ explicat

Transpusa unei matrice se obține transformând liniile în coloane. La BAC, regula se traduce prin schimbarea ordinii indicilor: elementul de pe linia curentă și coloana curentă ajunge pe coloana și linia corespunzătoare. O matrice este simetrică față de diagonala principală dacă este pătratică și coincide cu transpusa ei.

Lecția privește tablourile bidimensionale, incluse în programa de referință pentru matematică-informatică. Verifică programa specializării tale când alegi subiectele de BAC pentru antrenament. Vom separa construirea transpusei de verificarea simetriei, deoarece cele două cerințe folosesc aceeași relație între poziții, dar nu cer aceeași cantitate de memorie.

Ce se întâmplă cu dimensiunile

O matrice cu două linii și trei coloane are o transpusă cu trei linii și două coloane. Numărul elementelor rămâne același. Se schimbă organizarea lor, nu valorile și nici numărul aparițiilor fiecărei valori.

Consideră prima linie unu, doi, trei și a doua linie patru, cinci, șase. Transpusa are liniile unu, patru; doi, cinci; trei, șase. Prima coloană a matricei inițiale a devenit prima linie a rezultatului.

Element inițial, indici de la zero	Valoare	Poziție în transpusă
Linia 0, coloana 0	1	Linia 0, coloana 0
Linia 0, coloana 2	3	Linia 2, coloana 0
Linia 1, coloana 0	4	Linia 0, coloana 1
Linia 1, coloana 2	6	Linia 2, coloana 1

Tabelul arată de ce nu poți păstra automat limitele buclelor atunci când afișezi rezultatul. Dacă parcurgi liniile transpusei, limita lor este numărul coloanelor inițiale.

Afișarea transpusei fără al doilea tablou

Dacă matricea inițială este deja memorată și se cere numai afișarea transpusei, nu trebuie să construiești un al doilea tablou. Parcurgi coloanele inițiale în bucla exterioară și liniile inițiale în bucla interioară.

La fiecare pas al buclei exterioare afișezi o coloană întreagă, apoi treci la linie nouă. Această ordine produce exact liniile transpusei. Datele din matricea inițială rămân disponibile pentru alte cerințe.

Programul de mai jos citește dimensiunile, apoi elementele linie cu linie. Fiecare dimensiune este între unu și o sută. După transpusă, afișează dacă matricea inițială este simetrică. Valorile sunt întregi care încap în tipul folosit.

#include <iostream>
using namespace std;

int main() {
    int n, m, a[100][100];
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> a[i][j];
    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            if (i > 0) cout << ' ';
            cout << a[i][j];
        }
        cout << '\n';
    }
    bool simetrica = (n == m);
    if (simetrica) {
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (a[i][j] != a[j][i])
                    simetrica = false;
    }
    cout << (simetrica ? "DA" : "NU");
    return 0;
}

Programul nu compară poziții inversate pentru matrice dreptunghiulare. Condiția de formă este verificată înaintea comparațiilor, deoarece indicii inversați ar putea desemna poziții care nu aparțin matricei inițiale.

Cum verifici simetria

Într-o matrice pătratică, pozițiile simetrice față de diagonala principală sunt cele cu indicii inversați. Elementul de pe linia zero și coloana doi se compară cu elementul de pe linia doi și coloana zero.

Elementele diagonalei principale sunt propriile lor corespondente. Compararea fiecăruia cu el însuși nu oferă informație nouă. De aceea, verificăm numai pozițiile aflate strict deasupra diagonalei principale.

Dacă am verifica și pozițiile de sub diagonală, fiecare pereche ar fi comparată de două ori. Rezultatul ar rămâne corect, dar demonstrația și numărul operațiilor ar fi mai puțin clare. O singură nepotrivire este suficientă pentru a respinge simetria.

Un exemplu simetric și o modificare decisivă

Consideră matricea cu liniile unu, doi, trei; doi, patru, cinci; trei, cinci, șase. Perechile din afara diagonalei sunt doi cu doi, trei cu trei și cinci cu cinci. Matricea este simetrică.

Dacă înlocuiești ultimul element al primei linii cu nouă, perechea dintre pozițiile zero, doi și doi, zero devine nouă cu trei. Matricea nu mai este simetrică, deși toate celelalte comparații reușesc.

Sumele liniilor și coloanelor nu înlocuiesc comparațiile dintre elemente. De exemplu, matricea cu liniile zero, unu, zero; zero, zero, unu; unu, zero, zero are toate sumele egale cu unu, dar nu este simetrică. Egalitatea unor totaluri poate ascunde diferențe de poziție.

Transpunerea în același tablou

Pentru o matrice pătratică, poți schimba între ele elementele fiecărei perechi aflate de o parte și de alta a diagonalei. Trebuie să parcurgi numai una dintre jumătăți, de exemplu pozițiile strict deasupra diagonalei principale.

Dacă parcurgi toate pozițiile și faci de fiecare dată schimbul cu poziția inversată, fiecare pereche este schimbată de două ori. Prima operație o transpune, iar a doua o readuce în starea inițială. Programul poate părea activ, deși rezultatul final este matricea inițială.

Această observație explică și de ce transpusa transpusei este matricea inițială. O inversare a indicilor mută elementul la poziția corespondentă; a doua inversare îl readuce. Folosește proprietatea ca verificare a unei implementări, nu ca înlocuitor al analizei limitelor.

Ce rămâne invariant

Transpunerea păstrează suma tuturor elementelor, deoarece fiecare valoare apare exact o dată înainte și după transformare. Pentru o matrice pătratică păstrează și elementele diagonalei principale pe aceleași poziții.

Suma unei linii inițiale devine suma coloanei corespunzătoare din transpusă. Această relație este mai precisă decât afirmația că toate sumele rămân pe loc. Ordinea grupurilor se schimbă odată cu orientarea lor.

Într-o rezolvare scrisă, explică transformarea folosind o poziție generală și apoi verifică un exemplu numeric. Această combinație te ajută să înțelegi algoritmul, nu doar să memorezi buclele.

Timp și memorie

Afișarea transpusei vizitează fiecare element o singură dată, deci timpul este proporțional cu produsul dimensiunilor. Verificarea simetriei unei matrice pătratice cere cel mult o comparație pentru fiecare pereche din afara diagonalei.

Programul memorează matricea inițială și folosește în plus doar indici și un indicator logic. Nu construiește o copie transpusă. Dacă datele ar veni ca flux și nu ar putea fi recitite, ordinea diferită a afișării ar impune păstrarea informației necesare.

Exerciții cu răspunsuri

O matrice are trei linii și cinci coloane. Transpusa are cinci linii și trei coloane. Matricea inițială nu este simetrică în sensul egalității cu transpusa, deoarece dimensiunile diferă.

O matrice pătratică are un singur element, minus șapte. Este simetrică. Nu există perechi distincte de verificat, iar condiția de formă este îndeplinită.

Matricea are liniile unu, doi și trei, patru. Transpusa are liniile unu, trei și doi, patru. Matricea inițială nu este simetrică, deoarece doi diferă de trei.

Întrebări frecvente

Transpusa înseamnă inversarea fiecărei linii?

Nu. Inversarea unei linii schimbă ordinea elementelor din acea linie. Transpunerea schimbă rolul liniei și coloanei pentru fiecare element și poate schimba dimensiunile matricei.

Compar diagonala secundară pentru simetrie?

Nu pentru proprietatea de matrice simetrică discutată aici. Relația standard folosește diagonala principală. O cerință despre simetria față de diagonala secundară trebuie tratată separat, cu altă transformare a indicilor.

Cum identific o eroare de indici?

Testează întâi o matrice dreptunghiulară cu valori distincte, apoi una pătratică simetrică și una cu o singură pereche diferită. Poți analiza parcurgerea împreună cu un profesor de informatică.