Jogando gatos pela janela

150

Imagine que você está em um prédio alto com um gato. O gato pode sobreviver a uma queda de uma janela baixa, mas morrerá se jogado de um andar alto. Como você pode descobrir a queda mais longa que o gato pode sobreviver, usando o menor número de tentativas?

Obviamente, se você tiver apenas um gato, poderá pesquisar apenas linearmente. Primeiro jogue o gato do primeiro andar. Se sobreviver, jogue-o a partir do segundo. Eventualmente, depois de ser jogado do chão f, o gato morre. Você sabe que o piso f-1 era o piso seguro máximo.

Mas e se você tiver mais de um gato? Agora você pode tentar algum tipo de pesquisa logarítmica. Digamos que a construção tenha 100 andares e você tenha dois gatos idênticos. Se você atirar o primeiro gato para fora do 50º andar e ele morrer, será necessário procurar apenas 50 andares linearmente. Você pode melhorar ainda mais se escolher um piso inferior para sua primeira tentativa. Digamos que você opte por resolver o problema 20 andares por vez e que o primeiro andar fatal seja o número 50. Nesse caso, seu primeiro gato sobreviverá aos vôos dos andares 20 e 40 antes de morrer do andar 60. Você só precisa verificar os andares 41 a 49 individualmente. São 12 tentativas, o que é muito melhor do que as 50 que você precisaria se tentasse usar a eliminação binária.

Em geral, qual é a melhor estratégia e a pior complexidade possível para um edifício de dois andares com dois gatos? E quanto a n andares e m gatos?

Suponha que todos os gatos sejam equivalentes: todos sobreviverão ou morrerão de uma queda de uma determinada janela. Além disso, toda tentativa é independente: se um gato sobrevive a uma queda, é completamente ileso.

Isso não é tarefa de casa, embora eu possa ter resolvido isso uma vez na escola. É apenas um problema extravagante que me veio à cabeça hoje e não me lembro da solução. Pontos de bônus se alguém souber o nome desse problema ou do algoritmo da solução.

AndrewF
fonte
123
Oponho-me ao uso de gatos da maneira descrita. Podemos mudar para cães?
Thilo
53
Não é tão simples assim. Estudos foram feitos (de gatos caindo acidentalmente de arranha-céus, sem serem jogados). Havia um certo intervalo em que eles morreram, e um intervalo maior que este ***, onde eles sobreviveram. Algo sobre como eles enrijeceram seus corpos.
Andrew Shepherd
5
Eu li em algum lugar que 15 pés ou mais, os gatos têm uma chance maior de sobreviver. Esta pergunta seria mais adequada se deixássemos ex-namoradas e / ou esposas irritantes.
Anthony Forloney
34
Você sabe, se você começar com dois gatos, poderá esperar alguns meses e depois executar uma pesquisa binária. Ou então, espere alguns meses e faça uma "pesquisa simultânea", na qual você recebe ajudantes para atirar gatos de todos os andares simultaneamente - a contagem de gatos sobreviventes nesse caso é o número de andar mais alto do qual você pode jogá-los, é claro .
mjfgates
10
Nos coelhos, mude "meses" para "semanas".
mjfgates

Respostas:

70

Você pode escrever facilmente um pouco de DP (programação dinâmica) para o caso geral de n andares e m gatos.

A fórmula principal,, a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..ndeve ser auto-explicativa:

  • Se o primeiro gato é jogado do k-ésimo andar e morre, agora temos k - 1andares para checar (todos abaixo k) e m - 1gatos ( a[k - 1][m - 1]).
  • Se o gato sobrevive, há n - kandares restantes (todos os andares acima k) e ainda mgatos.
  • O pior caso de dois deve ser escolhido, portanto max.
  • + 1 vem do fato de que acabamos de usar uma tentativa (independentemente de o gato ter sobrevivido ou não).
  • Tentamos todos os pisos possíveis para encontrar o melhor resultado min(f(k)) : for k in 1..n.

Ele concorda com o resultado do Google no link 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]);

Você pode encontrar facilmente a estratégia (como jogar o primeiro gato), se salvar melhor kem outra matriz.

Também existe uma solução mais rápida, que não envolve cálculos de O (n ^ 3), mas já estou com um pouco de sono.

edit
Ah, sim, eu lembro onde vi esse problema antes .

