Si tiene ‘una pelota’, entonces puede encontrar el piso desde el cual la pelota se romperá en [matemática] O (n) [/ matemática], debe verificar desde el 1 ° hasta el n ° piso, donde la pelota se rompa será la solución . En el peor de los casos, tendrá que verificar hasta el enésimo piso.
Sin embargo, si tiene dos bolas, entonces la solución se convertirá en la que será esencialmente la solución de la ecuación [matemáticas] x ^ 2 + x-2 * n [/ matemáticas].
por ejemplo, si tiene 10 pisos, entonces
1) deje caer el primero desde el 4to piso, si eso se rompe, tome el 2do y comience a caer desde el piso 0.
2) si el primero no se rompe, déjelo caer del 7 ° y verifique el segundo del 5 ° al 7 °.
3) si el primero no se rompe, déjelo caer del noveno y así sucesivamente.
entonces, la solución está en [matemática] O ((sqrt (8 * n + 1) -1) / 2) [/ matemática] o para ser muy preciso [matemática] O (sqrt (n)) [/ matemática]
- ¿Cuáles son los beneficios de los algoritmos? No los encuentro importantes.
- ¿Es posible construir un algoritmo (para ejecutar en una computadora con recursos de espacio finito) que tomará como entrada un flujo de lanzamientos de monedas al azar imparciales (probabilidad independiente de caras 1/2) y emitirá caras con probabilidad irracional esperada?
- ¿Hay diseñadores que diseñan algoritmos?
- ¿Es útil leer 5 o más libros para algoritmos, o debería leer solo uno o dos y usar los otros como referencia para algún algoritmo en particular?
- Soy nuevo en Quora y no entiendo si las preguntas de coeficiente intelectual son una tendencia constante o si estoy atrapado en alguna forma de algoritmo infernal. Si es así, ¿cómo escapo?
referencia: 2 huevos 100 pisos