Jump to content
polska

Somas acumuladas

Recommended Posts

polska

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.

Share this post


Link to post
Share on other sites
pmg

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!

Share this post


Link to post
Share on other sites
polska

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 ? :thumbsup:


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

Share this post


Link to post
Share on other sites
pmg

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!

Share this post


Link to post
Share on other sites
polska

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.

Share this post


Link to post
Share on other sites
mogers

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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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]


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
mogers

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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
mogers
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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

[/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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
mogers
(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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites
mogers

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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • 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.