Matrici pătratice

Dacă pentru un tablou bidimensional, la o anumită rulare a programului, folosim și pentru numărul de linii și pentru numărul de coloane aceeași valoare, acesta se numește pătratic (matrice pătratică). În acest material vom studia diverse particularități care apar la astfel de tablouri. În fond, tot ce am discutat la prezentarea generală a matricelor este valabil, dar aici apar câteva lucruri noi. În tabelul de mai jos, pentru o matrice pătratică de dimensiune 7 (7 linii și 7 coloane) cu liniile și coloanele indexate de la 1, am notat doar indicii elementelor.

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

Discuția din acest material se dezvoltă în jurul faptului că, așa cum am subliniat și în figură, dacă se pleacă dintr-un colț și se avansează în diagonală, se ajunge exact în colțul opus (evident că acest lucru este valabil doar pentru că matricea este pătratică).

Ceea ce este hașurat mai sus se cheamă diagonala principală. Dacă se pleacă din colțul dreapta al liniei de sus (1,7) și se avansează în diagonală, se va ajunge în colțul stânga jos (7,1). Zona astfel parcursă se cheamă diagonala secundară.

Diagonala principală și zonele delimitate de ea


Ne vom ocupa de vizitarea elementelor din anumite zone formate. Cu elementele traversate putem realiza diverse operații dintre cele clasice (sume, produse, numărări, maxime, minime, verificări etc) dar în exemplele următoare noi vom realiza, pentru simplitate, suma.

Parcurgerea elementelor de pe diagonala principală


Observăm că elementele de pe diagonala principală au indicele de linie și cel de coloană egali. Doar ele sunt elementele din matrice cu indicii egali. Așadar o primă soluție este de a traversa toată matricea și, cu un if, selectăm doar elementele cu această proprietate.

for (i = 1;i <= n; i++)
    for (j = 1;j <= n; j++)
        if (i == j)
          sum += a[i][j];

Observăm că atât pentru linii cât și pentru coloane se merge cu indicii până la n (am considerat o matrice pătratică de dimensiune n, așa cum vom considera și în exemplele următoare).

Iată și o altă variantă de a însuma elementele de pe diagonala principală:

for (i = 1;i <= n; i++)
    sum += a[i][i];

Codul de mai sus este de asemenea corect, este mai scurt și este mai eficient (avem timp de ordin n spre deosebire de prima variantă unde timpul de executare este de ordin n 2 ). Cum am gândit pentru a ajunge la el?

Ne-am imaginat contorul de la for ca fiind linia pe care dorim să o vizităm și observăm că pe linia curentă este un singur element care ne interesează și că indicele de coloană are aceeași valoare cu acela de linie, fixat prin for.

O idee general valabilă este următoarea: dacă zona de traversat este liniară (o anume linie a matricei, o anume coloană a matricei, o anume diagonală etc) atunci vizitarea se poate face cu o singură structură repetitivă; dacă zona de traversat este ca o suprafață (matricea în sine sau o anume parte a sa dispusă pe mai multe linii și mai multe coloane), atunci vizitarea elementelor sale trebuie făcută cu două foruri, unul cu care indicăm linia pe care ne aflăm și celălalt pentru vizitarea elementelor de pe linia fixată. .

Vom vedea mai bine cele de mai sus în secțiunile următoare.

Parcurgerea elementelor din triunghiul delimitat de diagonala principală, aflate sub ea

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

Analizând tabelul cu indicii observăm că elementele aflate în zona care ne interesează au proprietatea că indicele de linie este mai mare decât cel de coloană și doar în această zonă elementele au această proprietate. Astfel, putem traversa toată matricea și, cu un if, selectăm aceste elemente. 

for (i = 1; i <= n; i++)
    for (j = 1;j <= n; j++)
        if (i > j)
            sum += a[i][j];

Codul prezentat vizitează elementele din zona aflată strict sub diagonală. Pentru a include și diagonala era suficient să schimbăm doar semnul de comparare de la condiția lui if din > în >=.

O variantă mai bună decât cea prezentată este să analizăm atent cum putem vizita doar elementele din zona care ne interesează. Am reduce astfel la jumătate timpul de executare (în zona care ne interesează sunt aproximativ jumătate dintre elementele matricei).

Observăm că liniile acoperite de elementele zonei sunt între 2 și n.

  • Pe linia 2, coloanele sunt de la 1 la 1
  • Pe linia 3, coloanele sunt de la 1 la 2
  • Pe linia 4, coloanele sunt de la 1 la 3
  • ...
  • Pe linia n coloanele sunt de la 1 la n-1.
    •

