Olá amigos! Na disciplina de PAA(Pesquisa e Análise de Algoritmos) do Mestrado, a prof. dra. Roseane de Freitas nos passou alguns desafios do URI, e o primeiro deles que estou postando aqui é “Onde está o mármore”. O enunciado do desafio você pode estar conferindo clicando aqui.
Seguindo então o que nos é apresentado pelo desafio, precisamos receber N(número) e Q(Quantidade de Consultas) e após isso imprimir algo como:
4 1
CASE# 1:
2
3
5
1
5
5 found at 4
Mas aí vem a dúvida, como que o resultado diz que o número 5 foi encontrado na posição 4 ? 🙂 E então ? Já sabe a charada ? Vamos reler o nome do desafio, “onde está o mármore ?”, a questão é que após os números serem inseridos para podemos trabalhar com eles, precisamos realizar a ordenação de modo que os números fiquem em ordem crescente, ou seja, a ordem no exemplo acima ficaria:
Números ordenados de forma crescente: 1 2 3 5, portando o 5 ele foi encontrado em nosso vetor ou conjunto e na posição 4. Então aqui foi a primeira dica. Para concluir, precisamos realizar uma busca pelo número informado e se tratando de busca iremos utilizar a “busca binária” pois conseguiremos uma melhor performance em relação a velocidade.
Marbles was hacked ! 🙂 O código fonte você pode conferir no meu github clinkando AQUI!
Até o próximo post!