Nikita Rybak
fonte
Hmm, a + 1necessidade de ficar de fora da min()? Como você diz, se a tentativa foi bem-sucedida ou não, ainda é uma tentativa.
Jrandom_hacker
@j_random_hacker Isso muda alguma coisa? Movendo-se para +1fora de min. Ou movê-lo dentro de max:)
Nikita Rybak
@ Nikita: Me desculpe, de alguma forma, não entendi bem o que você escreveu - o que você tem está exatamente certo para mim! +1.
Jrandom_hacker 23/10/10
Observe que isso é idêntico ao "Problema da gota de ovo" do Google Code Jam. O O (n ^ 3) abaixo solução não é suficiente, porque o conjunto grande problema utiliza N = 2000000000. code.google.com/codejam/contest/dashboard?c=32003#s=p2
ripper234
1
Veja esta nova pergunta para um algoritmo O (n). A resposta principal para o Google Code Jam é O (n), mas ainda não o entendo. stackoverflow.com/questions/4699067/...
ripper234
92

De acordo com um episódio recente do Radiolab (sobre "Queda") , um gato atinge a velocidade terminal no 9º andar. Depois disso, relaxa e é menos provável que se machuque. Existem gatos completamente não lesionados após uma queda acima do dia 30. Os andares mais arriscados são do 5º ao 9º.

Thilo
fonte
16
Como pessoa felina, gostaria de salientar que este estudo foi baseado em relatórios de hospitais de animais após incidentes de defestação. Nenhum gato adicional foi ferido ou incomodado neste inquérito.
Thilo
16
Não é uma resposta, apenas um contexto adicional do domínio comercial.
Thilo
19
É a resposta que a pergunta merece.
Mark Ransom
2
Isso apenas mostra como não é o caso de viver = 1, morrer = 0 como resultado, mas viver mais = 1,0, morrer = 0,0 e tudo o que há entre probabilidades. É também uma curva, não uma linha, que precisa ser descoberta.
Tadman
73
O problema desse relatório é o viés de seleção - ninguém leva um gato morto ao veterinário.
Niki Yoshiuchi 20/10/10
10

Imagine que você está em um prédio alto com um gato. O gato pode sobreviver a uma queda de uma janela baixa, mas morrerá se jogado de um andar alto. Como você pode descobrir a queda mais longa que o gato pode sobreviver, usando o menor número de tentativas?

A melhor estratégia para resolver esse problema é investigar, usando a lei da física, a probabilidade de suas suposições serem verdadeiras em primeiro lugar.

Se você o tivesse feito, perceberia que as chances de sobrevivência do gato aumentam quanto maior a distância do solo. Obviamente, supondo que você o jogue de um edifício cada vez mais alto, como as torres petronas, e não de uma montanha cada vez mais alta, como o monte everest.

Edit:
Na verdade, você veria uma distribuição inacabada de camelos.
Primeiro, a probabilidade de o gato morrer é baixa (altitude muito baixa), depois fica mais alta (altitude baixa), depois mais baixa (altitude mais alta) e depois novamente mais alta (altitude muito alta).

O gráfico para a probabilidade de um gato morrer em função da altitude acima do solo é assim:
(termina em 3, porque a distribuição inacabada de camelos)

texto alternativo

Atualização:
a velocidade terminal de um gato é de 100 km / h (60 mph) [= 27,7m / s = 25,4 jardas / s].
A velocidade terminal humana é de 210 km / h (130 mph). [= 75m / s = 68,58 jardas / s]

Fonte de velocidade terminal:
http://en.wikipedia.org/wiki/Cat_righting_reflex

Créditos:
Goooooogle

Preciso verificar mais tarde:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov /WWW/K-12/airplane/termv.html


Stefan Steiger
fonte
2
Isso está correto? Certamente, uma vez atingida a velocidade terminal, as chances não podem mudar - e fiquei com a impressão de que um gato pode sobreviver a uma queda da velocidade terminal.
ZoFreX 20/10/10
4
@ZoFreX: Claro que podem, é a velocidade terminal logo abaixo que é a mais fatal. Por outro lado, solte um gato, digamos a centenas de milhares de quilômetros, e é mais provável que o gato queime na atmosfera depois de morrer do vácuo do que cair e viver.
precisa
1
Essas orelhas de coelho estão nesse gráfico?
Njalj 20/10/10
1
@ZoFreX: momento angular. Um gato sempre cai de pé, devido ao momento angular devido ao design do corpo e às habilidades de giro do gato. Mas isso ainda significa que precisa de tempo para mudar. Quanto mais tempo houver (==> quanto maior a altitude), maior a probabilidade de o gato pousar em pé (==> as chances de sobrevivência aumentam drasticamente, em oposição a, por exemplo, pousar na cabeça). Mas você está certo, a probabilidade permanece a mesma após atingir a velocidade terminal. Eu diria que é bem provável que um gato possa sobreviver a uma queda de velocidade terminal, pelo menos o meu pulou pela janela do banheiro (aprox. 20m), sem nenhum arranhão.
Stefan Steiger
8

