none
Estrutura de DADOS RRS feed

  • Pergunta

  • Eu não entendi esse algoritmo, nem o exemplo dele, alguém consegue me o resultado do exemplo.

    Escreva um programa que receba um número e depois uma lista circularmente ordenada (sem repetições) separada por virgula e que responda, o mais rápido possível, se um número pertence ou não à lista. 

              Exemplo:

    Entrada: 5 2,3,4,0,1                                Saída: não

    Entrada: 4 2,3,4,0,1                                Saída: sim

    Entrada: 3 4,6,11,-1,1,2,3                    Saída: sim
    quarta-feira, 4 de julho de 2018 20:38

Respostas

  • >Escreva um programa que receba um número e depois uma lista circularmente ordenada (sem repetições) separada por virgula e que responda, o mais rápido possível, se um número pertence ou não à lista. 

    O que é uma lista circularmente ordenada ? Imagine um relogio, voce tem a dimensao horas que gera uma lista assim:

    1,2,3,4,5,6,7,8,9,10,11,12

    Isso se ponto inicial for 1 horas. Agora se o  ponto inicial muda para 4 horas, entao a lista pode ser reescrita assim:

    4,5,6,7,8,9,10,11,12,1,2,3

    Entendeu?

    Agora veja o enunciado do problema: 

    "Escreva um programa que receba um número e depois uma lista circularmente ordenada"

    Ou seja, voce recebe dois parametros de entrada: un numero e uma lista. Nos exemplos dados:

    Entrada: Numero=5  Lista=2,3,4,0,1 

    Saida: Não. O numero 5 nao faz parte da lista 2,3,4,0,1

    Agora qual é a forma mais rapida de saber se um numero faz parte de uma lista circularmente ordenada?

    Primeiro voce tem que achar a posicao do cabeçalho da lista e o pé da lista (header e footer). Na lista exemplo voce pode reescrever a lista da forma seguinte:

    0,1,2,3,4

    Neste caso o Header é 0 e o Footer é 4.

    Depois e testar se o elemento procurado é maior ou igual ao header ou menor ou igual ao footer. Nesse caso, 5 é maior que  o footer, logo, ele nao pertence à lista.

    Mas e se a lista fosse: 3,5,0,1,2 e voce esteja procurando o 4?

    Mais uma vez. Achar o header e footer: 0 e 5 respectivamente.

    Depois fazer o teste se 4 é maior ou igual ao header ou menor ou igual ao footer? Sim ele esta dentro da faixa, mas ainda nao temos certeza se ele pertence ou nao à lista.

    Nesse caso podemos testar elemento por elemento e verificar se é igual ao elemento procurado, mas se a lista contiver milhoes de elementos isso pode ser lento.

    O ideal é ir reduzindo a lista à partir dos extremos e aplicar o teste, desta forma:

    A lista pode ser reescrita assim: 0,1,2,3,5. Sabemos que o header é 0 e o footer é 5. Se diminuirmos o raio de 1 a lista fica : 1,2,3. Agora o novo header  é  1 e o novo footer é 3. 4 é maior ou igual à 1 e menor ou igual à 3? Não, 4 é maior que 3. Então ele nao pertence à lista.


    William John Adam Trindade
    Analyste-programmeur


    Sogi Informatique ltée
    If you found this post helpful, please "Vote as Helpful". If it actually answered your question, remember to "Mark as Answer". Se achou este post útil, por favor clique em "Votar como útil". Se por acaso respondeu sua dúvida, lembre de "Marcar como Resposta".


    quarta-feira, 4 de julho de 2018 21:15
    Moderador