Așadar, dacă vom vizita cu primul for liniile (i fiind indicele, deci linia curentă), coloana (deci indicele j de la al doilea for) va fi între 1 și i-1.

for (i = 1;i <= n; i++)
    for (j = 1; j < i; j++)
        sum += a[i][j];

Această variantă are complexitatea teoretică în timp tot de ordin n2 , ca și prima, dar numărul efectiv de operații este mai mic (aproximativ jumătate).

Parcurgerea elementelor din triunghiul delimitat de diagonala principală, aflate deasupra ei.

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

Vom prezenta, ca și mai sus, două moduri de abordare:

  • Observăm relația dintre indici pentru elementele zonei și le selectăm cu if în timpul parcurgerii întregii matrice;
  • Fixăm cu un indice liniile cu elemente care ne interesează și variem cu alt indice coloana de pe linia curentă după ce observăm regula generală pe care o aplicăm fiecărei linii;

Varianta 1.

Elementele zonei dorite sunt cele cu indicele de linie strict mai mic decât cel de coloană

for (i = 1;i <= n;i++)
    for (j = 1;j <= n; j++)
        if (i < j)
            sum += a[i][j];

Varianta 2.

Observăm că ne interesează linii de la 1 la n-1

  • Pe linia 1 avem coloane de la 2 la n
  • Pe linia 2 avem coloane de la 3 la n
  • Pe linia 3 avem coloane de la 4 la n
  • ...
  • Pe linia n-1 avem coloane de la n la n
    •  
for (i = 1;i <= n; i++)
    for (j = i+1;j <= n; j++)
        sum += a[i][j];

n legătură cu diagonala principală și celelalte diagonale “paralele” cu ea, facem următoarele observații:

  • Am spus că pentru elementele de pe diagonala principală i=j. Acest lucru este echivalent cu i-j=0.
  • Elementele de pe paralela la diagonala principală aflate imediat sub ea au i-j=1.
  • Elementele aflate pe diagonala aflate sub cea anterioară au i-j=2.
  • În cealaltă parte, elementele diagonalei aflată imediat deasupra celei principale au i-j=-1.

În colcluzie, elementele aflate pe diagonala principală sau pe aceeași paralelă la ea au diferența indicilor constantă.

Diagonala secundară și zonele delimitate de ea

1 , 1 1 , 2 1 , 3 1 , 4 1 , 5 1 , 6 1 , 7
2 , 1 2 , 2 2 , 3 2 , 4 2 , 5 2 , 6 2 , 7
3 , 1 3 , 2 3 , 3 3 , 4 3 , 5 3 , 6 3 , 7
4 , 1 4 , 2 4 , 3 4 , 4 4 , 5 4 , 6 4 , 7
5 , 1 5 , 2 5 , 3 5 , 4 5 , 5 5 , 6 5 , 7
6 , 1 6 , 2 6 , 3 6 , 4 6 , 5 6 , 6 6 , 7
7 , 1 7 , 2 7 , 3 7 , 4 7 , 5 7 , 6 7 , 7

De data aceasta vom porni cumva invers cu observațiile și anume: pentru elementele de pe diagonala secundară suma indicilor este n+1. Uitându-ne atent se vede că pe fiecare paralelă la diagonala secundară suma indicilor este constantă. Deci pe paralela aflată imediat deasupra suma indicilor este n, pe cea aflată încă un nivel mai sus suma indicilor este n-1 etc.

Deci, pe paralelele la diagonala principală avem diferența indicilor constantă iar pe paralelele la diagonala secundară avem suma indicilor constantă. .

Parcurgerea elementelor de pe diagonala secundară

Varianta 1. Este cea neoptimă: parcurgem toată matricea și punem condiția i+j=n+1

for (i = 1;i <= n; i++)
    for (j = 1;j <= n;j++)
        if (i + j == n + 1)
            sum += a[i][j];

Varianta 2. Observăm că zona de parcurs este liniară deci trebuie să putem rezolva cu un for. Fixăm indicele acestuia ca fiind linia unde avem elemente (de la 1 la n aici) și coloana o calculăm ca find n + 1 - liniaCurenta.

for (i = 1;i <= n; i++)
    sum += a[i][n + 1 - i]; /// or a[i][n - i + 1]

Parcurgerea elementelor din triunghiul delimitat de diagonala secundară, aflate sub ea

