algorithm - suba - Lanzar gatos fuera de las ventanas

proteccion ventanas gatos (9)

Imagina que estás en un edificio alto con un gato. El gato puede sobrevivir a una caída de una ventana de bajo nivel, pero morirá si lo arrojan desde un piso alto. ¿Cómo se puede saber la gota más larga que el gato puede sobrevivir, usando la menor cantidad de intentos?

La mejor estrategia para resolver este problema es investigar, usando la ley de la física, la probabilidad de que tus suposiciones sean verdaderas en primer lugar.

Si lo hubiera hecho, se daría cuenta de que las posibilidades de supervivencia del gato aumentan cuanto mayor es la distancia al suelo. Por supuesto, suponiendo que lo arrojes desde un edificio cada vez más alto, como las torres petronas, y no una montaña cada vez más alta, como el monte Everest.

Editar:
En realidad, verías una distribución de camellos sin terminar.
En primer lugar, la probabilidad de que el gato muera es baja (muy baja altitud), luego se vuelve más alta (baja altitud), luego de nuevo más baja (altitud más alta), y luego de nuevo más alta (altitud muy alta).

El gráfico de la probabilidad de morir de gato en función de la altitud sobre el suelo se ve así:
(Termine a las 3, porque la distribución del camello no está terminada)

Actualizar:
La velocidad máxima de un gato es de 100 km / h (60 mph) [= 27.7 m / s = 25.4 yardas / s].
La velocidad terminal humana es de 210 km / h (130 mph). [= 75 m / s = 68.58 yardas / s]

Fuente de velocidad terminal:
http://en.wikipedia.org/wiki/Cat_righting_reflex

Créditos:
Gooooooogle

Necesito verificar más tarde:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov/WWW/K-12/airplane/termv.html

Imagina que estás en un edificio alto con un gato. El gato puede sobrevivir a una caída de una ventana de bajo nivel, pero morirá si lo arrojan desde un piso alto. ¿Cómo se puede saber la gota más larga que el gato puede sobrevivir, usando la menor cantidad de intentos?

Obviamente, si solo tienes un gato, entonces solo puedes buscar linealmente. Primero tira al gato del primer piso. Si sobrevive, tíralo del segundo. Eventualmente, después de ser arrojado desde el piso f, el gato morirá. Entonces sabes que el piso f-1 era el piso seguro máximo.

Pero, ¿y si tienes más de un gato? Ahora puedes probar algún tipo de búsqueda logarítmica. Digamos que la construcción tiene 100 pisos y tienes dos gatos idénticos. Si arrojas al primer gato fuera del piso 50 y muere, entonces solo tienes que buscar 50 pisos linealmente. Puedes hacerlo aún mejor si eliges un piso más bajo para tu primer intento. Digamos que usted elige abordar el problema 20 pisos a la vez y que el primer piso fatal es el # 50. En ese caso, su primer gato sobrevivirá vuelos desde los pisos 20 y 40 antes de morir desde el piso 60. Solo tiene que verificar los pisos 41 a 49 individualmente. Eso es un total de 12 intentos, que es mucho mejor que los 50 que necesitaría si hubiera intentado utilizar la eliminación binaria.

En general, ¿cuál es la mejor estrategia y su peor complejidad para un edificio de dos pisos con dos gatos? ¿Qué hay de n pisos y m gatos?

Supongamos que todos los gatos son equivalentes: todos sobrevivirán o morirán por una caída desde una ventana determinada. Además, cada intento es independiente: si un gato sobrevive a una caída, está completamente ileso.

Esto no es tarea, aunque puedo haberlo resuelto para la tarea escolar una vez. Es solo un problema caprichoso que se me vino a la cabeza hoy y no recuerdo la solución. Puntos de bonificación si alguien sabe el nombre de este problema o del algoritmo de la solución.

¿No supone esto que estás usando "El Mismo Gato"?

