Ce vei învăța astăzi?
După această lecție vei înțelege cum se parcurge o matrice în mod recursiv, vei scrie subprogramul recursiv pentru suma elementelor și vei aplica parcurgerea liniilor și coloanelor în probleme concrete.
Ce este o matrice și cum o parcurgem recursiv?
Definiție: O matrice este o structură de date bidimensională, organizată pe linii și coloane, declarată în C++ ca a[n][m]. Un element se accesează cu a[i][j], unde i este numărul liniei și j numărul coloanei.
Parcurgerea recursivă a unei matrice descompune problema în subprobleme mai mici: parcurgem prima linie, apoi restul matricei fără prima linie; sau parcurgem primul element al liniei, apoi restul liniei.
Analogia: caietul de matematică cu pătrățele
Imaginează-ți un caiet de matematică: fiecare pagină are un tabel de pătrățele, organizate pe rânduri (linii) și coloane. Pentru a parcurge toate pătrățelele, citim întâi întreg primul rând, apoi trecem la rândul următor, și tot așa până la capătul paginii.
Este o linie a matricei, parcursă recursiv coloană cu coloană
Este matricea, parcursă recursiv linie cu linie
Este pasul recursiv: reia parcurgerea cu linia i + 1
| Element | Rol | Exemplu |
|---|---|---|
| n, m | Numărul de linii și coloane | int a[101][101] |
| i, j | Poziția curentă (linie, coloană) | a[i][j] |
| i == n | Cazul de bază: s-au parcurs toate liniile | if (i == n) return 0; |
| j == m | S-a terminat linia, trecem la linia următoare | suma(a, n, m, i + 1, 0) |
Suma elementelor unei matrice - recursiv
Definiția recursivă: suma elementelor unei matrice cu n linii și m coloane se calculează adunând elementele primei linii cu suma elementelor matricei rămase: suma_matrice(a, n, m, i, j) parcurge poziția (i, j), avansează pe coloană, iar la capătul liniei trece la linia următoare.
Cazul de bază este i == n (s-au parcurs toate liniile), când suma este 0.
#include <iostream>
using namespace std;
// Pasul 1: definim functia recursiva pentru suma elementelor matricei
int suma_matrice(int a[][101], int n, int m, int i, int j)
{
// Pasul 2: cazul de baza - s-au parcurs toate liniile
if (i == n)
return 0;
// Pasul 3: s-a terminat linia curenta, trecem la linia urmatoare
if (j == m)
return suma_matrice(a, n, m, i + 1, 0);
// Pasul 4: pasul recursiv - adunam elementul curent si continuam pe coloana
return a[i][j] + suma_matrice(a, n, m, i, j + 1);
}
int main()
{
int n, m, a[101][101];
// Pasul 5: citim dimensiunile matricei
cout << "n = ";
cin >> n;
cout << "m = ";
cin >> m;
// Pasul 6: citim elementele matricei
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
// Pasul 7: apelam functia si afisam rezultatul
cout << "Suma = " << suma_matrice(a, n, m, 0, 0);
return 0;
}
Exemplu verificat
Pentru matricea:
1 2 3 4 5 6
Suma = 1 + 2 + 3 + 4 + 5 + 6 = 21. Parcurgerea: (0,0) → (0,1) → (0,2), apoi j == m, trecem la linia 1: (1,0) → (1,1) → (1,2), apoi i == n, ne oprim.
Ordinea apelurilor pentru matricea 2 × 3
i, jParcurgerea liniilor: afișarea recursivă a matricei
Pentru afișarea matricei folosim două funcții recursive imbricate (funcții care se apelează una din cealaltă): afiseaza_matrice parcurge liniile, iar pentru fiecare linie apelează afiseaza_linie, care parcurge coloanele. Astfel, problema „afișează matricea" se descompune în problema mai simplă „afișează o linie", apoi „afișează restul liniilor".
#include <iostream>
using namespace std;
// Pasul 1: functia care afiseaza o singura linie, recursiv, coloana cu coloana
void afiseaza_linie(int a[][101], int m, int i, int j)
{
// Pasul 2: cazul de baza - s-au parcurs toate coloanele liniei
if (j == m)
return;
// Pasul 3: afisam elementul curent si trecem la coloana urmatoare
cout << a[i][j] << " ";
afiseaza_linie(a, m, i, j + 1);
}
// Pasul 4: functia care parcurge liniile matricei
void afiseaza_matrice(int a[][101], int n, int m, int i)
{
// Pasul 5: cazul de baza - s-au parcurs toate liniile
if (i == n)
return;
// Pasul 6: afisam linia curenta, apoi restul liniilor
afiseaza_linie(a, m, i, 0);
cout << endl;
afiseaza_matrice(a, n, m, i + 1);
}
int main()
{
int n, m, a[101][101];
// Pasul 7: citim dimensiunile si elementele matricei
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
// Pasul 8: afisam matricea folosind functiile recursive
afiseaza_matrice(a, n, m, 0);
return 0;
}
De reținut
- Matricea se parcurge întâi pe linii, apoi pe coloane; ordinea celor două bucle (sau a celor două apeluri recursive) este esențială.
- O matrice se declară cu dimensiunea maximă cunoscută:
a[101][101]pentru valori de până la 100. - Transmiterea matricei la o funcție se face cu
int a[][101]; numărul de coloane trebuie precizat. - Adâncimea stivei este n + m apeluri, deci parcurgerea recursivă este sigură pentru matrice de dimensiuni obișnuite.
Exercițiu de completare
Completează enunțul despre matrice cu cuvintele potrivite:
O matrice este o structură de date ______, organizată pe linii și ______. Elementul de pe linia i și coloana j se accesează cu ______. Parcurgerea recursivă se face întâi pe ______, apoi pe coloane. Cazul de bază pentru parcurgerea liniilor este ______.
Bancă de cuvinte:
Exercițiu de completare
Completează funcția recursivă pentru suma elementelor unei matrice:
Bancă de cuvinte:
Test de înțelegere
Test rapid - matrice recursive:
1. Cazul de bază pentru parcurgerea liniilor unei matrice este:
2. La capătul unei linii (j == m), funcția de sumă:
3. Transmiterea matricei la o funcție în C++ se face:
Aprofundare
Variante de parcurgere. Funcția de sumă poate parcurge matricea și pe coloane: se parcurge întâi coloana 0, apoi coloanele următoare. Ambele variante sunt corecte; alegerea depinde de problema concretă (de exemplu, prelucrarea diagonalelor impune un alt tip de parcurgere).
Prelucrări derivate. Aceeași schemă de parcurgere se adaptează la: numărarea elementelor pare, maximul unei matrice, verificarea dacă matricea este „pătrată magică" sau sortarea elementelor pe linii. Funcția poate primi un parametru suplimentar care păstrează rezultatul parțial, exact ca la inversul unui număr.
Adâncimea stivei. Numărul maxim de apeluri impuse simultan este n + m (pentru parcurgerea linie cu linie), spre deosebire de n · m, cât ar fi prin descompunere completă. Pentru matrice de dimensiuni obișnuite (sub 100 × 100), stiva suportă fără probleme această adâncime.
Recursivitate cu două funcții imbricate. Pentru afișare, funcția afiseaza_linie este apelată de afiseaza_matrice pentru fiecare linie; fiecare apel pe linie își construiește propriul lanț de apeluri pe coloane, demonstrând cum se compun două recurențe independente.
PbInfo - Suma elementelor unei matrice
Enunț:
Cerință: Se citesc n, m și elementele unei matrice cu n linii și m coloane. Să se afișeze suma tuturor elementelor matricei, folosind un subprogram recursiv de parcurgere.
Date de intrare:
Programul citește de la tastatură numerele n și m, apoi n linii cu câte m numere naturale.
Date de ieșire:
Programul va afișa pe ecran suma elementelor matricei.
Restricții și precizări:
1 ≤ n, m ≤ 100, elemente numere naturale mai mici decât 1000. Suma se încadrează în int.
Exemplu:
Intrare:
2 3 1 2 3 4 5 6
Ieșire:
21
Cum gândim soluția:
- Definim funcția recursivă
suma_matrice(a, n, m, i, j) - Cazul de bază: dacă
i == n, întoarcem 0 - Dacă
j == m, trecem la linia următoare cusuma_matrice(a, n, m, i + 1, 0) - Întoarcem
a[i][j] + suma_matrice(a, n, m, i, j + 1)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int suma_matrice(int a[][101], int n, int m, int i, int j)
{
if (i == n)
return 0;
if (j == m)
return suma_matrice(a, n, m, i + 1, 0);
return a[i][j] + suma_matrice(a, n, m, i, j + 1);
}
int main()
{
int n, m, a[101][101];
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
cout << suma_matrice(a, n, m, 0, 0);
return 0;
}
Ce învățăm: matricea se parcurge în ordine lexicografică (i, j): se epuizează coloanele liniei curente, apoi se trece la linia următoare, deci fiecare element este adunat o singură dată.
PbInfo - Afișarea matricei recursiv
Enunț:
Cerință: Se citesc n, m și elementele unei matrice. Să se afișeze matricea, linie cu linie, elementele fiecărei linii fiind separate prin câte un spațiu, folosind exclusiv subprograme recursive.
Date de intrare:
Programul citește de la tastatură numerele n și m, apoi n linii cu câte m numere naturale.
Date de ieșire:
Programul va afișa matricea, câte o linie pe fiecare rând al ecranului.
Restricții și precizări:
1 ≤ n, m ≤ 100. Rezolvarea trebuie făcută cu două subprograme recursive: unul pentru linii, unul pentru coloane.
Exemplu:
Intrare:
2 3 1 2 3 4 5 6
Ieșire:
1 2 3 4 5 6
Cum gândim soluția:
- Definim
afiseaza_linie(a, m, i, j)care afișează o linie, coloană cu coloană - Definim
afiseaza_matrice(a, n, m, i)care parcurge liniile și apeleazăafiseaza_linie - După fiecare linie afișăm
endlpentru a trece la rândul următor - Apelăm
afiseaza_matrice(a, n, m, 0)din main
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
void afiseaza_linie(int a[][101], int m, int i, int j)
{
if (j == m)
return;
cout << a[i][j] << " ";
afiseaza_linie(a, m, i, j + 1);
}
void afiseaza_matrice(int a[][101], int n, int m, int i)
{
if (i == n)
return;
afiseaza_linie(a, m, i, 0);
cout << endl;
afiseaza_matrice(a, n, m, i + 1);
}
int main()
{
int n, m, a[101][101];
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
afiseaza_matrice(a, n, m, 0);
return 0;
}
Ce învățăm: două funcții recursive imbricate compun două parcurgeri: prima parcurge liniile, a doua, apelată pentru fiecare linie, parcurge coloanele.
Exercițiul Practic: Prelucrări recursive pe matrice
Sarcini de lucru
Completează sarcinile următoare pentru a aplica recursivitatea pe matrice
Sarcina 1: Numărul de elemente pare dintr-o matrice
Cerință: Scrie un program C++ care afișează numărul de elemente pare dintr-o matrice, folosind o funcție recursivă de parcurgere. Pentru matricea din exemplu (1 2 3 / 4 5 6), rezultatul este 2.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int numara_pare(int a[][101], int n, int m, int i, int j)
{
if (i == n)
return 0;
if (j == m)
return numara_pare(a, n, m, i + 1, 0);
int c = numara_pare(a, n, m, i, j + 1);
if (a[i][j] % 2 == 0)
c++;
return c;
}
int main()
{
int n, m, a[101][101];
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
cout << numara_pare(a, n, m, 0, 0);
return 0;
}
Verifică: pentru matricea 1 2 3 / 4 5 6, elementele pare sunt 2 și 4, deci rezultatul este 2.
Sarcina 2: Suma elementelor de pe diagonala principală
Cerință: Scrie un program C++ care afișează suma elementelor de pe diagonala principală a unei matrice pătrate, folosind o funcție recursivă cu un singur parametru de poziție. Pentru matricea 1 2 / 3 4, rezultatul este 1 + 4 = 5.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int suma_diagonala(int a[][101], int n, int i)
{
if (i == n)
return 0;
return a[i][i] + suma_diagonala(a, n, i + 1);
}
int main()
{
int n, a[101][101];
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
cout << suma_diagonala(a, n, 0);
return 0;
}
Verifică: elementele diagonalei principale au i == j, deci funcția avansează doar pe i, citind a[i][i].