Me ajuda em algoritmo
Você é um oráculo e o seu objetivo é adivinhar um número, no intervalo de 1 a 8, que o
usuário vai escolher. Você pode fazer no máximo três perguntas
Soluções para a tarefa
Respondido por
1
Isso aí é busca binária.
A cada passo você reduz o tamanho do problema pela metade.
1, 2, 3, 4, 5, 6, 7, 8
Você pega sempre o número que está na metade do intervalo e pergunta se o número é maior que o número do meio.
Digamos que escolheram 6 e você não sabe.
No intervalo de 1 a 8 você pega o termo do meio, que é o 4 (8/2).
Aí você pergunta: o número escolhido é maior que o 4?
Aí te respondem "sim" (porque o 6 é o número secreto)
Daí você sabe que o número está no intervalo de 5 a 8.
Repete. Pega o do meio, que é 6, e pergunta se é maior. Te respondem "não" porque 6 não é maior que 6.
Resta o intervalo de 5 a 6.
Pega o cinco e pergunta se o úmero é maior que 5 e te respondem "sim".
Logo, o número é 6 e você só fez três perguntas (com resposta sim ou não).
Um algoritmo poderia ser.
inicio = 1
fim = 8
achou = false
enquanto (achou == false) faça:
meio = parte inteira de (inicio + fim)/2
se (inicio == fim) faça:
numero = fim
achou = true
senão, faça:
se n > meio faça:
inicio = meio + 1
senão, faça:
fim = meio
A cada passo você reduz o tamanho do problema pela metade.
1, 2, 3, 4, 5, 6, 7, 8
Você pega sempre o número que está na metade do intervalo e pergunta se o número é maior que o número do meio.
Digamos que escolheram 6 e você não sabe.
No intervalo de 1 a 8 você pega o termo do meio, que é o 4 (8/2).
Aí você pergunta: o número escolhido é maior que o 4?
Aí te respondem "sim" (porque o 6 é o número secreto)
Daí você sabe que o número está no intervalo de 5 a 8.
Repete. Pega o do meio, que é 6, e pergunta se é maior. Te respondem "não" porque 6 não é maior que 6.
Resta o intervalo de 5 a 6.
Pega o cinco e pergunta se o úmero é maior que 5 e te respondem "sim".
Logo, o número é 6 e você só fez três perguntas (com resposta sim ou não).
Um algoritmo poderia ser.
inicio = 1
fim = 8
achou = false
enquanto (achou == false) faça:
meio = parte inteira de (inicio + fim)/2
se (inicio == fim) faça:
numero = fim
achou = true
senão, faça:
se n > meio faça:
inicio = meio + 1
senão, faça:
fim = meio
Perguntas interessantes
Matemática,
9 meses atrás
Português,
9 meses atrás
Matemática,
9 meses atrás
Sociologia,
1 ano atrás
Física,
1 ano atrás
Geografia,
1 ano atrás