Problema de 2 huevos y 100 pisos (resuelto)

los 2 huevos y 100 pisos El problema se plantea con frecuencia en las entrevistas para evaluar la comprensión del candidato de la búsqueda lineal y la búsqueda binaria. Traté de explicar este problema de la manera más simple posible.

Índice
  1. Planteamiento del problema
  2. Solución 1 (investigación de recubrimientos)
  3. Solución 2 (búsqueda binaria)
  4. Solución 3 (Divide y vencerás)
  5. Solución 4 (Ecuación)

Planteamiento del problema

Hay un edificio de 100 pisos. Uno de los pisos es el piso más alto (digamos el N-ésimo piso) desde el cual se puede dejar caer un huevo sin romperse.

  • Si un huevo cae desde este piso (N) o desde arriba (N+1, N+2,…), se romperá.
  • Si cae desde cualquier piso de abajo (N-1, N-2,…), no se romperá y podrás volver a dejar caer el huevo.

Dados dos huevos 🥚🥚, encuentre el piso (N) desde el cual se puede dejar caer un huevo sin romperse número mínimo de gotas.

Problema de 2 huevos y 100 pisos

La pregunta es, ¿Qué estrategia debe adoptar para minimizar el número de gotas de huevo necesarias para encontrar la solución?. (¿Y cuál es el peor de los casos para cuántas gotas tomará?)

Piense en el problema durante unos minutos y luego siga leyendo.

La primera solución es la estrategia de búsqueda lineal, que es muy simple si no nos importa la cantidad de gotas. Podemos comenzar a dejar caer el huevo desde el piso 1, piso 2, piso 3 y continuar hasta el piso 100 hasta encontrar el piso N. En el peor de los casos, tomará 100 caídas si el huevo solo se rompe en el último (100) piso.

    Linear search - worst case - 100 drops

¿Podemos mejorar en el peor de los casos utilizando una estrategia de búsqueda binaria? vamos a ver en respuesta 2.

La segunda solución es la estrategia de búsqueda binaria donde comenzamos desde el piso medio (50).

  • Si el huevo se rompe en el piso 50, eso significa que nuestra N es menor que 50.
  • Si el huevo no se rompe, eso significa que nuestro N es mayor que 50.

La estrategia de búsqueda binaria dice que si el huevo se rompe en el piso 50, debemos verificar ahora desde el piso 25, pero espera, tenemos un problema aquí. Ya hemos perdido 1 huevo y ahora nos queda solo 1 huevo, por lo que terminamos con una búsqueda lineal solamente, pero en este caso solo del piso 1 al 50 en el peor de los casos. Por lo tanto, nuestras gotas se han reducido a la mitad en comparación con la solución 1

    Binary Search - worst case - 50 drops

¿Todavía podemos mejorar el peor de los casos? Deja ver en respuesta 3

Solución 3 (Divide y vencerás)

Apliquemos nuestro aprendizaje de las soluciones anteriores y apliquemos una combinación de enfoque lineal y binario.

Esta vez empezamos dejando caer un huevo en el piso 10, piso 20, piso 30... aumentando el piso en 10

  • Si el primer huevo se rompe en el piso 10, usamos el segundo huevo para una búsqueda lineal del 1 al 9

  • Si el primer huevo se rompe en el piso 20, usamos el segundo huevo para una búsqueda lineal del 11 al 19

  • ….

  • En el peor de los casos, si el huevo se rompe en el último piso (100), usamos el segundo huevo para una búsqueda lineal del 91 al 99. En el peor de los casos, se necesitarán 19 gotas (10, 20, 30... … 70 80 90 91 …. 99)

      Divide and Conquer - worst case - 19 drops
    

Ahora cuando lleguemos a un acuerdo, veamos respuesta 4

Solución 4 (Ecuación)

Lo que necesitamos es una solución que minimice nuestras gotas máximas. La solución anterior indica que lo que necesitamos es una estrategia que trate de hacer que las soluciones a todas las respuestas posibles tengan la misma profundidad (la misma cantidad de gotas). La forma de reducir el peor de los casos es intentar que todos los casos tomen el mismo número de gotas.

Como espero que pueda ver ahora, si la solución está en algún lugar en un piso bajo, entonces tenemos espacio adicional para la cabeza cuando tenemos que pasar por los sencillos, pero, a medida que avanzamos en el edificio, ya hemos usado las posibilidades de llegar allí, así nos quedan menos gotas cuando tenemos que ir piso por piso.

Vamos a romper un poco de álgebra.

Imagina que tiramos nuestro primer huevo del suelo nosi se rompe podemos pasar por el anterior (n-1) pisos uno por uno.

Si no se rompe, mejor que salte otro no pisos, en lugar de eso deberíamos intensificar (n-1) pisos (porque tenemos una gota menos disponible si tenemos que ir a un piso uno por uno), por lo que el siguiente piso que debemos probar es el piso n + (n-1)

Asimismo, si esta caída no se rompe, entonces debemos saltar al suelo. n + (n-1) + (n-2)luego piso n + (n-1) + (n-2) + (n-3) …

Continuamos reduciendo el terreno de juego en uno cada vez que saltamos, hasta que el terreno de juego es solo de un piso, y obtenemos la siguiente ecuación para un edificio de 100 pisos:

n + (n-1) + (n-2) + (n-3) + (n-4) + … + 1 >= 100

Esta suma, como muchos reconocerán, es la fórmula del número triangular (lo cual tiene sentido, ya que estamos reduciendo en uno con cada gota que hacemos) y se puede simplificar a:

n (n+1) / 2 >= 100

Esta es una ecuación cuadrática, con la raíz positiva de 13.651 (que necesitamos redondear a 14)

Esto significa que queremos empezar a bajar desde el piso 14, saltar 13 pisos para bajar desde el piso 27, saltar 12 pisos para bajar desde el piso 39, y así sucesivamente. Nuestro peor escenario es entonces un total de 14 caídas.

    Equation - worst case - 14 drops
Olvídelo Suelo
#1 14
#2 27
#3 39
#4 60
#6 69
#7 77
#8 84
#9 90
#diez 95
#11 99
#12 100

Si quieres conocer otros artículos parecidos a Problema de 2 huevos y 100 pisos (resuelto) puedes visitar la categoría Tutoriales.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Subir

Esta página web utiliza cookies para analizar de forma anónima y estadística el uso que haces de la web, mejorar los contenidos y tu experiencia de navegación. Para más información accede a la Política de Cookies . Ver mas