Somas acumuladas

[polska 21]

Boas pessoal, estou a tentar perceber como é que uma matriz de somas acumuladas foi gerada, mas não estou a entender, a matriz inicial é esta:

E depois, a matriz de somas ficou assim:

Eu não estou a entender, se foi gerada por linhas, como é que passa de 1 para 2 na primeira linha e depois na segunda não passa de 2 para 3 em vez de 1 para 2 e depois 3 3 ... Se foi em colunas, porque é que as 3 primeiras são todas iguais e depois na 4 ja é diferente...

alguma ajuda?

Edited July 22, 2012 by pmg
colocou imagem directamente no topico

[pmg 96]

Aparentemente cada celula da matriz de baixo tem o numero de celulas na sub-matriz da matriz de cima que contem "X" e que tem indice x <= indice x da matriz de baixo e indice y <= indice y da matriz de baixo.

[polska 21]

Aparentemente cada celula da matriz de baixo tem o numero de celulas na sub-matriz da matriz de cima que contem "X" e que tem indice x <= indice x da matriz de baixo e indice y <= indice y da matriz de baixo.

Desculpa mas não percebi muito bem ... Podes-te explicar melhor ?

[pmg 96]

Na tua primeira matrix, a sub-matriz que vai ate (4, 3)

tem 2 quadrados com "X". A sub-matriz que vai ate (5, 3) tem 4 quadrados com "X"

A sub-matriz que vai ate (6, 5)

tem 5 quadrados com "X". Indo para (6, 6) passas a ter 7 quadrados com "X".

[polska 21]

Na tua primeira matrix, a sub-matriz que vai ate (4, 3)

tem 2 quadrados com "X". A sub-matriz que vai ate (5, 3) tem 4 quadrados com "X"

A sub-matriz que vai ate (6, 5)

tem 5 quadrados com "X". Indo para (6, 6) passas a ter 7 quadrados com "X".

Obrigado

[mogers 14]

Assumir que a matriz se encontra nas coordenadas 1..Nlinhas, 1..Ncolunas ajuda a simplificar o código do cálculo das somas acumuladas (linha e a coluna 0 devem ter apenas zeros)

// somar as submatrizes acima e à esquerda e retirar a porção que foi contada 2 vezes (i-1, j-1)
for (i = 1 ; i <= L ; i++)
for (j = 1 ; j <= C ; j++)
	 somas[i][j] = somas[i-1][j] + somas[i][j-1] - somas[i-1][j-1] + (matriz[i][j] == 'X');

Edited July 24, 2012 by mogers

[HappyHippyHippo 1,188]

Assumir que a matriz se encontra nas coordenadas 1..Nlinhas, 1..Ncolunas ajuda a simplificar o código do cálculo das somas acumuladas (linha e a coluna 0 devem ter apenas zeros)

vê bem o código que não estás a retirar o que dizes retirar

e falta o somas[0][0]

[mogers 14]

Sim, eu reparei e editei logo a seguir.

e falta o somas[0][0]

Como assim? Acho que não preciso de fazer nada com o somas[0][0]

[/

[HappyHippyHippo 1,188]

se matrix[0][0] for 'X' nunca estás a dizer que somas[0][0] é 1, o que vai causar um erro de contagem

[mogers 14]

Assumir que a matriz se encontra nas coordenadas 1..Nlinhas, 1..Ncolunas

Como disse, estou a assumir que os indices começam em 1 para simplificar o código.

Edited July 24, 2012 by mogers

[HappyHippyHippo 1,188]

[/font][/color]

Como disse, estou a assumir que os indices começam em 1 para simplificar o código.

então o problema é outro :

- tens os ciclos a começar em 1 e tens código tipo

somas[i-1][j-1]; // isto é somas[0][0] para i = 1 e j = 1

[mogers 14]

(linha e a coluna 0 devem ter apenas zeros)

quando i = 1 , j = 1,

somas[1][1] = somas[0][1] + somas[1][0] - somas[0][0] + (matriz[1][1] == 'X')

ou seja

somas[1][1] = 0 + 0 - 0 + (matriz[1][1] == 'X')

[HappyHippyHippo 1,188]

então estás a usar uma linha e coluna desnecessária inicial só porque achas mais intuitivo, apesar de que os índices começarem sempre por 0 ??

porque de outra forma "somas[0][1] + somas[1][0] - somas[0][0]" (se não existissem o índices 0, terás sempre acessos inválidos de memória

[mogers 14]

Por "assumir que os indices começam em 1" quero dizer que os dados da matriz que nos interessam começam nos indices 1.

Como estamos a usar C, os índices reais começam em 0.

Isto é feito simplesmente para evitar estar a introduzir ifs que lidam com potenciais indices negativos (linha e coluna 0), ou separar o calculo da linha e coluna 0 em for's independentes.

eu gosto deste tradeoff, estou a gastar mais L+C memória mas tenho um código mais compacto.

[HappyHippyHippo 1,188]

eu não disse que estava errado até porque se utilizado com cabeça funciona,

no entanto esse tipo de práticas não são intuitivas muito menos como exemplos para pessoas que estão a aprender