👤
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 :

CINEVAFARANUMEID

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 pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari