Matrici (tablouri bidimensionale)

Introducere

După ce v-ați obișnuit cu tablourile unidimensionale, a venit timpul să generalizăm lucrurile și pentru tablourile bidimensionale (cunoscute colocvial ca matrici) și cele cu mai multe dimensiuni.

O matrice este, în esență, un vector de vectori. În memorie, matricea este stocată astfel încât liniile să fie plasate una după alta în ordine consecutivă.

De-a lungul acestui articol, vom discuta diferite moduri de a parcurge matricile, precum și elemente care apar des în exerciții probleme și cum să le identificați cu ușurință în diverse contexte. Ulterior, vom discuta și tehnici mai avansate, care pot fi utile atunci când aveți de lucrat în contexte mai dificile, precum și tablourile multidimensionale.

Declararea, parcurgerea și umplerea matricilor statice

În C++, matricele pot fi declarate în două moduri:

• Forma clasică, specifică limbajului C.
• Variante moderne bazate pe biblioteci din STL (abordată într-un articol separat).

În acest articol, ne concentrăm pe matricile statice, adică matrici care au dimensiuni fixe și nu pot fi extinse.

Declarație și structură

Pentru declararea unei matrice statice, aveți nevoie de:

1. Tipul de date al elementelor (e.g., int, float).
2. Dimensiunile matricei.

--8 < --"cppintro/matrices/matrices01.cpp"

Aceasta definește o matrice cu 101 linii și 101 coloane, fiecare element fiind de tip int. Indicii sunt numerotați de la 0 la 100.

Următoarea matrice are 5 rânduri și 8 coloane și este indexată de la 0. Pentru a accesa elementul de pe al treilea rând și a cincea coloană, folosim matrice[2][4]. Așa ar arăta pe matricea noastră:

--8 < --"cppintro/matrices/matrices02.cpp"

În acel caz, matricea va fi stocată astfel:

Parcurgere și atribuire de valori

Valorile matricei pot fi accesate și modificate similar cu variabilele obișnuite, utilizând indicii.

--8 < --"cppintro/matrices/matrices03.cpp"

Pentru a parcurge elementele, de regulă se folosesc structuri repetitive imbricate.

--8 < --"cppintro/matrices/matrices04.cpp"

Problemă exemplu - sumapare2 de pe pbinfo

Problema presupune citirea unei matrice și calcularea sumei tuturor elementelor pare din ea. Soluția poate fi implementată astfel:

--8 < --"cppintro/matrices/matrices05.cpp"

Matrici pătratice

În acest caz, folosim pentru ambele dimensiuni o singură variabilă. De obicei se folosește n, însă în acest articol vom folosi dim (de la dimensiune). Așa arată una:

Într-o matrice pătratică avem diagonale. Distingem două diagonale:

• Diagonala principală este diagonala care începe din colțul stânga-sus și se termină în colțul dreapta-jos.
• Diagonala secundară este diagonala care începe din colțul dreapta-sus și se termină în cel stânga-jos.

Următoarea poză arată diagonala principală a matricei de mai sus:

Elementele care aparțin acestei diagonale se află la (0, 0), (1, 1), (2, 2), (3, 3), (4, 4). De aici, putem deriva faptul că elementele diagonalei principale sunt cele pentru care rândul coincide cu coloana. Asta ne permite să scriem următorul cod care parcurge diagonala principală:

--8 < --"cppintro/matrices/matrices06.cpp"

Din moment ce rândul coincide cu coloana, putem scăpa de al doilea for, pentru a obține acest cod:

--8 < --"cppintro/matrices/matrices07.cpp"

Același lucru se aplică pentru indexarea de la 1, doar că va fi for (int i = 1; i <= dim; ++i).

Pentru matricea noastră, așa va arăta diagonala secundară:

Elementele care aparțin acestei diagonale se află la (0, 4), (1, 3), (2, 2), (3, 1), (4, 0). Remarcăm că dacă adunăm rândul și coloana, obținem 4, care este cu unu mai mic decât dimensiunea matricei. Asta ne permite să scriem următorul cod care parcurge diagonala secundară:

--8 < --"cppintro/matrices/matrices08.cpp"

La fel ca în cazul diagonalei principale, putem folosi un singur for. Din condiția de mai sus putem scoate c. Mai exact, putem muta r în partea cealaltă pentru a obține c == dim - r + 1. Acum putem scrie codul:

--8 < --"cppintro/matrices/matrices09.cpp"