Puede abordarlo matemáticamente, pero eso es lo bueno de las matemáticas ... con las suposiciones correctas, 0 puede ser igual a 1 (para valores grandes de 0).

Desde un punto de vista práctico, puede obtener "Gatos similares", pero no puede obtener "El mismo gato".

Podría tratar de determinar empíricamente la respuesta, pero creo que habría suficientes diferencias estadísticas que la respuesta sería estadísticamente sin sentido.

Podría intentar usar "The Same Cat", pero eso no funcionaría, ya que, después de la primera caída, ya no es el mismo gato. (De manera similar, uno nunca puede entrar al mismo río dos veces)

O bien, puede agregar la salud del gato, muestrear a intervalos extremadamente cercanos, y encontrar las alturas para las cuales el gato está "mayormente vivo" (en oposición a "la mayoría muerta" de "La princesa prometida"). Los gatos sobrevivirán, en promedio (hasta el último intervalo).

Creo que me he desviado de la intención original, pero si vas por la ruta empírica, voto por comenzar tan alto como sea posible y sigo bajando gatos a medida que la altura disminuye hasta que sobreviven estadísticamente. Y luego volver a probar en gatos supervivientes para estar seguro.

De acuerdo con un episodio reciente de Radiolab (sobre "Caída") , un gato alcanza la velocidad terminal en el noveno piso. Después de eso, se relaja y es menos probable que se lastime. Hay gatos completamente ilesos después de una caída desde arriba del 30. Los pisos más riesgosos son del 5 ° al 9 °.

No puedo leer el google blogspot en esto (gracias a works blogwall) pero no creo que una búsqueda directa de estilo binario sea lo mejor. La razón es que una búsqueda binaria se basa en la idea de que la respuesta que está buscando tiene las mismas posibilidades de estar en cualquier índice de índice en la lista. Sin embargo, en este caso, eso no es cierto. En este caso, la respuesta tendrá una mayor probabilidad de estar más cerca de un extremo del rango que el otro. No tengo idea de cómo incluir eso en la búsqueda, pero es un pensamiento interesante.

Primero leí este problema en el Manual de diseño de algoritmos de Steven Skiena (ejercicio 8.15). Siguió un capítulo sobre programación dinámica, pero no necesita saber programación dinámica para demostrar límites precisos en la estrategia . Primero la declaración del problema, luego la solución a continuación.

Los huevos se rompen cuando se caen desde una altura suficiente. Dado un edificio de n pisos, debe haber un piso f tal que los huevos caídos del piso f se rompan, pero los huevos caídos del piso f-1 sobreviven. (Si el huevo se rompe de cualquier piso, diremos f = 1. Si el huevo sobrevive de cualquier piso, diremos f = n + 1).
Usted busca encontrar el piso crítico f. La única operación que puede realizar es tirar un huevo en un piso y ver qué pasa. Comienzas con k huevos, y tratas de dejar caer huevos lo menos posible. Los huevos rotos no se pueden reutilizar (los huevos intactos pueden). Deje que E (k, n) sea la cantidad mínima de excrementos de huevo que siempre será suficiente.
Muestre que E (1, n) = n.
Muestre que E(k,n) = Θ(n**(1/k)) .
Encuentre una recurrencia para E (k, n). ¿Cuál es el tiempo de ejecución del programa dinámico para encontrar E (k, n)?

Solo 1 huevo

Dejar caer el huevo de cada piso comenzando en el primero encontrará el piso crítico en (en el peor de los casos) n operaciones.

No hay algoritmo más rápido. En cualquier momento en cualquier algoritmo, deje que el piso más alto desde el cual se haya visto el huevo no se rompa. El algoritmo debe probar piso g + 1 antes de cualquier piso más alto h> g + 1, de lo contrario si el huevo se rompiese del piso h, no podría distinguir entre f = g + 1 y f = h.

2 huevos

Primero, consideremos el caso k = 2 huevos, cuando n = r ** 2 es un cuadrado perfecto. Aquí hay una estrategia que toma el tiempo O (sqrt (n)). Comience dejando caer el primer huevo en incrementos de r pisos. Cuando se rompe el primer huevo, digamos en el piso ar , sabemos que el piso crítico f debe ser (a-1)r < f <= ar . Luego colocamos el segundo huevo de cada piso comenzando en (a-1)r . Cuando se rompe el segundo huevo, hemos encontrado el piso crítico. Dejamos caer cada huevo a la mayoría de las veces, por lo que este algoritmo toma las operaciones 2r en el peor de los casos, que es Θ (sqrt (n)).

Cuando n no es un cuadrado perfecto, tome r = ceil(sqrt(n)) ∈ Θ(sqrt(n)) . El algoritmo permanece Θ (sqrt (n)).

Prueba de que cualquier algoritmo toma al menos sqrt (n) tiempo. Supongamos que hay un algoritmo más rápido. Considere la secuencia de pisos desde la cual deja caer el primer huevo (siempre que no se rompa). Como cae menos que sqrt (n), debe haber un intervalo de al menos n / sqrt (n) que es sqrt (n). Cuando f está en este intervalo, el algoritmo tendrá que investigarlo con el segundo huevo, y eso debe hacerse piso por piso recordando el caso de 1 huevo. CONTRADICCIÓN.

k huevos

El algoritmo presentado para 2 huevos se puede extender fácilmente a k huevos. Deja caer cada huevo a intervalos constantes, que deben tomarse como los poderes de la raíz k de n. Por ejemplo, para n = 1000 yk = 3, busque intervalos de 100 plantas con el primer huevo, 10 con el segundo huevo y 1 con el último huevo.

De forma similar, podemos demostrar que ningún algoritmo es más rápido Θ(n**(1/k)) al inducir desde la prueba k = 2.

Solución exacta

Deducimos la recurrencia optimizando dónde dejar caer el primer huevo (piso g), suponiendo que conocemos soluciones óptimas para parámetros más pequeños. Si el huevo se rompe, tenemos los pisos g-1 a continuación para explorar con huevos k-1. Si el huevo sobrevive, tenemos pisos superiores para explorar con k huevos. El diablo elige lo peor para nosotros. Por lo tanto, para k> 1 la recurrencia

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n

Puede escribir fácilmente un poco de DP (programación dinámica) para el caso general de n pisos y m gatos.

La fórmula principal, a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..n , debe ser autoexplicativo:

Si se arroja el primer gato desde el piso k-ésimo y muere, ahora tenemos k - 1 pisos para verificar (todos los de abajo k ) y m - 1 gatos ( a[k - 1][m - 1] ).
Si el gato sobrevive, quedan n - k pisos (todos los pisos por encima de k ) y aún m gatos.
El peor caso de dos debe ser elegido, por lo tanto, max .
+ 1 proviene del hecho de que acabamos de utilizar un intento (independientemente de si el gato ha sobrevivido o no).
Probamos cada piso posible para encontrar el mejor resultado, por lo tanto min(f(k)) : for k in 1..n .

Está de acuerdo con el resultado de Google del enlace de Gaurav Saxena para (100, 2).

int n = 100; // number of floors int m = 20; // number of cats int INFINITY = 1000000; int[][] a = new int[n + 1][m + 1]; for (int i = 1; i <= n; ++i) { // no cats - no game a[i][0] = INFINITY; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { // i floors, j cats a[i][j] = INFINITY; for (int k = 1; k <= i; ++k) { // try throw first cat from k-th floor int result = Math.max(a[k - 1][j - 1], a[i - k][j]) + 1; a[i][j] = Math.min(a[i][j], result); } } } System.out.println(a[n][m]);

Puede encontrar fácilmente la estrategia (cómo lanzar el primer gato), si guarda mejor k en otro conjunto.

También hay una solución más rápida que no incluye O (n ^ 3) cálculos, pero ya tengo un poco de sueño.

editar
Oh, sí, recuerdo dónde vi este problema antes .

