Lanzar gatos por las ventanas

Imagina que estás en un edificio alto con un gato. El gato puede sobrevivir a una caída por una ventana de piso bajo, pero morirá si lo arroja desde un piso alto. ¿Cómo puedes calcular la caída más larga que el gato puede sobrevivir, utilizando el menor número de intentos?

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

Pero, ¿y si tienes más de un gato? Ahora puede intentar 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. Puede hacerlo aún mejor si elige un piso inferior para su primer intento. Digamos que elige abordar el problema de 20 pisos a la vez y que el primer piso fatal es el # 50. En ese caso, su primer gato sobrevivirá a los vuelos desde los pisos 20 y 40 antes de morir desde el piso 60. Solo tiene que revisar los pisos 41 a 49 individualmente. Eso es un total de 12 intentos, que es mucho mejor que los 50 que necesitarías si hubieras intentado usar la eliminación binaria.

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

Suponga que todos los gatos son equivalentes: todos sobrevivirán o morirán de una caída desde una ventana determinada. Además, cada intento es independiente: si un gato sobrevive a una caída, no sufre ningún daño.

Esto no es tarea, aunque puede que la haya resuelto para la asignación escolar una vez. Es solo un problema caprichoso que 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 solució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, debería explicarse por sí misma:

• Si el primer gato es arrojado del piso k-ésimo y muere, ahora tenemos k - 1pisos para verificar (todo a continuación k) y m - 1gatos ( a[k - 1][m - 1]).
• Si el gato sobrevive, n - kquedan pisos (todos los pisos superiores k) y todavía hay mgatos.
• El peor de los dos casos debe ser elegido, por lo tanto max.
• + 1 proviene del hecho de que acabamos de usar un intento (independientemente de si el gato ha sobrevivido o no).
• Intentamos 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 ken otra matriz.

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

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

Según un episodio reciente de Radiolab (sobre "Falling") , 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.

Imagina que estás en un edificio alto con un gato. El gato puede sobrevivir a una caída por una ventana de piso bajo, pero morirá si lo arroja desde un piso alto. ¿Cómo puedes calcular la caída más larga que el gato puede sobrevivir, utilizando el menor número de intentos?

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

Si lo hubiera hecho, se daría cuenta de que las posibilidades de supervivencia del gato en realidad 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 desde una montaña cada vez más alta, como el monte everest.

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

El gráfico de la probabilidad de que el gato muera en función de la altitud sobre el suelo se ve así:
(termina en 3, porque la distribución de camellos sin terminar)

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

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

Créditos:
Goooooogle

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

Leí por primera vez 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 probar límites precisos en la estrategia . Primero el enunciado del problema, luego la solución a continuación.

Los huevos se rompen cuando se caen desde una altura lo suficientemente grande. Dado un edificio de n pisos, debe haber un piso f tal que los huevos caigan del piso f se rompan, pero los huevos caídos del piso f-1 sobreviven. (Si el huevo se rompe desde cualquier piso, diremos f = 1. Si el huevo sobrevive desde cualquier piso, diremos f = n + 1).

Buscas encontrar el piso crítico f. La única operación que puede realizar es dejar caer un huevo del piso y ver qué sucede. Empiezas con k huevos y buscas soltar los huevos lo menos posible. Los huevos rotos no se pueden reutilizar (los huevos intactos sí). Sea E (k, n) el número mínimo de excrementos de huevo que siempre será suficiente.

1. Demuestre que E (1, n) = n.
2. Muestra eso E(k,n) = Θ(n**(1/k)).
3. 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 desde cada piso comenzando por 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 que se ha visto que el huevo no se rompa. El algoritmo debe probar el piso g + 1 antes de cualquier piso más alto h> g + 1; de lo contrario, si el huevo se separara del piso h, no podría distinguir entre f = g + 1 y f = h.

2 huevos

Primero, consideremos el caso de k = 2 huevos, cuando n = r ** 2 es un cuadrado perfecto. Aquí hay una estrategia que toma 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 dejamos caer el segundo huevo de cada piso a partir de (a-1)r. Cuando se rompe el segundo huevo, hemos encontrado el piso crítico. Dejamos caer cada huevo en la mayoría de los casos, por lo que este algoritmo toma en el peor de los casos las operaciones 2r, que es Θ (sqrt (n)).

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

Prueba de que cualquier algoritmo lleva al menos tiempo sqrt (n). Supongamos que hay un algoritmo más rápido. Considere la secuencia de pisos desde los que 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. Suelta cada huevo con intervalos constantes, que deben tomarse como las potencias de la raíz k de n. Por ejemplo, para n = 1000 yk = 3, busque intervalos de 100 pisos con el primer huevo, 10 con el segundo huevo y 1 con el último huevo.

Del mismo modo, podemos demostrar que ningún algoritmo es más rápido Θ(n**(1/k))al inducir a partir de la prueba k = 2.

Solución exacta

Deducimos la recurrencia optimizando dónde colocar 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 debajo para explorar con los huevos k-1. Si el huevo sobrevive, tenemos pisos superiores para explorar con k huevos. El diablo elige lo peor para nosotros. Así, para k> 1 la recurrencia

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..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 los supuestos correctos, 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ías tratar de determinar la respuesta empíricamente, pero creo que habría suficientes diferencias estadísticas que la respuesta carecería de significado estadístico.

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

O bien, puede agregar la salud del gato, tomar muestras a intervalos extremadamente cercanos y encontrar las alturas para las cuales el gato está "mayormente vivo" (en oposición a "mayormente muerto" 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, votaré por comenzar lo más alto posible y continuar soltando gatos a medida que la altura disminuya hasta que estadísticamente sobrevivan. Y luego vuelva a probar en los gatos sobrevivientes para estar seguro.

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

Comencé trabajando en el piso máximo que podría cubrirse usando x cats e y adivina usando el siguiente método.

Comience con 1 piso y siga aumentando el número de conjeturas mientras realiza un seguimiento de los pisos verificados, qué conjeturas se verificaron y cuántos gatos quedaban por cada piso.
Repita esto hasta y veces.

Este código muy ineficiente para calcular la respuesta dada, pero ú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 (principalmente que involucraba escribir secuencias de números en OEIS ) noté que los pisos máximos para x siguen un patrón de combinación por partes.

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)

A partir de aquí, tomé el enfoque fácil de incrementar de manera simple 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 proporciona la solución correcta para (100, 2) = 14.
Para cualquiera que desee verificar algo menos trivial, proporciona (1 000 000, 5) = 43.

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

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). 

No puedo leer el google blogspot sobre esto (gracias al blogwall de obras) pero no creo que una búsqueda directa de estilo binario sea mejor. La razón es que una búsqueda binaria se basa en la noción de que la respuesta que está buscando tiene la misma probabilidad de estar en cualquier índice de índice de 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 del otro. No tengo idea de cómo incluir eso en la búsqueda, pero es un pensamiento interesante.

toda esta alocada charla sobre gatos ... y es solo una suposición el problema del número con suposiciones mínimas (número de gatos). tampoco debería ser necesario definir artificialmente (e incorrectamente) el infinito como parte de la solución. la variable debería haber sido denominada límite superior o max-try o algo así. Sin embargo, la definición del problema (lo del gato) tiene algunos problemas serios, ya que las personas responden al potencial de crueldad hacia los animales y también a las muchas facetas de dicho problema planteado en la vida real, por ejemplo, arrastre aéreo, la gravedad es la aceleración y otros parámetros de la vida real. del problema. entonces quizás debería haberse preguntado de una manera totalmente diferente.