Dacă matricea este indexată de la 1, atunci atât r, cât și c vor avea un 1 în plus, așadar condiția devine r - 1 + c - 1 == dim - 1 sau r + c == dim + 1, sau c == dim - r + 1. Pentru indexare de la 1, așa va arăta codul:

--8 < --"cppintro/matrices/matrices10.cpp"

Cu indexarea la 0, scădem 1, iar cu indexare de la 1, adăugăm 1.

Firește, dacă avem o diagonală, putem vorbi și despre elementele de deasupra sau de sub ea.

Așa arată elementele de deasupra, respectiv de sub diagonala principală:

Așa arată elementele de deasupra, respectiv de sub diagonala secundară:

Indicii urmează următoarele reguli:

Este ușor să țineți minte următoarea regulă: deasupra e mai mic, sub e mai mare.

Intersecția acestor regiuni formează patru regiuni: de nord, sud, vest și est. Elementele din aceste regiuni sunt determinate de aceste condiții:

• Nord:
  • Deasupra diagonalei principale și deasupra diagonalei secundare.
  • Formula: r < c && r + c < dim - 1.
• Sud:
  • Sub diagonala principală și sub diagonala secundară.
  • Formula: r > c && r + c > dim - 1.
• Vest:
  • Sub diagonala principală și deasupra diagonalei secundare.
  • Formula: r > c && r + c < dim - 1.
• Est:
  • Deasupra diagonalei principale și sub diagonala secundară.
  • Formula: r < c && r + c > dim - 1.

Generări de matrice

Multe probleme ce implică matrici, în special cele întâlnite la examenele de bacalaureat și admitere, necesită generarea și construcția de matrici specifice. În această secțiune, vom prezenta câteva exerciții și probleme rezolvate, oferind explicații clare și optimizări acolo unde este cazul.

O listă foarte bună cu probleme suplimentare de acest tip se găsește aici.

Exercițiu adaptat dintr-un model al examenului de bacalaureat

2 2 2 2 2 2 2
2 2 2 2 2 2 2
2 2 2 2 2 2 2
2 2 2 2 2 2 2
2 2 2 4 2 2 2
2 2 4 4 4 2 2
2 4 4 4 4 4 2

Pentru a rezolva acest exercițiu, putem observa faptul că toată matricea este umplută cu 2, cu excepția regiunii de sud unde avem 4. La problemele de bacalaureat de obicei indexarea este de la 1, așa că vom urma și noi această regulă.

--8 < --"cppintro/matrices/matrices11.cpp"

Problemă exemplu - genmat25 de pe pbinfo

Pentru a rezolva această problemă, trebuie să urmăm cu atenție instrucțiunile din enunț, în ordinea în care sunt date. Ulterior, vom afișa matricea rezultată.

--8 < --"cppintro/matrices/matrices12.cpp"

Problemă exemplu - genmat23 de pe pbinfo

Pentru a rezolva această problemă, vom vrea să aflăm pentru fiecare poziție distanța față de marginea matricii și apoi vom colora pătratele cu 0 sau 1 după caz.

--8 < --"cppintro/matrices/matrices13.cpp"

Problemă exemplu - zona1 de pe pbinfo

Această problemă se concentrează pe zona de sud a matricii. După ce parcurgem elementele matricii, le vom adăuga într-un vector de frecvență pentru a obține răspunsul cerut.

--8 < --"cppintro/matrices/matrices14.cpp"

Problemă exemplu - diagonal de pe nerdarena

Aici, vrem să ne folosim de structura matricii pentru a procesa diagonalele, de jos în sus și de la stânga la dreapta. Mai întâi, mergem prin punctele de pe prima coloană și apoi cele de pe prima linie, iar pentru diagonala secundară, punctele de pe prima linie și apoi cele de pe ultima coloană. Indiferent de parcurgere, vom merge în jos ulterior.

--8 < --"cppintro/matrices/matrices15.cpp"

Alte parcurgeri și modificări în matrice

Parcurgerea în spirală

Parcurgerea matricii în spirală este un tip de cerință ce apare des în problemele de informatică și este de multe ori, un tip de cerință care pun mari dificultăți celor care vor să devină mai pricepuți la implementare.

Există foarte multe moduri de a implementa corect algoritmul de parcurgere în spirală, dar aici ne vom concentra pe două dintre variante.

Varianta 1 - acoperim fiecare zonă concentrică

O primă variantă constă în a simula cele patru mutări pentru fiecare zonă concentrică și să folosim bucle imbricate pentru a avea scrise parcurgerile.

