polska Posted July 22, 2012 Report Share Posted July 22, 2012 (edited) 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 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 More sharing options...
pmg Posted July 22, 2012 Report Share Posted July 22, 2012 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 More sharing options...
polska Posted July 22, 2012 Author Report Share Posted July 22, 2012 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 More sharing options...
pmg Posted July 22, 2012 Report Share Posted July 22, 2012 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". 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 More sharing options...
polska Posted July 23, 2012 Author Report Share Posted July 23, 2012 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 🙂 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 More sharing options...
mogers Posted July 24, 2012 Report Share Posted July 24, 2012 (edited) 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 "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 More sharing options...
HappyHippyHippo Posted July 24, 2012 Report Share Posted July 24, 2012 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 Portugol Plus Link to comment Share on other sites More sharing options...
mogers Posted July 24, 2012 Report Share Posted July 24, 2012 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 More sharing options...
HappyHippyHippo Posted July 24, 2012 Report Share Posted July 24, 2012 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 Portugol Plus Link to comment Share on other sites More sharing options...
mogers Posted July 24, 2012 Report Share Posted July 24, 2012 (edited) 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 "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 More sharing options...
HappyHippyHippo Posted July 24, 2012 Report Share Posted July 24, 2012 [/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 Portugol Plus Link to comment Share on other sites More sharing options...
mogers Posted July 24, 2012 Report Share Posted July 24, 2012 (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 More sharing options...
HappyHippyHippo Posted July 24, 2012 Report Share Posted July 24, 2012 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 Portugol Plus Link to comment Share on other sites More sharing options...
mogers Posted July 24, 2012 Report Share Posted July 24, 2012 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 More sharing options...
HappyHippyHippo Posted July 24, 2012 Report Share Posted July 24, 2012 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 Portugol Plus Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now