Tomé un método ligeramente diferente para producir una solución.

Empecé por calcular el piso máximo que podría cubrirse utilizando x gatos y adivina utilizando el siguiente método.

Comienza con 1 piso y sigue aumentando el número de conjeturas mientras haces un seguimiento de los pisos, lo que supone que fueron controlados y cuántos gatos quedaban para cada piso.
Repita esto hasta y veces.

Este código muy ineficiente para calcular la respuesta dada, pero no obstante útil para un pequeño número de gatos / pisos.

Código de Python:

def next_step(x, guess): next_x = [] for y in x: if y[0] == guess: if y[1] != 1: next_x.append((guess+1, y[1] - 1)) next_x.append(y) if y[0] == guess: next_x.append((guess+1, y[1])) return next_x x = [(1, TOTAL_NUM_CATS)] current_floor = 1 while len(x) <= TOTAL_NUM_FLOORS: x = next_step(x, current_floor) current_floor += 1 print len(x)

Para 2 gatos, los pisos máximos que se pueden identificar en x conjeturas son:
1, 3, 6, 10, 15, 21, 28 ...

Para 3 gatos:
1, 3, 7, 14, 25, 41, 63 ...

Para 4 gatos:
1, 3, 7, 15, 30, 56, 98 ...

Después de una extensa investigación (en su mayoría involucrando secuencias de números de mecanografía en OEIS ) noté que los pisos máximos para x siguen un patrón por partes combination .

Para 2 gatos:
n <2: 2 ^ n - 1
n> = 2: C (n, 1) + C (n, 2)

Para 3 gatos:
n <3: 2 ^ n - 1
n> = 3: C (n, 1) + C (n, 2) + C (n, 3)

Para 4 gatos:
n <4: 2 ^ n - 1
n> = 4: C (n, 1) + C (n, 2) + C (n, 3) + C (n, 4)

Desde aquí tomé el enfoque fácil de simple incremento n hasta que pase el número requerido de pisos.

Código de Python:

def find_smallest(floors, eggs): maximum_floors = 0 n = 0 while maximum_floors < floors: maximum_floors = 0 n += 1 if n < eggs: maximum_floors = 2**n - 1 else: count = 0 for x in xrange(1, eggs+1): maximum_floors += combination(n, x) print n

Esto da la solución correcta para (100, 2) = 14.
Para cualquiera que desee comprobar algo menos trivial, da (1 000 000, 5) = 43.

Esto se ejecuta en O (n) donde n es la respuesta al problema (cuanto más gatos, mejor).
Sin embargo, estoy seguro de que alguien con un nivel más alto de matemáticas podría simplificar las fórmulas por partes para calcular en O (1).

toda esta alocada charla sobre gatos ... y solo es un adivinar el problema del número con conjeturas mínimas (cantidad de gatos). no debería haber una necesidad de definir artificialmente (e incorrectamente) el infinito como parte de la solución tampoco. la variable debería haber sido llamada upper-bound o max-try o algo así. la definición del problema (la cosa del gato) tiene algunos problemas graves, con personas que responden al potencial de crueldad animal y también las múltiples facetas de tal problema planteado en la vida real, por ejemplo, arrastre de aire, gravedad es aceleración y otros parámetros de la vida real del problema. así que quizás debería haberse preguntado de una manera totalmente diferente.

O(m*(n^(1/m))) algorithm. Let ''x'' be the maximum number of attempts needed. m = 1 => linear => x=n m = 2: Let the floors be split into ''k'' partitions. The first cat is thrown at the end of each partition (max ''k'' times). When it dies, the second cat is used to go up from the beginning of this partition. x = k + n/k. Minimize x by diff wrt k and setting = 0, to get k = n^(1/2) and x = 2 * n^(1/2). m = 3: x = k + 2*(y^(1/2)), where y = n/k diff wrt x and set = 0, to get k = n^(1/3) and x = 3 * n^(1/3) for general m: x = m * n^(1/m).