Li este problema pela primeira vez no Manual de design de algoritmos de Steven Skiena (exercício 8.15). Ele seguiu um capítulo sobre programação dinâmica, mas você não precisa conhecer programação dinâmica para provar limites precisos da estratégia . Primeiro a declaração do problema, depois a solução abaixo.

Os ovos partem quando caem de uma altura suficientemente grande. Dado um edifício de n andares, deve haver um piso f para que os ovos caiam do piso f, mas os ovos que caem do piso f-1 sobrevivem. (Se o ovo partir de qualquer andar, diremos f = 1. Se o ovo sobreviver de qualquer andar, diremos f = n + 1).

Você procura encontrar o piso crítico f. A única operação que você pode executar é soltar um ovo do chão e ver o que acontece. Você começa com k ovos e tenta soltar os ovos o menor número de vezes possível. Ovos quebrados não podem ser reutilizados (ovos intactos podem). Seja E (k, n) o número mínimo de excremento de ovos que sempre será suficiente.

  1. Mostre que E (1, n) = n.
  2. Mostre isso E(k,n) = Θ(n**(1/k)).
  3. Encontre uma recorrência para E (k, n). Qual é o tempo de execução do programa dinâmico para encontrar E (k, n)?

Apenas 1 ovo

Largar o ovo de cada andar, começando no primeiro, encontrará o andar crítico nas (na pior das hipóteses) n operações.

Não há algoritmo mais rápido. A qualquer momento em qualquer algoritmo, deixe g o andar mais alto a partir do qual o ovo não quebra. O algoritmo deve testar o piso g + 1 antes de qualquer piso superior h> g + 1; caso contrário, se o ovo sair do piso h, não será possível distinguir entre f = g + 1 ef = h.

2 ovos

Primeiro, vamos considerar o caso de k = 2 ovos, quando n = r ** 2 é um quadrado perfeito. Aqui está uma estratégia que leva tempo O (sqrt (n)). Comece largando o primeiro ovo em incrementos de r andares. Quando o primeiro ovo quebra, digamos no chão ar, sabemos que o piso crítico f deve estar (a-1)r < f <= ar. Em seguida, largamos o segundo ovo de cada andar a partir de (a-1)r. Quando o segundo ovo quebra, encontramos o piso crítico. Como eliminamos cada ovo no máximo r tempo, esse algoritmo leva na pior das operações 2r, que é Θ (sqrt (n)).

Quando n não é um quadrado perfeito, use r = ceil(sqrt(n)) ∈ Θ(sqrt(n)). O algoritmo permanece Θ (sqrt (n)).

Prova de que qualquer algoritmo leva pelo menos sqrt (n) tempo. Suponha que exista um algoritmo mais rápido. Considere a sequência de pisos a partir da qual ele solta o primeiro ovo (desde que não se quebre). Como cai menos que sqrt (n), deve haver um intervalo de pelo menos n / sqrt (n) que seja sqrt (n). Quando f está nesse intervalo, o algoritmo terá que investigá-lo com o segundo ovo, e isso deve ser feito passo a passo, lembrando o caso de 1 ovo. CONTRADIÇÃO.

k ovos

O algoritmo apresentado para 2 ovos pode ser facilmente estendido para k ovos. Largue cada ovo com intervalos constantes, que devem ser tomados como os poderes da k-ésima raiz de n. Por exemplo, para n = 1000 ek = 3, pesquise intervalos de 100 andares com o primeiro ovo, 10 com o segundo ovo e 1 com o último ovo.

Da mesma forma, podemos provar que nenhum algoritmo é mais rápido Θ(n**(1/k))induzindo a partir da prova k = 2.

Solução exata

Deduzimos a recorrência otimizando onde soltar o primeiro ovo (piso g), presumindo que conhecemos soluções ideais para parâmetros menores. Se o ovo quebrar, temos o piso g-1 abaixo para explorar com ovos k-1. Se o ovo sobreviver, temos os andares acima para explorar com k ovos. O diabo escolhe o pior para nós. Assim, para k> 1, a recorrência

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n
Coronel Panic
fonte
Se eu tenho k ovos, por que não é o tempo O(k*n**(1/k))de execução para o pior caso? Já que, no pior dos casos, tenho que passar n**(1/k) exatamente o ktempo.
precisa saber é o seguinte
2