Cu alte cuvinte, acoperim fiecare zonă colorată diferit în imaginea de mai jos și începem mereu de pe linia și coloana i.

Aici puteți găsi implementarea din limbajul C++ a soluției pentru problema spirala de pe pbinfo care folosește această tehnică.

--8 < --"cppintro/matrices/matrices16.cpp"

Varianta 2 - folosind vectori de direcție

O variantă alternativă este aceea de a observa modul în care se execută mișcările de către algoritmul explicat la primul pas.

Vom lua drept exemplu n = 4.

• 4 pași la dreapta
• 3 pași în jos
• 3 pași la stânga
• 2 pași în sus
• 2 pași la dreapta
• 1 pas în jos
• 1 pas la stânga

Se poate observa faptul că după ce facem primul pas și avem n mutări, lungimile mutărilor se repetă câte două, astfel putem folosi vectorii de direcție pentru a implementa aceste mutări foarte ușor, fără mari probleme.

Aici puteți găsi implementarea din limbajul C++ a soluției pentru problema spirala de pe pbinfo care folosește această tehnică.

--8 < --"cppintro/matrices/matrices17.cpp"

Transpunerea elementelor în matrice

În unele probleme, suntem nevoiți să rotim matricea pentru a lucra mai ușor cu ea.

De obicei, cele mai frecvente rotații sunt cele la stânga sau la dreapta, dar avem de-a face și cu alte tipuri de mișcări, precum transpozițiile sau oglindirea valorilor.

Se poate observa faptul că după o rotire a matricii cu 90°, prima linie va deveni prima coloană scrisă invers, a doua coloană va deveni a doua coloană scrisă invers ș.a.m.d.

Aici se poate găsi soluția problemei rotire de pe pbinfo, unde trebuie să rotim matricea la stânga cu 90°.

--8 < --"cppintro/matrices/matrices18.cpp"

Bordarea unei matrici

Pentru a borda o matrice, putem să marcăm cu o valoare care să ne marcheze faptul că nu vrem să trecem prin acele poziții (de exemplu, -1).

--8 < --"cppintro/matrices/matrices19.cpp"

Căutarea unor elemente și secvențe în matrici

Pentru a căuta elementele în matrici, vom procesa mai mult sau mai puțin ca la vectori, putând aplica algoritmii învățați la vectori și pentru matrici.

O tehnică care merită știută este aceea că în cazul multor probleme, dacă vrem să alegem o submatrice cu o anumită proprietate, de multe ori este optim să fixăm linia de început și de final, iar mai apoi să procesăm valorile dintre cele două linii presupunând că acestea formează un vector, ulterior aplicând tehnicile și algoritmii învățați la vectori.

Un astfel de exemplu de problemă este Submatrix SumMax, discutată în articolul cu secvențe.

Tablouri multidimensionale

În general, când vine vorba de tablouri cu mai multe dimensiuni, putem să le declarăm fie la fel cum declarăm matricile, fie folosind variantele din STL, care vor fi detaliate în articolul corespunzător.

De exemplu, int v[101][101][101]; reprezintă un "cub" de dimensiuni $101 \times 101 \times 101$. La fel ca la celelalte tablouri, cu cât avem mai multe dimensiuni, cu atât cantitatea de memorie crește, iar în cele mai multe cazuri, nu vom avea nevoie de mai mult de 3-4 dimensiuni.

Concluzii

Lucrul cu matrici și tablouri multidimensionale este un pas înainte pentru aprofundarea principiilor programării în oricare limbaj de programare. Foarte mulți algoritmi pe matrici sunt aplicați în diverse moduri și așa cum se poate vedea în metodele de mai sus, aplicațiile sunt foarte răspândite.

Probleme suplimentare

• cntlinii pbinfo
• ordlin pbinfo
• lincol pbinfo
• chenar pbinfo
• zone1 pbinfo
• serpuire pbinfo
• spirala1 pbinfo
• spirala2 pbinfo
• eroziune pbinfo
• memory001 pbinfo
• OJI 2007 cartele
• infoarena mostenire2
• infoarena marmote
• Problemele recomandate în cele 4 articole de aici
• Probleme de la parcurgerea matricelor oarecare - pbinfo
• Probleme de la parcurgerea matricelor pătratice - pbinfo
• Probleme diverse cu matrici - pbinfo

Resurse suplimentare

• Tablouri bidimensionale - pbinfo
• Articolele din secțiunea tablouri bidimensionale (matrice) - CPPI Sync
• Matrici - InfoGym
• Tablouri pătratice - pbinfo