Prima variantă se bazează pe observația că elementele acestei zone sunt cele pentru cate i+j>n+1. Așadar putem parcurge toată matricea și selectăm cu if doar aceste elemente.

for (i = 1;i <= n;i++)
    for (j = 1;j <= n; j++)
        if (i + j > n + 1)
            sum += a[i][j];

Varianta a doua, cea în care vizităm exact elementele zonei se bazează pe observația:

  • Avem elemente pe linii de la 2 la n;
  • La o anume linie i, elementele care ne interesează sunt cele aflate după cel de pe diagonala secundară de pe linia i și până la finalul liniei. Așadar, indicii sunt de la (n+1-i)+1 până la n. Am scris în scop didactic formula dar în cod scriem compact n-i+2.
for (i = 2;i <= n; i++)
    for (j = n - i + 2; j <= n; j++)
        sum += a[i][j];

Parcurgerea elementelor din triunghiul delimitat de diagonala secundară, aflate deasupra ei

Varianta 1: elementele care ne interesează sunt cele cu suma indicilor mai mică decât n+1.

for (i = 1;i <= n;i++)
    for (j = 1;j <= n;j++)
        if (i + j < n + 1)
            sum += a[i][j];

Varianta 2: facem observațiile:

  • Avem elemente pe linii de la 1 la n-1;
  • La o anume linie i, elementele care ne interesează sunt cele aflate de la începutul liniei, deci coloana 1, până înainte de cel de pe diagonala secondară, adică mergem cu coloana până la n-i.
for (i = 1; i < n; i++)
    for (j = 1; j <= n-i; j++)
        sum += a[i][j];

Probleme rezolvate

Ideile folosite la rezolvarea acestor probleme sunt unele clasice, des întâlnite în practică

1. Se citește de la tastatură un număr n. Să se construiască o matrice pătratică de dimensiune n, după următoarele reguli:

  • Elementele de pe diagonala principală să aibă valoarea 1;
  • Elementele din triunghiul de sub diagonala principală să aibă valoarea 2;
  • Elementele din triunghiul de deasupra diagonalei principale să aibă valoarea 3.

Exemplu:

Input Output
5 
1 3 3 3 3
2 1 3 3 3
2 2 1 3 3
2 2 2 1 3
2 2 2 2 1

Rezolvare:

Observăm că de data aceasta nu se mai citesc de la tastatură toate valorile unei matrice. Avem de construit una pornind de la dimensiunea sa. Întrucât avem de vizitat toate elementele se impune folosirea metodei care traversează toată matricea și care, cu if, identifică zona în care ne aflăm. Mai departe prezentăm doar secvența de cod presupunând că matricea de construit se numește a.

for (i = 1;i <= n;i++)
    for (j = 1;j <= n;j++) {
        if (i == j)
            a[i][j] = 1;
        else
            if (i > j)
                a[i][j] = 2;
            else
                a[i][j] = 3;
}

Am prezentat doar secvența de memorare de valori în matrice fără a mai afișa ulterior tabloul.

2. Se citește de la tastatură un număr n. Să se construiască o matrice pătratică de dimensiune n după regulile:

  • Elementele celor două diagonale au valoarea 1;
  • Elementele triunghiului de sus delimitat de cele două diagonale au valoarea 2;
  • Elementele triunghiului de jos delimitat de cele două diagonale au valoarea 3;
  • Elementele triunghiului din stânga delimitat de cele două diagonale au valoarea 4;
  • Elementele triunghiului din dreapta delimitat de cele două diagonale au valoarea 5;

Exemplu:

Input Output
5 
1 2 2 2 1
4 1 2 1 5
4 4 1 5 5
4 1 3 1 5
1 3 3 3 1

Solution:

Aplicăm aceeași tehnică de la problema anterioară, parcurgând toată matricea și identificând zona în care ne aflăm. Pentru zonele triunghiulare delimitate de două diagonale folosim if cu două condiții, câte o condiție pentru a indica partea de care se află elementul curent față de fiecare diagonală.

for (i = 1;i <= n; i++)
    for (j = 1;j <= n; j++) {
        if (i == j || i + j == n + 1)
            a[i][j] = 1;
        if (i < j || i + j < n + 1)
            a[i][j] = 2;
        if (i > j || i + j > n + 1)
            a[i][j] = 3;
        if (i > j || i + j < n + 1)
            a[i][j] = 4;
        if (i < j || i + j > n + 1)
            a[i][j] = 4;
}

La această problemă am ales varianta cu if-uri succesive în locul celei cu if-else-if întucât codul este mai compact.