algorithm - traductor - what to do with all this love traduccion al español




Dos canicas y un edificio de 100 pisos (6)

¿Cada uno se rompe cuando se cae desde la misma altura, o son diferentes?

Si son iguales, voy al piso 50 y tiro el primer mármol. Si no se rompe, voy al piso 75 y hago lo mismo, siempre y cuando no se rompa, sigo subiendo un 50% de lo que queda. Cuando se rompe, vuelvo a uno más alto que donde estaba anteriormente (así que si se rompió en el piso 75, vuelvo al piso 51) y tiro el segundo mármol y me muevo por el piso a la vez hasta que se rompe, en ese punto sé el piso más alto desde donde puedo caer sin rotura de mármol.

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

Una de esas preguntas de entrevista de programación clásica ...

Le dan dos canicas y le dicen que se romperán cuando caigan desde cierta altura (y presumiblemente no sufrirán daños si caen desde debajo de esa altura). Luego lo llevan a un edificio de 100 pisos (presumiblemente más alto que la altura determinada), y le piden que busque el piso más alto desde el que pueda tirar una canica sin romperlo de la manera más eficiente posible.

Información extra

  • Debes encontrar el piso correcto (no un rango posible)
  • Las canicas están garantizadas para romperse en el mismo piso
  • Suponga que le toma cero tiempo cambiar de piso: solo el número de gotas de mármol
  • Suponga que el piso correcto se distribuye al azar en el edificio

Creo que la verdadera pregunta es cuán precisa es la respuesta. Porque tu eficiencia realmente va a depender de eso.

Voy a estar de acuerdo con Justin si quieres un 100% de precisión en los mármoles y una vez que el primer mármol te rompa tendrás que subir de piso en piso desde el último piso "bueno" conocido hasta que descubras qué piso es el ganador." Tal vez incluso incluya algunas estadísticas y comience en el piso 25 en lugar del piso 50, de modo que su peor escenario sería 24 en lugar de 49.

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

En segundo lugar, ¿caminar contra las escaleras cuenta en contra de su eficiencia? En ese caso, siempre suelte ambos mármoles y levante ambos mármoles en cada viaje arriba / abajo.


Suelta el primer mármol del 3er piso. Si se rompe, sabes que es el piso 1 o 2, así que suelta el otro mármol del piso 2. Si no se rompe, has encontrado que el piso 2 es el más alto. Si se rompe, has encontrado que el piso 1 es el más alto. 2 gotas

Si cayendo desde el tercer piso no rompe el mármol, déjalo caer desde el piso 6. Si se rompe, sabes que el piso 4 o 5 es el más alto. Suelta el segundo mármol del piso 5. Si no se rompe, has encontrado que 5 es el más alto. Si lo hace, el piso 4 es el más alto. 4 gotas

Continuar.

3 plantas - máximo de 2 gotas

6 pisos - máximo de 4 gotas

9 pisos - máximo de 6 gotas

12 pisos - un máximo de 8 gotas

etc.

3x pisos - máximo de 2x gotas

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

A pesar de que dijiste que no importaba, probablemente requeriría la menor cantidad de caminar y no tienes que saber qué tan alto es el edificio.

Parte del problema es cómo defines la eficiencia. ¿Es más "eficiente" tener siempre una solución en menos de x gotas, o es más eficiente tener una buena oportunidad de tener una solución en y cae donde y <x con la advertencia de que podrías tener más de x gotas? ?


Suelta la primera canica en el piso 10, 20, 30, etc. hasta que se rompa, salta de nuevo al último piso bueno conocido y comienza a soltar canicas desde allí un piso a la vez. El peor caso es 99 siendo el piso mágico y siempre puedes encontrarlo en 19 gotas o menos.


Lo primero que haría es usar el algoritmo muerto simple que comienza en el piso 1. Deja caer el mármol de un piso a la vez hasta que llegue a 100 o se rompa el mármol.

Luego preguntaría por qué debería perder tiempo optimizándolo hasta que alguien pueda demostrar que será un problema. Demasiadas veces las personas se obsesionan con encontrar el algoritmo complicado perfecto cuando uno mucho más simple resolverá el problema. En otras palabras, no optimices las cosas hasta que las necesites.

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


Esto se puede hacer mejor con solo 7 canicas.

Entonces, siguiendo la respuesta, marque mármol en al menos 49º piso.

  1. Piso 50 -> descansos (la respuesta está entre 1 y 50 inclusive)
  2. Piso 25 -> no se rompe (26 a 50)
  3. Piso 37 -> no se rompe (38 a 50)
  4. Piso 43 -> no se rompe (44 a 50)
  5. Piso 46 -> no se rompe (47 a 50)
  6. Piso 48 -> no se rompe (49 o 50)
  7. 49th floor -> breaks (49th, este paso es realmente necesario porque podría haber sido el mínimo para que el mármol se rompa en 50º)

Esto se puede imaginar como hacer una búsqueda binaria en un conjunto ordenado para algunos k, donde tenemos la mitad del espacio de solución con cada intento. Para 100 plantas, necesitamos log2 100 = 6.644 (7 intentos). Con 7 canicas, podemos estar seguros de cuál es el piso mínimo en que el mármol se dividirá en 128 pisos.







puzzle