Lanzar gatos por las ventanas

150

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.

AndrewF
fuente
123
Me opongo al uso de gatos de la manera descrita. ¿Podemos cambiarlo a perros?
Thilo
53
No es tan simple. Se han realizado estudios (de gatos que se caen accidentalmente de los rascacielos, no se los arroja). Hubo un cierto rango donde murieron, y un rango *** más alto que este *** donde sobrevivieron. Algo sobre cómo tensaron sus cuerpos.
Andrew Shepherd
55
He leído en algún lugar que 15 pies o más, los gatos tienen una mayor probabilidad de sobrevivir. Esta pregunta sería más adecuada si abandonáramos a ex novias y / o esposas molestas.
Anthony Forloney el
34
Sabes, si comienzas con dos gatos, PODRÍAS esperar unos meses y luego realizar una búsqueda binaria. O espere unos meses después de eso y haga una "búsqueda simultánea", en la que obtenga ayudantes para arrojar gatos desde todos los pisos al mismo tiempo; el recuento de gatos sobrevivientes en ese caso es el número más alto desde el que puede arrojarlos, por supuesto .
mjfgates
10
Con conejitos, cambie "meses" a "semanas".
mjfgates

Respuestas:

70

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 .

Nikita Rybak
fuente
Hmm, ¿no es + 1necesario estar fuera min()? Como usted mismo dice, si el intento es exitoso o no, sigue siendo un intento.
j_random_hacker
@j_random_hacker ¿Cambia algo? Moviéndose +1fuera de min. O moviéndolo dentro de max:)
Nikita Rybak
@Nikita: Lo siento, de alguna manera leí mal lo que escribiste, ¡lo que tienes es exactamente correcto para mí! +1.
j_random_hacker
Tenga en cuenta que esto es idéntico al "problema de la caída del huevo" de Google Code Jam. La solución O (n ^ 3) a continuación no es lo suficientemente buena, porque el conjunto de problemas grandes usa N = 2000000000. code.google.com/codejam/contest/dashboard?c=32003#s=p2
ripper234
1
Vea esta nueva pregunta para un algoritmo O (n). La respuesta principal al Google Code Jam es O (n), pero aún no lo entiendo. stackoverflow.com/questions/4699067/…
ripper234
92

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.

Thilo
fuente
16
Como persona de gatos, me gustaría señalar que este estudio se basó en informes de hospitales de animales después de incidentes de defenestración. Ningún gato adicional resultó herido o inconveniente en esta investigación.
Thilo
16
No es una respuesta, solo un contexto adicional del dominio empresarial.
Thilo
19
Es una respuesta tan buena como la pregunta merece.
Mark Ransom
2
Esto solo muestra que no es un caso de live = 1, die = 0 como resultado, sino más de live = 1.0, die = 0.0 y todo lo demás son probabilidades. También es una curva, no una línea, que necesita ser descubierta.
tadman
73
El problema con ese informe es el sesgo de selección: nadie lleva un gato muerto al veterinario.
Niki Yoshiuchi
10

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)

texto alternativo

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


Stefan Steiger
fuente
2
¿Es esto correcto? Seguramente una vez que se alcanza la velocidad terminal, las posibilidades no pueden cambiar, y tenía la impresión de que un gato puede sobrevivir a una caída de velocidad terminal.
ZoFreX
44
@ZoFreX: Claro que sí, es la velocidad terminal justo debajo de la más fatal. Por otro lado, deja caer un gato, digamos cien mil millas arriba, y es más probable que el gato se queme en la atmósfera después de morir del vacío que caerse y vivir.
David Thornley
1
¿Son esas orejas de conejo en ese gráfico?
ninjalj
1
@ZoFreX: momento angular. Un gato siempre cae de pie, debido al impulso angular debido al diseño del cuerpo del gato y las habilidades de giro del gato. Pero eso todavía significa que necesita tiempo para girar. Cuanto más tiempo haya (==> cuanto mayor sea la altitud), más probable será que el gato caiga de pie (==> las posibilidades de supervivencia aumentan dramáticamente, en lugar de, por ejemplo, aterrizar en la cabeza). Pero tienes razón, la probabilidad se mantiene igual después de alcanzar la velocidad terminal. Diría que es muy probable que un gato pueda sobrevivir a una caída de velocidad terminal, al menos la mía saltó por la ventana del baño (aprox. 20 m), sin un rasguño.
Stefan Steiger
8

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
Coronel Panic
fuente
Si tengo k huevos, ¿por qué no es el tiempo O(k*n**(1/k))de ejecución para el peor de los casos? Como en el peor de los casos tengo que pasar por momentos n**(1/k) exactos k.
Rakete1111
2

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

Bagazo
fuente
0

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

Threenplusone
fuente
0
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). 
tldr
fuente
-1

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.

drekka
fuente
1
Creo que la pregunta es el mejor y el peor de los casos, por lo que la distribución es irrelevante siempre que sea posible cada piso.
Steve Jessop
-1

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.

Chris
fuente
FWIW puede ser un problema disfrazado de la vida real. Suponga que tiene una prueba automática que falla en la versión 1234 pero funcionó en la versión 42. El gato está muerto en 1234 pero vive en la versión 42. ¿Qué revisión lo mató? Si la actualización, por ejemplo, de la 42 a la 43, es rápida y fácil, pero revisar y reconstruir una nueva versión es difícil, esto comienza a parecerse mucho al problema del gato.
mcdowella