Ankur y Vijay son aficionados a los juegos de números. En uno de los juegos, Ankur tiene que elegir un número X, tal que X pertenezca a [1, 10000] . Vijay tiene que adivinar el número elegido lo antes posible. Ankur le hará saber a Vijay si su conjetura es menor, mayor o igual que el número. La advertencia es que Vijay pierde el juego si su suposición es mayor que el número elegido por Ankur dos o más veces.
Q1. ¿Cómo hacer conjeturas y cuántas conjeturas son necesarias?
Q2. ¿Qué pasa si a Ankur se le permite elegir un número positivo muy grande sin límites dados? .
Solución:
Ambos problemas se pueden tratar de las siguientes maneras:
Respuesta 1:
Cuando Ankur elige un número entre 1 y n, aquí n=10000, Vijay debe comenzar a adivinar √n, 2√n, 3√n, 4√n, etc. La primera vez que su conjetura supera el número de Ankur, el rango de números se ha reducido a √n números; luego comienza a adivinar secuencialmente en ese rango.
Respuesta 2: si Ankur adivina un número n arbitrariamente grande, entonces Vijay puede usar la búsqueda binaria, lo que significa elegir la mitad de 1 y 10000, es decir, 5000, y si Ankur dice que es menor, entonces elija la mitad del término de 1 y 5000, es decir, 2500, etc. Al final, te encontrarás con el número exacto n. Se necesita el tiempo de la orden O(n) para completarse.
Este rompecabezas es una contribución de Ujjwal Prakash. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA