Diagonalele și marginea unei matrice în C++

După ce poți citi o matrice, multe probleme se reduc la alegerea elementelor care respectă o condiție pe indici. De exemplu, diagonala principală are linia egală cu coloana, iar marginea cuprinde prima sau ultima linie și prima sau ultima coloană.

Înainte de lecție, parcurge tablourile bidimensionale și condițiile logice. Folosim indici de la zero și verificăm separat cazurile în care zonele se suprapun.

Diagonalele unei matrice pătratice

Pentru o matrice cu n linii și tot n coloane, diagonala principală conține elementele cu i == j. Diagonala secundară conține elementele cu i + j == n - 1. Pentru n = 3, indicii de pe diagonala secundară sunt (0, 2), (1, 1), (2, 0).

Când n este impar, diagonalele au în comun elementul central. Dacă cerința spune „suma elementelor aflate pe cel puțin una dintre diagonale”, centrul trebuie adunat o singură dată.

Condiția cu sau selectează reuniunea diagonalelor și nu dublează centrul.

Suma celor două diagonale, fără dublare

Citim n, cu 1 <= n <= 100, apoi n * n întregi între -1000000 și 1000000. Afișăm suma elementelor selectate.

Varianta cu tablou clasic

int a[100][100]{}; rezervă o capacitate de 100 de linii și 100 de coloane. Folosim numai indicii din dimensiunile citite. Acoladele inițializează elementele cu zero.

#include <iostream>

int main() {
    int n = 0;
    std::cin >> n;
    int a[100][100]{};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> a[i][j];
        }
    }
    long long suma = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j || i + j == n - 1) {
                suma += a[i][j];
            }
        }
    }
    std::cout << suma << '\n';
    return 0;
}

Varianta cu std::vector

În varianta de mai jos, fiecare linie este un std::vector<int>, iar matricea conține exact numărul citit de linii și coloane. Accesul rămâne a[i][j]; condițiile de parcurgere și rezultatul sunt aceleași.

#include <iostream>
#include <vector>

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

Pentru matricea din imagine, rezultatul este 25. Operatorul || înseamnă „sau”: dacă oricare condiție este adevărată, adunăm elementul. Corpul lui if se execută o singură dată pentru perechea de indici curentă, chiar dacă ambele condiții sunt adevărate.

Două instrucțiuni if independente, fiecare cu propria adunare, ar dubla centrul. Pentru n = 1, singurul element aparține ambelor diagonale, iar răspunsul trebuie să fie chiar valoarea lui. Acesta este un test mic care detectează imediat greșeala.

Marginea unei matrice dreptunghiulare

Marginea conține elementele care îndeplinesc cel puțin una dintre condițiile i == 0, i == n - 1, j == 0, j == m - 1. Și aici zonele se suprapun, de această dată în colțuri sau pe întreaga matrice dacă există o singură linie ori coloană.

Programul citește n și m, cu 1 <= n, m <= 100, și valori în același interval. Fiecare element de pe margine trebuie numărat o singură dată.

Varianta cu tablou clasic

int a[100][100]{}; rezervă o capacitate de 100 de linii și 100 de coloane. Folosim numai indicii din dimensiunile citite. Acoladele inițializează elementele cu zero.

#include <iostream>

int main() {
    int n = 0, m = 0;
    std::cin >> n >> m;
    int a[100][100]{};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    long long suma = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x = a[i][j];
            if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                suma += x;
            }
        }
    }
    std::cout << suma << '\n';
    return 0;
}

Varianta cu std::vector

În varianta de mai jos, fiecare linie este un std::vector<int>, iar matricea conține exact numărul citit de linii și coloane. Accesul rămâne a[i][j]; condițiile de parcurgere și rezultatul sunt aceleași.

#include <iostream>
#include <vector>

int main() {
    int n = 0, m = 0;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    long long suma = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int x = a[i][j];
            if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                suma += x;
            }
        }
    }
    std::cout << suma << '\n';
    return 0;
}

Pentru matricea de trei pe trei cu valorile de la 1 la 9, suma marginii este 40: din totalul 45 lipsește doar centrul 5. Pentru o singură linie, toate valorile sunt pe margine. Pentru o matrice de un element, îl adunăm o singură dată.

Cele două variante memorează matricea pentru a compara reprezentările. Pentru această cerință poți însă decide dacă păstrezi o valoare chiar în momentul citirii, pe baza indicilor. Dacă aduni imediat valorile de pe margine, este suficient un acumulator și nu mai ai nevoie de matrice. În alte probleme, unde ai nevoie să revizitezi vecinii, memorarea poate fi necesară.

Cost și alte regiuni

Citirea și parcurgerea matricei pătratice au timp O(n²). Varianta cu std::vector memorează n² elemente, iar tabloul clasic rezervă 100 * 100 elemente. După citire, diagonalele ar putea fi vizitate direct în O(n) pași, dar citirea tuturor datelor rămâne O(n²). Calculul marginii are timp O(n * m) și doar O(1) memorie suplimentară față de matrice. Dacă prelucrezi direct la citire, fără memorarea ei, întreaga soluție folosește spațiu suplimentar O(1).

Elementele strict deasupra diagonalei principale satisfac i < j, iar cele strict sub ea satisfac i > j. Dacă adaugi egalitatea, incluzi și diagonala. Pentru început desenează o matrice mică, scrie indicii și verifică selecția înainte să programezi condiția.

În variantele clasice, memoria rezervată este dată de capacitatea din declarație, nu de numărul de elemente folosite. În variantele cu std::vector, stocarea din aceste exemple este proporțională cu dimensiunile citite. Algoritmul și numărul de elemente prelucrate nu se schimbă între reprezentări. Inițializarea cu {} a tabloului clasic pune la zero întreaga capacitate, inclusiv pozițiile nefolosite; acest cost este separat de parcurgerea celor n elemente sau a celor n * m celule.

Exersează

1. Ce sumă a diagonalelor obții pentru o matrice de un element, -4?
2. Câte elemente distincte au diagonalele pentru n = 3? Dar pentru n = 4?
3. Care este suma marginii pentru linia 2 0 -3?
4. Ce condiție selectează interiorul unei matrice?

Răspunsuri: -4; 5, respectiv 8; -1; 0 < i && i < n - 1 && 0 < j && j < m - 1. Dacă una dintre dimensiuni este cel mult doi, interiorul este gol.

Revino la cuprinsul capitolului sau continuă cu șirurile de caractere.