3

Preciso criar uma algoritmo que calcule o valor mínimo de distância entre os índices de uma matriz que contem valores adjacentes. Mas o que são valores adjacentes alguém poderia me dar exemplos?

Por exemplo, na matriz A tal que:

  

  A [0] = 0
  A [1] = 3
  A [2] = 3
  A [3] = 7
  A [4] = 5
  A [5] = 3
  A [6] = 11
  A [7] = 1

Os seguintes pares de valores têm índices adjacentes:

  (0, 7), (1, 2), (1, 4),

  (1, 5), (1, 7), (2, 4),

  (2, 5), (2, 7), (3, 4),

  (3, 6), (4, 5), (5, 7).

Os índices 4 e 5 têm valores adjacentes porque não há nenhum valor no array A

que se encontra estritamente entre A [4] = 5 e A [5] = 3; a única tal valor poderia ser o número 4,

e que não está presente na matriz.

4
  • Existe o conceito de valor adjacente em estatística. 11/02/2016 às 20:04
  • @Pablo Quero entender a logica desse exemplo. 11/02/2016 às 23:43
  • @AlUnserAlbuquerque vou responder, mas o texto vai ficar um pouco extenso.
    – Gomiero
    11/02/2016 às 23:58
  • @Gomiero tudo bem 12/02/2016 às 0:02

1 Resposta 1

3

Valores adjacentes podem ter muitos significados diferentes, e dependem, principalmente, do enunciado do problema e da área a qual ele se aplica.

Dois exemplos passo-a-passo, para mostrar regras diferentes para o conceito valores adjacentes.


Exemplo 1


Extraído da pergunta no SO em inglês:

Trying to sort and find the nearest pair of adjacent values in an array in C#

Neste caso, a regra é:

...
Um array A não-vazio com índice zero contém N inteiros.
Um par de índices (P, Q) onde 0 ≤ P < Q < N, é dito adjacente, se nenhum valor "encontra-se estritamente" entre A[P] e A[Q].
...


Aqui, a regra para criar as tuplas (P, Q) indica que não pode haver valores intermediários entre 2 elementos, portanto:


Valor   |  0 |  3 |  3 |  7 |  5 |  3 | 11 |  1 |  
--------+----+----+----+----+----+----+----+----+  
Índice  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  


Tuplas (P, Q) de índices (explicação segue a notação valor[índice] ou valor):

(0, 1)  => não, porque tem o valor 1[7] entre 0 e 3
(0, 2)  => não, porque tem o valor 1[7] entre 0 e 3
(0, 3)  => não, porque tem o valores 1[7] e 5[4] entre 0 e 7
(0, 4)  => não, porque tem o valor 1[7] e 3[1] entre 0 e 5
(0, 5)  => não, porque tem o valor 1[7] entre 0 e 3
(0, 6)  => não, porque tem o valores 1[7], 3[1], 5[4] e 7[3] entre 0 e 11
(0, 7)  => SIM, porque não há valor entre 0 e 1 (adjacentes)

(1, 2)  => SIM, porque não há valor entre 3 e 3 (adjacentes)
(1, 3)  => não, porque tem o valor 5[4] entre 3 e 7
(1, 4)  => SIM, porque não há valor entre 3 e 5 (adjacentes)
(1, 5)  => SIM, porque não há valor entre 3 e 3 (adjacentes)
(1, 6)  => não, porque tem o valores 5[4] e 7[3] entre 3 e 11
(1, 7)  => SIM, porque não há valor entre 3 e 1 (adjacentes)

(2, 3)  => não, porque tem o valor 5[4] entre 3 e 7
(2, 4)  => SIM, porque não há valor entre 3 e 5 (adjacentes)
.....
.....
.....

E seguindo esses passos, obtém-se o conjunto das tuplas:

(0, 7), (1, 2), (1, 4),
(1, 5), (1, 7), (2, 4),
(2, 5), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7)

Exemplo 2

Semelhante à pergunta feita por você em:

Algoritmo de números adjacentes com complexidade O (N * log (N))

estou supondo que a origem seja parecida com o seguinte desafio no site Codility:


Shortest Adjacency Sequency

(Não copiei o texto aqui devido a direitos autorais, mas é só clicar no link e no botão View no site)


Deve se achar o menor caminho do primeiro elemento (1) ao último elemento (2), seguindo as regras descritas no link acima.

Vetor de exemplo:

Valor   |  1 | 10 |  6 |  5 | 10 |  7 |  5 |  2 |
--------+----+----+----+----+----+----+----+----+
Índice  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |



Alguns caminhos possíveis (explicação segue a notação valor[índice] ou valor):


[1, 10, 6, 5, 10, 7, 5, 2]

Explicação: é o próprio vetor original.


[1, 10, 6, 5, 10, 7, => 5, 10, 7, 5, 2]

Explicação: Percorre o vetor até o valor 5[6], volta para o valor 5[3] (adjacente) e continua até o final.


[1, 10, 6, 5, => 10, 6, 5, 10, 7, 5, 2]

Explicação: Percorre o vetor até o valor 10[4], volta para o valor 10[1] (adjacente) e continua até o final.


[1, => 10, 7, 5, 2];

Explicação: Percorre o vetor até o valor 10[1], pula para o valor 10[4] (adjacente) e continua até o final.


[1, => 10, => 5, 2]

Explicação: Percorre o vetor até o valor 10[1], pula para o valor 10[4] (adjacente), volta para o valor 5[3] (anterior), pula para o valor 5[6] (adjacente) e continua até o final.


Neste exemplo, segundo o problema, a solução (menor caminho) é o [1, 10, 5, 2].



Portanto, o termo valores adjacentes depende da regra especificada no problema e, também, a área onde o termo é utilizado (conforme os comentários).


Abaixo, segue uma implementação (em Python) do exemplo 2:

Codility Iota 2011 Coding Challenge - ShortestAdjSeq

1
  • Perfeito exemplo bem claro para o solução do meu problema. Obrigado 12/02/2016 às 1:26

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .