Jump to content

Somas acumuladas


polska
 Share

Recommended Posts

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:

scaled.php?server=521&filename=semttulotsd.png&res=landing

E depois, a matriz de somas ficou assim:

scaled.php?server=29&filename=semttulorna.png&res=landing

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 by pmg
colocou imagem directamente no topico

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

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.

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

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 ? 👍

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

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

image.png

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)

image.png

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

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

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

image.png

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)

image.png

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

Obrigado 🙂

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

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 by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

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]

[/

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

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 by mogers

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

(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')

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

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

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

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.

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.