Question

Salutare! Imi poate explica cineva codul de mai jos in cuvinte? Multumesc!


#include
using namespace std;
int main(){
int n, m, a[51][51], maxi;
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
maxi = a[0][0];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
for(int i2 = i; i2 < n; i2++) {
for(int j2 = j; j2 < m; j2++) {
int s = 0;
for(int k = i; k <= i2; k++) {
for(int l = j; l <= j2; l++) {
s += a[k][l];
}
}
if(s > maxi) {
maxi = s;
}
}
}
}
}
cout << maxi;
}

Answer 1

Răspuns:

Pe scurt rezultatul codului tau este suma elementelor din matricea citita de la tastatura. Dar ca sa ajunga la acest rezultat algoritmul urmeaza o serie mai indelungata de pasi si anume, de la orice index in parte el calculeaza acea suma pentru elementele ce formeaza o submatrice ce are ca inceput acel index.

Explicație:

Daca am avea n = 3 si m = 3, adica o matrice cu 3 linii si 3 coloane, iar aceasta ar fi:

1 2 3

4 5 6

7 8 9

atunci algoritmul calculeaza, pe rand, suma elementelor formate de toate submatricile ce se pot forma de la inceputul si pana la sfarsitul matricei initiale.

1, s = 1

1 2, s = 3

1 2 3, s = 6

1

4, s = 5

1 2

4 5, s = 12

1 2 3

4 5 6, s = 21

.

. pana ajungem chiar la matricea introdusa de la tastatura

.

1 2 3

4 5 6

7 8 9, s = 45

In acelasi timp, pe masura ce se calculeaza "s" se face si verificarea din if (s > maxi) iar maxi este actualizat, asadar dupa ce a calculat suma elementelor tuturor submatricilor ce au ca prim element chiar primul element din matricea initiala (exemplul de mai sus) rezulta ca maxi este 45, iar acesta urmeaza a fi comparat cu urmatoarele submatrici ce au ca prim element urmatoarele elemente din matricea initiala, adica, 2, 3, ... , 9.

De exemplu urmatoarea suma maxima pe care algoritmul o va calcula va fi suma submatricilor ce au ca prim element, elementul 2 si anume:

2, s = 2

2 3, s = 5

2

5, s = 7

2 3

5 6, s = 16

2

5

8, s = 15

2 3

5 6

8 9, s = 33

Din nou, pe masura ce se calculeaza "s", se verifica daca s > maxi, lucru care este fals pentru orice submatrice de aici, inclusiv cele ce vor mai urma, deoarece maxi = 45 iar nicio alta submatrice mai mica decat matricea initiala nu are cum sa aiba o suma a elementelor mai mare.

Asadar, algoritmul va calcula mereu suma elementelor matricei doar ca va parcurge mult mai multi pasi in plus crescand astfel timpul de executie si memoria.