Isso não pressupõe que você esteja usando "O mesmo gato"?

Você pode abordá-lo matematicamente, mas isso é bom na matemática ... com as suposições corretas, 0 pode ser igual a 1 (para valores grandes de 0).

Do ponto de vista prático, você pode obter 'Gatos Similares', mas não pode obter 'O Mesmo Gato'.

Você poderia tentar determinar a resposta empiricamente, mas eu pensaria que haveria diferenças estatísticas suficientes para que a resposta fosse estatisticamente sem sentido.

Você pode tentar usar "The Same Cat", mas isso não funcionaria, pois, após a primeira queda, não é mais o mesmo gato. (Da mesma forma, nunca se pode entrar no mesmo rio duas vezes)

Ou você pode agregar a saúde do gato, amostrando em intervalos extremamente próximos e encontrar as alturas para as quais o gato está "quase todo vivo" (ao contrário de "quase todo morto" de "The Princess Bride"). Os gatos sobreviverão, em média (até o último intervalo).

Acho que me desviei da intenção original, mas se você estiver seguindo o caminho empírico, voto por começar o mais alto possível e continuar a largar gatos à medida que a altura diminui até que eles sobrevivam estatisticamente. E, em seguida, teste novamente os gatos sobreviventes para ter certeza.

Marc
fonte
0

Eu tomei um método ligeiramente diferente para produzir uma solução.

Comecei por trabalhar fora do chão o máximo que poderia ser coberto usando x gatos e y suposições utilizando o seguinte método.

Comece com 1 andar e continue aumentando o número de palpites, mantendo o controle dos andares marcados, que acho que eles foram verificados e quantos gatos restavam para cada andar.
Repita isso até y vezes.

Este código muito ineficiente para calcular a resposta dada, mas ainda assim útil para um pequeno número de gatos / pisos.

Código 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, o piso máximo que pode ser identificado em x palpites é:
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 ...

Após uma extensa pesquisa (principalmente envolvendo digitar seqüências de números no OEIS ), notei que o número máximo de andares para x segue um padrão combinado de 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 daqui, adotei a abordagem fácil de incrementar simples n até passar o número necessário de andares.

Código 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

Isso fornece a solução correta para (100, 2) = 14.
Para quem deseja verificar algo menos trivial, fornece (1 000 000, 5) = 43.

Isso ocorre em O (n), onde n é a resposta para o problema (quanto mais gatos, melhor).
No entanto, tenho certeza de que alguém com um nível mais alto de matemática poderia simplificar as fórmulas por partes para calcular em O (1).

threenplusone
fonte
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
fonte
-1

Não consigo ler o blogspot do google sobre isso (graças ao works blogwall), mas não acho que uma pesquisa direta em estilo binário seria melhor. O motivo é que uma pesquisa binária se baseia na noção de que a resposta que você está procurando tem a mesma chance de estar em qualquer índice de índice da lista. No entanto, neste caso, isso não é verdade. Nesse caso, a resposta terá uma probabilidade maior de estar mais perto de uma extremidade do intervalo do que a outra. Não tenho idéia de como levar isso em consideração na pesquisa, mas é um pensamento interessante.

drekka
fonte
1
Acho que a pergunta está pedindo o melhor dos piores casos; portanto, a distribuição é irrelevante desde que todos os pisos sejam possíveis.
Steve Jessop
-1

toda essa conversa louca sobre gatos ... e é apenas um palpite que o problema do número com palpites mínimos (número de gatos). também não deve ser necessário definir artificialmente (e incorretamente) o infinito como parte da solução. a variável deveria ter sido chamada de limite superior ou tentativa máxima ou algo parecido. a definição do problema (a coisa do gato) tem alguns problemas sérios, com as pessoas respondendo ao potencial de crueldade animal e também as muitas facetas desse problema colocadas na vida real, por exemplo, resistência ao ar, gravidade é aceleração e outros parâmetros da vida real do problema. então talvez devesse ter sido perguntado de uma maneira totalmente diferente.

chris
fonte
FWIW, pode ser um problema disfarçado da vida real. Suponha que você tenha um teste automático que falha na versão 1234, mas funcionou na versão 42. O gato está morto na 1234, mas vive na versão 42. Que revisão o matou? Se a atualização, por exemplo, de 42 para 43 é rápida e fácil, mas é difícil verificar e reconstruir uma nova versão, isso começa a parecer muito com o problema do gato.
22611 mcdowella # 039: