a fost răspuns

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;
}

Răspuns :

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.

ID Alte intrebari