• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

softklin

[Resolvido] Comparar numeros repetidos num array multidimensional

10 mensagens neste tópico

Boas pessoal!

Bem, venho por este meio pedir-vos ajuda, passo a explicar: tenho um vector bidimensional (nao se baseiem numa linguagem - e até por isso é que está nesta secção  :( ) com diferentes valores em diferentes linhas e colunas, exemplificando:

[table]

[/table]

Espero que tenham percebido este pequeno quadro, basicamente diz-nos que , por exmeplo, se fizermos v[3][1] obtemos o valor 5, e assim sucessivamente. Notem que algumas posições do array nao têm valores, é mesmo assim, pode haver dimensões "mais compridas" que outras.

Sim, e agora o que pretendo fazer com tudo isto? Bem, pretendia, dado um numero pelo utilizador X, detectar se há algum numero repetido x posições à frente desse vector. Exemplificando, se o X=3, entao o programa detectaria os valores em 5 em v[2][0] e em v[2][2], porque são numeros iguais, e estão a uma distancia inferior ou igual a X.

Finalmente, o meu problema é: sabendo à partida que o vector nao tem uma dimensão comum em todas as linhas, com um X=7, por exemplo, ele é forçado a detectar na "linha" a seguir... este passo é que eu nao sei fazer... se me conseguirem ajudar, agradeço imenso, tenho um trabalho pendente que inclui este parte. Obrigado desde já aos demais  :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O tamanho do vector é demasiado grande para tentar brute force?

Existe uma solução trivial cúbica, melhor do que isso já vai dar trabalho.. (ou seja, já tinha que pensar, não quer dizer que haja)

Edit: acabei de pensar numa solução que me parece n², podes passar todos os valores da matriz para um vector (estrutura que guarda valor, i e j), ordenar esse vector primeiramente por valor e depois pelas coordenadas.

Depois percorres esse vector, os número que te interessam vão estar consecutivos, basta testar se as diferenças entre eles é igual a X.

Para isso podes fazer um line sweep, ou mesmo brute force, nesse caso já tens bastantes menos valores iguais consecutivos, já é bastante mais eficiente do que bruteforce puro.

(se for mesmo necessário ser eficiente, até podes manter dois vectores, um ordenado pelo X e outro pelos Y, e a pesquisa torna-se linear dentro de cada um deles.)

Edit 2:

Ok, afinal é mais fácil do que isto.

Podes manter essa matriz, onde está tudo encostado à esquerda, e uma segunda, onde "encostas" tudo acima.

Procurar a distância entre dois valores passa a ser mesmo quadrático, basta procurares as distâncias na horizontal na primeira e na vertical na segunda..

PS: Atenção que n² = linha*coluna.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas se encostar tudo acima n vai alterar as distâncias reais a que se encontram os valores na matriz ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas, e obrigado pelas respostas!

Bem Warrior, obrigado pela tua sugestão. Porém, infelizmente não consegui chegar a esse nível de raciocinio... e realmente não iria acontecer a situação que o saunde referiu? É que é mesmo crucial manter uma correcta ordem das coordenadas. Outro ponto que me lembrei, é que o array pode tomar dimensões ou muito pequenas, ou gigantescas... ele deve estar mesmo preparado para tudo, pelo que fazer uma cópia do mesmo iria reflectir-se na performance...  :(

Bem, eu também já tinha tentado e tinha feito com este algoritmo

linhaExtra := 0

para cada linha i{

para cada coluna j{

para Y=1 até X{

se (j+Y) maior que tamanho de numero[j] então{

linhaExtra := 1

}

se numero[i+linhaExtra][j] = numero[j+Y] então{

numero detectado

}

linhaExtra := 0

}

}

}

Os problemas deste algoritmo:

- Se tiver de passar mais de uma linha nao dá

- Falta algo para controlar o ciclo para Y=1 até X, ou seja para que comece na linha seguinte, e continue a procurar a "distância que falta"

- Se não tiver mais linhas tb não dá... aqui tinha pensado em colocar outra condição no ciclo, por exemplo, uma flag fimDasLinhas que passava para a operação seguinte (uma vez que já tinha chegado ao fim do array, onde ira procurar?  :(

Será que alguém me consegue dar aqui uns arranjos neste algoritmo?  B)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Esse é o algoritmo brute force, é mais lento do que copiar a matriz toda como eu sugeri.

Basicamente tens o teu ciclo interior errado, tu pretendes que o Y vá de 1 a X, mas só queres que ele incremente quando encontras uma linha válida.

Basicamente, se a linha for valida, y = y+1, e passa para a linha seguinte, se nao for, passa para a linha seguinte, mas não incrementas o y.

Quanto à pergunta do saunde, se encostares tudo "acima" na matriz, ficas com a distância  correcta na vertical, mas errada na horizontal, como disseste muito bem. Mas por isso mesmo é que verificas a distância na horizontal na matriz original.

Já agora:

"Exemplificando, se o X=3, entao o programa detectaria os valores em 5 em v[2][0] e em v[2][2]"

A distância de v[2][0] e v[2][2] não devia ser 2?

v[2][0] - v[2][2] = 2

v[2][0] - v[2][1] = 1

v[2][0] - v[2][0] = 0

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Basicamente tens o teu ciclo interior errado, tu pretendes que o Y vá de 1 a X, mas só queres que ele incremente quando encontras uma linha válida.

Basicamente, se a linha for valida, y = y+1, e passa para a linha seguinte, se nao for, passa para a linha seguinte, mas não incrementas o y.

Desculpa, aqui esqueci-me de referir que o Y é como referiste, vai de 1 até X. Este valor é incrementado quer encontre um valor igual, quer nao encontre,

ou seja ficará

linhaExtra := 0

para cada linha i{

  para cada coluna j{

      para Y=1 até X{

        se (j+Y) maior que tamanho de numero[j] então{

            linhaExtra := 1

        }

        se numero[i+linhaExtra][j] = numero[j+Y] então{

            numero detectado

        }

        linhaExtra := 0

        Y := Y + 1

      }

  }

}

com a alteração que destaquei em cima

Já agora:

"Exemplificando, se o X=3, entao o programa detectaria os valores em 5 em v[2][0] e em v[2][2]"

A distância de v[2][0] e v[2][2] não devia ser 2?

v[2][0] - v[2][2] = 2

v[2][0] - v[2][1] = 1

v[2][0] - v[2][0] = 0

Sim, mas o valor que eu dei foi uma sugestão. Se o X fosse 1, isso já não iria ser detectado, porque (até se fizeres o ciclo, reparas nisso). O utilizador escolhe esse valor X sem pensar no números que lá estão dentro, é apenas uma distância.. se houver valores igauis compreendidos entre essas distâncias, então detecta... senao, se houver numeros mais à frente dessa distância, nem que seja so por 1 posição, este ja nao é detectado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Os teus erros no ciclo não são resolvidos colocando lá um "Y=Y+1", até porque eu supus que isso fosse um ciclo "for" e portanto incrementava sempre no final.

O problema é mesmo esse, se calhar um "while" resolvia melhor o teu problema, incrementando o Y só quando queres..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Os teus erros no ciclo não são resolvidos colocando lá um "Y=Y+1", até porque eu supus que isso fosse um ciclo "for" e portanto incrementava sempre no final.

O problema é mesmo esse, se calhar um "while" resolvia melhor o teu problema, incrementando o Y só quando queres..

Sim, novamente enganei-me queria escrever um while (enquanto e não para). Bem, se calhar para já vou pensar que o programa so pesquisa, no máximo, até uma linha extra abaixo... Vou ver no que isto dá, mais tarde postarei os meus resultados. Obrigado a todos :(

(ainda não está resolvido, não fechem o topico sff)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ok pessoal agora está resolvido. Acabei por seguir a sugestão de criar um novo array, peloq ue se tornou muito mais viável ;) Obrigado a todos!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

BOm isso e por acaso um dos problemas que eu usei para fazer o meu 1º labirinto em c++ xD

é apenas para cada 5 verificar tds os y.

pelo menos foi assim k pensei =)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora