Me lo pidieron en una entrevista:
Problema
* Te dan 2 huevos.
* Tienes acceso a un edificio de 100 pisos.
- ¿Cuál es el rompecabezas más difícil que has encontrado (y / o lo has resuelto)?
- ¿Cuáles son algunos rompecabezas que solo necesitan sentido común para resolverlos?
- ¿Dónde puedo encontrar una gran cantidad de acertijos lógicos de alta calidad que no requieren conocimientos especializados (por ejemplo, semáforos)?
- ¿Conoces buenos acertijos o acertijos lógicos?
- ¿Hay una manera fácil de recordar el algoritmo para resolver el cubo de Rubik?
* Los huevos pueden ser muy duros o muy frágiles, lo que significa que pueden romperse si se caen desde el primer piso o incluso no romperse si se caen desde el piso 100. Ambos huevos son idénticos.
* Debes descubrir que el piso más alto de un edificio de 100 pisos puede dejar caer un huevo sin romperse.
* Ahora la pregunta es cuántas gotas necesitas hacer. Se le permite romper 2 huevos en el proceso.
Solución
Deje caer el primer huevo de 50. Si se rompe, puede intentar el mismo enfoque para un edificio de 50 pisos (1 a 49) y probarlo desde el piso 25. Si no se rompió, intente en el piso 75. Y use la búsqueda lineal con la porción restante del piso que necesitamos probar. Por ejemplo, si el primer huevo se rompe a 50 necesitamos probar todas las posibilidades de 1 a 49.
Ahora esto parece una solución factible. En la jerga de los estudiantes de informática, haga una búsqueda binaria con el primer huevo y una búsqueda lineal con el segundo. El mejor caso es log (100) y el peor es 50.
Ahora, la solución óptima para el problema es que descubres que eventualmente terminarás con una búsqueda lineal porque no tienes forma de decidir el piso más alto con un solo huevo (si rompiste un huevo y tienes que encontrar la respuesta entre 10 todo lo que puede hacer es comenzar de menor a mayor y lo peor es el número total de pisos). Entonces, la pregunta completa es cómo usar el primer huevo para reducir la prueba lineal del huevo.
(Para los estudiantes estrictos de ciencias de la computación, bueno, este problema se puede resolver mediante la búsqueda binaria en la cantidad de gotas necesarias para encontrar el piso más alto).
Ahora dejemos que x sea la respuesta que queremos, la cantidad de gotas requeridas.
Entonces, si el primer huevo se rompe al máximo, podemos tener gotas x-1; y por eso siempre debemos poner el primer huevo desde la altura x. Entonces hemos determinado que para una x dada debemos dejar caer la primera bola desde x altura.
Y ahora, si la primera gota del primer huevo no se rompe, podemos tener gotas x-2 para el segundo huevo si el primer huevo se rompe en la segunda gota.
Tomando un ejemplo, digamos que 16 es mi respuesta, que necesito 16 gotas para encontrar la respuesta. Veamos si podemos encontrar la altura en 16 gotas. Primero caemos desde la altura 16, y si se rompe probamos todos los pisos del 1 al 15. Si el huevo no se rompe, entonces hemos dejado 15 gotas, por lo que lo dejaremos caer desde 16 + 15 + 1 = piso 32. La razón es que si se rompe en el piso 32 podemos probar todos los pisos del 17 al 31 en 14 gotas (un total de 16 gotas). Ahora, si no se rompió, nos quedan 13 gotas. y podemos averiguar si podemos averiguar si podemos descifrar el piso en 16 gotas.
Tomemos el caso con 16 como respuesta
1 + 15 16 si se rompe en 16 controles de 1 a 15 en 15 gotas
1 + 14 31 si se rompe a 31 controles de 17 a 30 en 14 gotas
1 + 13 45 … ..
1 + 12 58
1 + 11 70
1 + 10 81
Fuente : internet
Enlaces adicionales :
Acertijos duros y respuestas
7 acertijos y respuestas súper difíciles
12 acertijos increíblemente difíciles que te volverán loco
iRIDDLER.com – acertijos muy difíciles – gratis en línea