Dos canicas y un edificio de 100 pisos

https://stackoverflow.com/questions/6547

08-06-2019
|

Pregunta

Una de esas preguntas clásicas de la entrevista de programación...

Te dan dos canicas y te dicen que se romperán si las dejas caer desde cierta altura (y presumiblemente no sufrirán daños si las dejas caer desde debajo de esa altura).Luego te llevan a un edificio de 100 pisos (presumiblemente más alto que cierta altura) y te piden que encuentres el piso más alto desde el que puedes dejar caer una canica sin romperla de la manera más eficiente posible.

Información extra

Debes encontrar el piso correcto (no un rango posible)
Se garantiza que ambas canicas se romperán en el mismo piso.
Supongamos que no le lleva tiempo cambiar de piso; solo cuenta la cantidad de gotas de mármol.
Suponga que el piso correcto está distribuido aleatoriamente en el edificio.

Solución

Lo interesante aquí es cómo puedes hacerlo en la menor cantidad de gotas posible.Ir al piso 50 y dejar caer el primero sería desastroso si el piso de ruptura es el 49, lo que nos obligaría a hacer 50 caídas.Deberíamos dejar caer la primera canica en el piso n, donde n es la cantidad máxima de gotas requeridas.Si la canica se rompe en el piso n, es posible que tengamos que hacer n-1 caídas después de eso.Si la canica no se rompe subimos al piso 2n-1 y si se rompe aquí tenemos que dejar caer la segunda canica n-2 veces en el peor de los casos.Seguimos así hasta el piso 100 e intentamos romperlo en 3n-2, 4n-3....
y n+(n-1)+(n-2)+...1 <=100
n=14 ¿Son las gotas máximas requeridas?

Otros consejos

Este problema se trata en el Problema 6.5 del Libro "Descifrando la entrevista de codificación (quinto)", con soluciones resumidas de la siguiente manera:

Observación:

Independientemente de cómo eliminemos Marble1, Marble2 debe realizar una búsqueda lineal.Por ejemplo, si el mármol1 se rompe entre el piso 10 y 15, tenemos que revisar cada piso intermedio con el mármol2

El enfoque:

Un primer intento: Supongamos que dejamos caer una canica desde el piso 10, luego desde el piso 20,...

En el primer mármol que se rompe en la primera caída (Piso 10), tenemos como máximo 10 caídas en total.
Si el primer mármol se rompe en la última gota (piso 100), entonces tenemos como máximo 19 gotas en total (pisos 1 a 100, entonces 91 a 99).
Eso está bastante bien, pero lo único que consideramos es el peor de los casos.Deberíamos hacer un "equilibrio de carga" para hacer que esos dos casos sean más pares.

Meta: Cree un sistema para dejar caer Marble1 de modo que la mayor cantidad de gotas requeridas sea constante, ya sea que Marble1 se rompa en la primera o en la última.

Un sistema equilibrado perfectamente de carga sería uno en el que las gotas de mármol1 + gotas de mármol2 son siempre las mismas, independientemente de dónde se rompiera el mármol1.
Para que ese sea el caso, ya que cada gota de mármol1 da un paso más, Marble2 tiene un paso menos.
Por lo tanto, debemos reducir el número de pasos potencialmente requeridos por el mármol2 por una gota cada vez.Por ejemplo, si Marble1 se deja caer en el piso 20 y luego el piso 30, el mármol2 es potencialmente necesario para dar 9 pasos.Cuando volvemos a colocar Marble1, debemos reducir los posibles pasos de Marble2 a solo 8.por ejemplo, debemos dejar caer Marble1 en el piso 39.
Sabemos, por lo tanto, Marble1 debe comenzar en el piso X, luego subir por pisos X-1, luego X-2, ..., hasta que llegue a 100.
Resuelva para X+(X-1)+(X-2)+…+1 = 100.X(X+1)/2 = 100 -> X = 14

Vamos al Piso 14, luego al 27, luego al 39,… Esto requiere 14 pasos como máximo.

Código y extensión:

Para la implementación del código, puede consultar aquí.
Para la extensión a N canicas, M pisos, echa un vistazo Capítulo 12:El rompecabezas de los huevos y los suelos .

¿Cada uno se rompe al caer desde la misma altura o son diferentes?

Si son iguales, voy al piso 50 y dejo caer la primera canica.Si no se rompe voy al piso 75 y hago lo mismo, mientras no se rompa sigo subiendo el 50% de lo que queda.Cuando se rompe, vuelvo a una más alta que donde estaba anteriormente (por lo que si se rompió en el piso 75, vuelvo al piso 51), dejo caer la segunda canica y subo un piso a la vez hasta que se rompe. momento en el que sé cuál es el piso más alto desde el que puedo caer sin que se rompa el mármol.

Probablemente no sea la mejor respuesta, tengo curiosidad por ver cómo responden los demás.

Deja caer la primera canica en el piso 10, 20, 30, etc.hasta que se rompa y luego salte al último conocido bien piso y comience a dejar caer canicas desde allí, un piso a la vez.En el peor de los casos, 99 es el Magic Floor y siempre puedes encontrarlo en 19 gotas o menos.

Personalmente, no soy muy fanático de este tipo de preguntas de acertijos, prefiero ejercicios de programación reales en las entrevistas.

Dicho esto, primero dependería de si puedo saber si están rotos o no desde el suelo donde los dejo caer.Supongo que puedo.

