Transformări pe matrice

Interschimbări de linii și coloane, transpusa, rotații și parcurgerea în spirală, adică problemele de geometrie a indicilor.

Ideea comună

Problemele din această categorie nu au aproape nimic de calculat. Toată dificultatea stă în a nimeri indicii.

Sfatul care ajută cel mai mult: desenează o matrice mică, 3×3 sau 4×4, cu pozițiile numerotate, și urmărește pe ea ce se întâmplă. Cinci minute de desen te scutesc de o jumătate de oră de încercări.

Interschimbarea a două linii

for (int j = 1; j <= m; j++) {
    int aux = a[p][j];
    a[p][j] = a[q][j];
    a[q][j] = aux;
}

Se interschimbă element cu element, pe toată lățimea. La coloane e la fel, doar că indicele fixat este al doilea:

for (int i = 1; i <= n; i++) {
    int aux = a[i][p];
    a[i][p] = a[i][q];
    a[i][q] = aux;
}

Transpusa

Transpusa schimbă liniile cu coloanele: elementul de pe poziția (i, j) ajunge pe (j, i).

Pentru o matrice pătratică se poate face pe loc, dar parcurgând doar jumătate din ea:

for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
        int aux = a[i][j];
        a[i][j] = a[j][i];
        a[j][i] = aux;
    }

j pornește de la i + 1, nu de la 1. Dacă ai parcurge toată matricea, ai interschimba fiecare pereche de două ori și ai reveni la matricea inițială. Rezultatul ar fi un program care „nu face nimic".

Pentru o matrice dreptunghiulară n × m, transpusa are alte dimensiuni, deci îți trebuie o a doua matrice:

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        b[j][i] = a[i][j];
// b are m linii și n coloane

Rotația cu 90°

O rotație spre dreapta duce prima linie pe ultima coloană, a doua linie pe penultima coloană și așa mai departe:

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        b[j][n + 1 - i] = a[i][j];

Merită s-o verifici pe un colț. Elementul a[1][1] (stânga-sus) ajunge în b[1][n], adică dreapta-sus, cum trebuie la o rotație spre dreapta.

Pentru rotația spre stânga, formula devine b[n + 1 - j][i] = a[i][j].

Verifică întotdeauna o formulă de indici pe un colț. E cea mai rapidă metodă de a prinde o inversare și merge și pe hârtie, la examen.

Oglindirea

Față de o axă verticală (stânga-dreapta):

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m / 2; j++) {
        int aux = a[i][j];
        a[i][j] = a[i][m + 1 - j];
        a[i][m + 1 - j] = aux;
    }

Din nou, j merge doar până la jumătate. Pentru m impar, coloana din mijloc rămâne pe loc, și așa e corect.

Parcurgerea în spirală

Este cea mai cerută dintre parcurgerile „geometrice": pornești din colțul stânga-sus și mergi în cerc, spre interior.

Lucrezi cu patru margini, care se strâng după fiecare latură parcursă:

int sus = 1, jos = n, stanga = 1, dreapta = m;

while (sus <= jos && stanga <= dreapta) {
    for (int j = stanga; j <= dreapta; j++)      // →
        cout << a[sus][j] << " ";
    sus++;

    for (int i = sus; i <= jos; i++)             // ↓
        cout << a[i][dreapta] << " ";
    dreapta--;

    if (sus <= jos)
        for (int j = dreapta; j >= stanga; j--)  // ←
            cout << a[jos][j] << " ";
    jos--;

    if (stanga <= dreapta)
        for (int i = jos; i >= sus; i--)         // ↑
            cout << a[i][stanga] << " ";
    stanga++;
}

Cele două teste suplimentare, dinaintea laturilor a treia și a patra, sunt necesare. Când a rămas o singură linie, latura de jos ar afișa a doua oară aceleași elemente. Un astfel de detaliu îl prinzi doar testând pe o matrice 1 × 5 și pe una 5 × 1.

Cum verifici o transformare

Trei teste care prind aproape orice greșeală:

Matricea 1×1. Trebuie să rămână neschimbată.

Colțurile. Urmărește unde ajunge fiecare dintre cele patru colțuri și compară cu ce ar trebui.

Dimensiuni inegale. Multe formule merg pe matrice pătratice și greșesc pe cele dreptunghiulare. Dacă enunțul permite n ≠ m, testează explicit acest caz.

De reținut

Problema este a indicilor, nu a calculului. Desenează o matrice mică.
Transpusa pe loc parcurge doar j > i, altfel se anulează singură.
Oglindirea merge până la jumătate, din același motiv.
Verifică orice formulă de indici urmărind un colț.
La spirală, testează cazurile cu o singură linie sau coloană.