El día de hoy vamos a resolver un ejercicio en Python en donde el usuario va a pensar un número y el programa o la computadora va a adivinarlo.

Para ello vamos a usar la búsqueda binaria: vamos a hacer que la computadora piense en un número y se lo muestre al usuario. Luego el usuario le debe decir si acertó, y en caso de que no, le debe decir si es menor o mayor.

Lo interesante aquí es que la computadora adivinará en el menor número de intentos posibles, sin confiar en la suerte.

Explicación del algoritmo

Como te dije, vamos a usar la búsqueda binaria. Obviamente el número que va a pensar el usuario estará dentro de un límite; así que se va a calcular el número intermedio y en caso de no acertar entonces el rango se va a acortar dividiéndolo entre 2.

Digamos que va a ir dividiendo sus posibilidades entre 2. Por ejemplo aquí yo pensé en el número 80 con un rango de 1 a 100 y esta fue la salida:

See the gist on github.

Como puedes ver, va dividiendo entre 2 la cantidad de números en los que pudiste pensar. Así es como usamos la búsqueda binaria para adivinar el número que el usuario pensó.

Adivinar número con Python

Ya expliqué el algoritmo, ahora veamos el código. Simplemente vamos a definir el rango y a partir de él calcular el número que se encuentra a la mitad. El doble símbolo de división // es para dividir y redondear al entero anterior más cercano.

See the gist on github.

Hacemos un ciclo while que se va a ejecutar mientras la computadora (y el programa en Python) no adivinen el número en el que pensó el usuario.

Dentro del ciclo se va a calcular el número intermedio y preguntar si acertó; en caso de que no entonces se va a preguntar si el número en el que el usuario pensó es menor o mayor, y a partir de ello el rango se acortará a la mitad.

También se comprueba si el número está fuera del rango. Obviamente tú puedes modificar el rango según tus necesidades; entre más corto sea, más rápido adivinará la computadora.

Me parece que el número de intentos que el programa tomará será aproximadamente el logaritmo base 2 de la cantidad de números dentro del rango.

Por ejemplo: si son 100 números, el programa tomará un máximo de 7 intentos (y el log2(100) es 6.64)… pero eso se lo dejo a alguien que sepa más sobre matemáticas.

Para terminar te dejo con más tutoriales de Python en mi blog.