¿Cuántas conjeturas necesitarías para determinar el número entre 1 y 100 en el peor de los casos usando una búsqueda lineal?

¿Recibes algún comentario después de cada suposición?

  • “¡Tienes mi número!” O “¡Inténtalo de nuevo!”
    • Si el único comentario que obtiene es “Correcto” o “Incorrecto”, necesitará 99 conjeturas en el peor de los casos. Si no lo obtuvo con su última suposición, solo queda un número que tiene que ser.
  • “¡Demasiado alto!”, “¡Demasiado bajo!” O “¡Tienes mi número!”
    • Si obtiene pistas como “Superior” o “Inferior” cuando está equivocado, solo necesita siete conjeturas en el peor de los casos, si hace su primera suposición para que no queden más de 63 números a cada lado de su primera suposición, no quedan más de 31 números a cada lado de su segunda suposición, etc.
    • Si tiene una calculadora TI 83–84, como la calculadora gráfica TI-84 PLUS CE, entonces puedo ofrecerle un conjunto de tres programas que le permiten turnarse con su calculadora, adivinando los números de cada uno con el valor “más alto / más bajo” algoritmo. Deja un comentario si quieres una copia, y buscaré una dirección donde puedas descargarla.

Si la única pregunta que puede hacer es “¿ es esta? “Para lo cual la respuesta es” “o” no “, entonces una búsqueda lineal es todo lo que realmente puede esperar hacer:

¿Es 1? No.

¿Es 2? No.

¿Es 3? No. etc.

En el peor de los casos, el número es 100 y se necesitan 100 conjeturas. No importa cómo ordene sus preguntas: el peor de los casos es siempre 100 conjeturas. En promedio, tomará 50.5 conjeturas.

¡Una búsqueda lineal es tan ineficiente como una simple búsqueda puede ser!

Si, en lugar de responder ” ” o ” no “, las respuestas son ” “, ” más alto ” o ” más bajo “, entonces puede recurrir a la búsqueda binaria mucho más eficiente. En cada suposición, puede refinar el rango de posibles respuestas y su próxima suposición es siempre el punto medio de ese rango. Imagina que el número es 80:

¿Son 50? Mayor. [51,100]

¿Es 75? Mayor. [76,100]

¿Es 88? Inferior. [76,87]

¿Es 81? Inferior. [76,80]

¿Es 78? Mayor. [79,80]

¿Es 79? Mayor. [80,80]

En seis conjeturas sabes que el número es 80 (no necesitas la conjetura final en este caso).

Para una búsqueda binaria, el peor de los casos es [math] Log_2 (N) [/ math] conjeturas.

Lineal significa secuencialmente qué peor caso debe adivinarse cada número para garantizar que se encuentre el número.