Curso 2024/2025
Este algoritmo devuelve el número secreto; suponemos que
disponemos de una función intentar
que nos dice
si el número secreto es mayor o menor en cada intento (podría
consistir en preguntarle al usuario).
int adivinarNumero() { // En una primera fase va multiplicando por 2 hasta encontrar // el número secreto o superarlo, empezando en 1 int numero = 1; string respuesta = intentar(numero); while (respuesta == "es mayor") { numero = numero * 2; respuesta = intentar(numero); } if (respuesta != "es menor") return numero; // Si no lo ha encontrado, en una segunda fase realiza // una búsqueda binaria entre los dos últimos numeros int limiteInferior = numero / 2 + 1; int limiteSuperior = numero - 1; while (limiteInferior < limiteSuperior) { numero = (limiteInferior + limiteSuperior) / 2; respuesta = intentar(numero); if (respuesta == "es mayor") limiteInferior = numero + 1; else if (respuesta == "es menor") limiteSuperior = numero - 1; else return numero; } return limiteInferior; }
Por ejemplo, supongamos que el número secreto es 23. En la primera fase, los intentos son 1, 2, 4, 8, 16 y 32. En la segunda fase, los intentos son 24, 20, 22 y 23.