👤
a fost răspuns

Buna!
Imi poate explica cineva cum functioneaza sumele partiale in matrice? Nu inteleg nicicum algoritmul acesta:

int n,m, A[1001][1001], S[1001][1001];
//citire n,m,A[][]

for(int i = 0 ; i <= n ; i ++)
S[i][0] = 0;
for(int j = 0 ; j <= m ; j ++)
S[0][j] = 0;

for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];

int is,js; // coltul stanga sus
int ij,jj; // coltul dreapta jos
//citire is,js, ij,jj;

cout << S[ij][jj] - S[is-1][jj] - S[ij][js-1] + S[is-1][js-1];

Multumesc!

Răspuns :

CINEVAFARANUMEWIX

Daca avem o matrice/submatrice cu 4 zone care arata asa:

aaaaaaaabbbbbb

aaaaaaaabbbbbb

aaaaaaaabbbbbb

ccccccccdddddd

ccccccccdddddd

ccccccccdddddd

ccccccccdddddd

Si matricea cu sume este deja construita, atunci putem afla suma tuturor elementelor din zona d, stiind doar coordonatele colturilor stanga sus si dreapta jos astfel :

Prima oara, suma din coltul dreapta jos este suma tuturor elementelor din zonele a,b,c si d.

Apoi, scadem suma tuturor elementelor din zonele a si c, ne raman doar b si d.

Scadem suma tuturor elementelor din zonele a si b, raman (suma tuturor elementelor din zona d) - (suma tuturor elementelor din zona a)

Apoi, adaugam suma tuturor elementelor din zona a si ne ramane suma tuturor elementelor din zona d.

Atunci, daca ij, jj, is, js sunt indicii pentru randul si coloana coltului dreapta jos, respectiv indicii pentru randul si coloana pentru coltul stanga sus, si S matricea cu sumele, avem:

suma tuturor elementelor din zona a = S[is-1][js-1]

suma tuturor elementelor din zona b = S[is-1][jj]

suma tuturor elementelor din zona c = S[ij][js-1]

suma tuturor elementelor din zona d este S[ij][jj] - S[is-1][jj] - S[ij-1][jj] + S[is-1][js-1]

Pentru a construi matricea, avem:

S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + element[i][j]

Impartim iar o submatrice in 4 zone, a,b,c,d

aaaaaaa b

aaaaaaa b

ccccccc d

Atunci, suma tuturor elementelor din aceasta submatrice este:

(suma elementelor din zonele a si c) + (suma elementelor din zonele a si b) - (suma elementelor din zona a) + elementul d.

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că informațiile disponibile v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de sprijin, nu ezitați să ne contactați. Vă așteptăm cu drag și data viitoare! Nu uitați să adăugați site-ul nostru la favorite pentru acces rapid.


Wix Learning: Alte intrebari