Subiría al segundo piso y dejaría caer la primera canica.Si se rompiera, probaría en el primer piso.Si eso se rompiera, sabría que no hay piso.

Si el primero no se rompiera, iría al cuarto piso y bajaría desde allí.Si eso se rompiera, volvería a bajar y tomaría la otra canica, luego me dejaría caer en el tercer piso, rompiéndome o no, sabría cuál es el límite.

Si ninguno se rompía, iría a buscar ambos y haría el mismo proceso, esta vez comenzando en el sexto piso.

De esta manera, puedo saltarme cada dos pisos hasta conseguir una canica que se rompa.

Esto se optimizaría si la canica se rompe temprano...Supongo que probablemente haya una cantidad óptima de pisos que podría saltar para aprovechar al máximo cada salto...pero si uno se rompe, tendría que revisar cada piso individualmente desde el primer piso encima del último piso conocido...lo cual, por supuesto, sería una molestia si me saltara demasiados pisos (lo siento, no voy a encontrar la solución óptima en este momento).

Lo ideal sería una bolsa entera de canicas, luego podría usar un algoritmo de búsqueda binaria y dividir el número de pisos por la mitad con cada gota...pero claro, esa no era la cuestión, ¿verdad?

Pienso que el real La pregunta es qué tan precisa quieres que sea la respuesta.Porque tu eficiencia realmente dependerá de eso.

Voy a estar de acuerdo con Justin si quieres una precisión del 100% en las canicas, una vez que la primera mármol se rompe, tendrás que subir 1 piso a la vez desde el último piso "bueno" conocido hasta que descubras qué piso es el ganador." Tal vez incluso agregue algunas estadísticas y comience en el piso 25 en lugar del piso 50 para que su peor escenario sea 24 en lugar de 49.

Si su respuesta puede ser más o menos uno o dos pisos, entonces podría haber algunas optimizaciones.

En segundo lugar, ¿subir o bajar escaleras cuenta en contra de su eficiencia?En ese caso, siempre deja caer ambas canicas y recoge ambas canicas en cada viaje hacia arriba o hacia abajo.

Deja caer la primera canica del tercer piso.Si se rompe, sabrás que es el piso 1 o 2, así que deja caer la otra canica del piso 2.Si no se rompe, habrás descubierto que el piso 2 es el más alto.Si se rompe, habrás descubierto que el piso 1 es el más alto.2 gotas.

Si al caer desde el tercer piso no se rompe el mármol, déjese caer desde el piso 6.Si se rompe, sabes que el piso 4 o 5 es el más alto.Deja caer la segunda canica del piso 5.Si no se rompe, habrás descubierto que 5 es el más alto.Si es así, el piso 4 es el más alto.4 gotas.

Continuar.

3 pisos - máximo de 2 caídas

6 pisos - máximo de 4 caídas

9 pisos - máximo de 6 caídas

12 pisos - máximo de 8 caídas

etc.

3x pisos - máximo de 2x caídas

Entonces, para un edificio de 99 pisos, tendrías un máximo de 66 caídas.Y eso es lo máximo.Probablemente tendrías menos gotas que eso.Ah, y 66 también es el máximo para un edificio de 100 pisos.Solo necesitarías 66 gotas si el piso de descanso fuera el piso 98 o 97.Si el piso de descanso fuera 100, usarías 34 gotas.

Aunque dijiste que no importaba, esto probablemente requeriría caminar menos y no es necesario saber qué tan alto es el edificio.

Parte del problema es cómo se define la eficiencia.¿Es más "eficiente" tener siempre una solución en menos de x gotas, o es más eficiente tener una buena posibilidad de tener una solución en y gotas donde y < x con la salvedad de que podría tener más de x gotas? ?

Esto se puede hacer mejor con sólo 7 canicas.

Entonces, siguiendo la respuesta votada, digamos que el mármol se rompe al menos en el piso 49.

Piso 50 -> descansos (la respuesta está entre 1 y 50 inclusive)
Piso 25 -> no se rompe (26 a 50)
Piso 37 -> no se rompe (38 a 50)
Piso 43 -> no se rompe (44 a 50)
Piso 46 -> no se rompe (47 a 50)
Piso 48 -> no se rompe (49 o 50)
Piso 49 -> roturas (49.º, este paso en realidad es necesario porque podría haber sido el piso mínimo para que el mármol se rompa, está en el 50.º)

Esto se puede imaginar como si se hiciera una búsqueda binaria en un conjunto ordenado para algún k, donde se obtiene la mitad del espacio de solución en cada intento.Para 100 pisos, necesitamos log2 100 = 6,644 (7 intentos).Con 7 canicas podemos estar seguros de cuál es el piso mínimo que romperá el mármol hasta 128 pisos.

Lo primero que haría es usar el algoritmo muy simple que comienza en el piso 1 y deja caer la canica un piso a la vez hasta llegar al 100 o la canica se rompe.

Luego preguntaría por qué debería dedicar tiempo a optimizarlo hasta que alguien pueda demostrar que será un problema.Muchas veces la gente se obsesiona con encontrar el algoritmo complicado perfecto cuando uno mucho más simple resolverá el problema.En otras palabras, no optimice las cosas hasta que sea necesario.

Esta podría ser una pregunta capciosa para ver si eres una de esas personas que pueden hacer una montaña a partir de un topo.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow