Выбрасывать кошек из окон

150

Представь, что ты в высоком здании с кошкой. Кошка может пережить падение из невысокого окна, но умрет, если ее выбросить с высокого пола. Как вы можете определить самую длинную каплю, которую может выжить кошка, используя наименьшее количество попыток?

Очевидно, что если у вас есть только один кот, то вы можете искать только линейно. Сначала бросьте кота с первого этажа. Если он выживет, киньте его со второго. В конце концов, после того, как его выбросят с пола, кошка умрет. Тогда вы знаете, что этаж f-1 был максимально безопасным этажом.

Но что, если у вас есть более одного кота? Теперь вы можете попробовать какой-то логарифмический поиск. Допустим, сборка имеет 100 этажей, и у вас есть две одинаковые кошки. Если вы выбрасываете первого кота с 50-го этажа, и он умирает, то вам нужно только искать 50 этажей линейно. Вы можете сделать еще лучше, если вы выберете нижний этаж для первой попытки. Допустим, вы решили заняться проблемой 20 этажами одновременно, и что первый фатальный этаж - №50. В этом случае ваша первая кошка переживет полеты с этажей 20 и 40, а затем умрет с этажа 60. Вам просто нужно проверить этажи с 41 по 49 индивидуально. Это в общей сложности 12 попыток, что намного лучше, чем 50, которые вам понадобились бы, если бы вы попытались использовать двоичное исключение.

В общем, какова лучшая стратегия и сложность в худшем случае для n-этажного здания с 2 кошками? Как насчет n этажей и m кошек?

Предположим, что все кошки эквивалентны: все они выживут или погибнут от падения из заданного окна. Кроме того, каждая попытка независима: если кошка переживет падение, она совершенно не пострадает.

Это не домашнее задание, хотя, возможно, я однажды решил его для школьного задания. Это просто причудливая проблема, которая возникла у меня в голове сегодня, и я не помню решения. Бонусные баллы, если кто-то знает название этой проблемы или алгоритм решения.

AndrewF
источник
123
Я возражаю против использования кошек описанным способом. Можем ли мы изменить это на собак?
Тило
53
Это не так просто. Были проведены исследования (о кошках, случайно выпадающих из небоскребов, не брошенных). Был определенный диапазон, где они умерли, и диапазон *** выше, чем этот ***, где они выжили. Что-то о том, как они напрягли свои тела.
Андрей Шепард
5
Я где-то читал, что 15 футов или выше, у кошек больше шансов выжить. Этот вопрос был бы лучше, если бы мы бросали бывших подружек и / или нытье жен.
Энтони Форлони
34
Вы знаете, если вы начнете с двух кошек, вы МОЖЕТЕ просто подождать несколько месяцев, а затем запустить бинарный поиск. Или подождите несколько месяцев после этого и выполните «одновременный поиск», при котором вы получаете помощников, которые бросают кошек со всех этажей одновременно - количество выживших кошек в этом случае является наибольшим числом этажей, из которого вы, конечно, можете их бросить. ,
mjfgates
10
С кроликами измените «месяцы» на «недели».
mjfgates

Ответы:

70

Вы можете легко написать небольшое DP (динамическое программирование) для общего случая n этажей и m котов.

Основная формула, a[n][m] = min(max(a[k - 1][m - 1], a[n - k][m]) + 1) : for each k in 1..nдолжна быть самоочевидной:

  • Если первая кошка выброшена с k-го этажа и умирает, теперь у нас есть k - 1этажи для проверки (все ниже k) и m - 1cats ( a[k - 1][m - 1]).
  • Если кошка выживет, осталось несколько n - kэтажей (все этажи выше k) и все еще mкошки.
  • Следовательно, следует выбрать наихудший вариант из двух max.
  • + 1 исходит из того, что мы только что использовали одну попытку (независимо от того, выжил кот или нет).
  • Мы стараемся изо всех сил, чтобы найти лучший результат, следовательно min(f(k)) : for k in 1..n.

Это согласуется с результатом Google по ссылке Гаурава Саксены для (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]);

Вы можете легко найти стратегию (как бросить первую кошку), если лучше сохранить kв другой массив.

Есть также более быстрое решение, не требующее O (n ^ 3) вычислений, но я уже немного сонный.

редактировать
Ах да, я помню , где я видел эту проблему раньше .

Никита Рыбак
источник
Хм, разве нет + 1необходимости быть вне min()? Как вы сами говорите, удачная попытка или нет, это все же попытка.
j_random_hacker
@j_random_hacker Это что-то меняет? Переезд +1за пределы min. Или перемещая это внутрь max:)
Никита Рыбак
@ Никита: Извините, я почему-то неправильно понял, что вы написали - то, что у вас есть, совершенно верно, по мне! +1.
j_random_hacker
Обратите внимание, что это идентично «проблеме с выпадением яиц» в Google Code Jam. Приведенное ниже решение O (n ^ 3) недостаточно, потому что большой набор проблем использует N = 2000000000. code.google.com/codejam/contest/dashboard?c=32003#s=p2
ripper234
1
Посмотрите этот новый вопрос для алгоритма O (n). Лучший ответ на Google Code Jam - O (n), но я пока не понимаю. stackoverflow.com/questions/4699067/…
ripper234
92

Согласно недавнему эпизоду Radiolab (о «Падении») , кошка достигает предельной скорости на 9-м этаже. После этого он расслабляется и с меньшей вероятностью будет ранен. Есть совершенно неповрежденные кошки после падения сверху 30-го. Самые опасные этажи с 5 по 9.

Тило
источник
16
Как человек с кошкой, я хотел бы отметить, что это исследование было основано на отчетах больниц для животных после инцидентов с дефестацией. Никакие дополнительные кошки не пострадали или не пострадали в этом расследовании.
Тило
16
Не ответ, просто дополнительный контекст из бизнес-сферы.
Тило
19
Это столько же ответа, сколько заслуживает вопрос.
Марк Рэнсом
2
Это просто показывает, что это не случай live = 1, die = 0 в качестве результата, но больше live = 1.0, die = 0.0 и все, что между ними - вероятности. Это также кривая, а не линия, которую нужно обнаружить.
tadman
73
Проблема с этим отчетом заключается в предвзятости выбора - никто не ведет мертвого кота к ветеринару.
Ники Йошиути
10

Представь, что ты в высоком здании с кошкой. Кошка может пережить падение из невысокого окна, но умрет, если ее выбросить с высокого пола. Как вы можете определить самую длинную каплю, которую может выжить кошка, используя наименьшее количество попыток?

Лучшая стратегия для решения этой проблемы - исследовать, используя закон физики, вероятность того, что ваши предположения верны в первую очередь.

Если бы вы сделали это, вы бы поняли, что шансы кошки на выживание на самом деле возрастают с увеличением расстояния до земли. Конечно, если вы выбрасываете его из более высокого здания, такого как башни Петронас, а не из более высокой горы, такой как гора Эверест.

Изменить:
На самом деле, вы увидите незаконченное распределение верблюдов.
Во-первых, вероятность смерти кота мала (очень низкая высота), затем она становится выше (низкая высота), затем снова уменьшается (большая высота), а затем снова увеличивается (очень большая высота).

График вероятности смерти кота в зависимости от высоты над землей выглядит следующим образом:
(закончите на 3, потому что незаконченное распределение верблюдов)

альтернативный текст

Обновление:
конечная скорость кошки составляет 100 км / ч (60 миль в час) [= 27,7 м / с = 25,4 ярда / с].
Конечная скорость человека составляет 210 км / ч (130 миль в час). [= 75 м / с = 68,58 ярдов / с]

Терминальный источник скорости:
http://en.wikipedia.org/wiki/Cat_righting_reflex

Кредиты:
Goooooogle

Мне нужно проверить позже:
http://en.wikipedia.org/wiki/Terminal_velocity
http://www.grc.nasa.gov /WWW/K-12/airplane/termv.html


Стефан Штайгер
источник
2
Это верно? Конечно, как только достигнута предельная скорость, шансы не могут измениться - и у меня сложилось впечатление, что кошка может пережить предельное падение скорости.
ZoFreX
4
@ZoFreX: Конечно, могут, это чуть ниже предельной скорости, которые являются самыми фатальными. С другой стороны, бросьте кошку, скажем, на сто тысяч миль вверх, и кошка с большей вероятностью сгорит в атмосфере после смерти от вакуума, чем упадет и выживет.
Дэвид Торнли
1
Эти уши кролика на этом графике?
ниндзя
1
@ZoFreX: угловой момент. Кошка всегда приземляется на ноги, из-за углового момента из-за дизайна тела кошки и навыков поворота кошки. Но это все еще означает, что нужно время, чтобы повернуться. Чем больше времени (==> чем выше высота), тем больше вероятность, что кошка приземлится на ноги (==> шансы на выживание резко возрастают, в отличие, например, от приземления на голову). Но вы правы, вероятность остается неизменной после достижения предельной скорости. Я бы сказал, что вполне вероятно, что кошка сможет пережить предельное падение скорости, по крайней мере, мое выпрыгнуло из окна ванной комнаты (около 20 м) без единой царапины.
Стефан Штайгер
8

Я впервые прочитал эту проблему в Стивене Скиене алгоритмов (упражнение 8.15). Он последовал за главой о динамическом программировании, но вам не нужно знать динамическое программирование, чтобы доказать точные границы стратегии . Сначала постановка задачи, затем решение ниже.

Яйца ломаются при падении с достаточно большой высоты. Учитывая n-этажное здание, должен быть этаж f, чтобы яйца падали с пола f, но яйца, сброшенные с пола f-1, выживают. (Если яйцо разбивается с любого пола, мы скажем f = 1. Если яйцо выживет с любого пола, мы скажем f = n + 1).

Вы стремитесь найти критический этаж f. Единственная операция, которую вы можете выполнить, это сбросить яйцо с пола и посмотреть, что произойдет. Вы начинаете с k яиц и стараетесь бросать яйца как можно меньше раз. Разбитые яйца нельзя использовать повторно (неповрежденные яйца могут). Пусть E (k, n) будет минимальным количеством помета яиц, которого всегда будет достаточно.

  1. Покажите, что E (1, n) = n.
  2. Покажи это E(k,n) = Θ(n**(1/k)) .
  3. Найти повторение для E (k, n). Каково время работы динамической программы для поиска E (k, n)?

Только 1 яйцо

Сброс яйца с каждого этажа, начиная с первого, найдет критический этаж в (в худшем случае) n операций.

Нет более быстрого алгоритма. В любое время в любом алгоритме, пусть g самый высокий этаж, с которого было замечено, что яйцо не разбилось. Алгоритм должен проверять этаж g + 1 перед любым верхним этажом h> g + 1, иначе, если яйцо оторвется от пола h, он не сможет различить f = g + 1 и f = h.

2 яйца

Сначала рассмотрим случай k = 2 яиц, когда n = r ** 2 - идеальный квадрат. Вот стратегия, которая занимает O (sqrt (n)) время. Начните с того, что опустите первое яйцо с шагом r этажа. Когда первое яйцо разбивается, скажем, на этаже ar, мы знаем, что критический этаж f должен быть (a-1)r < f <= ar. Затем мы бросаем второе яйцо с каждого этажа, начиная с (a-1)r. Когда второе яйцо разбивается, мы нашли критический этаж. Мы отбрасывали каждое яйцо не более r раз, поэтому этот алгоритм выполняет в худшем случае 2r операций, что составляет Θ (sqrt (n)).

Когда n не является идеальным квадратом, возьмем r = ceil(sqrt(n)) ∈ Θ(sqrt(n)) . Алгоритм остается Θ (sqrt (n)).

Доказательство того, что любой алгоритм требует как минимум sqrt (n) времени. Предположим, есть более быстрый алгоритм. Рассмотрим последовательность этажей, с которых оно сбрасывает первое яйцо (пока оно не разбивается). Поскольку он падает меньше, чем sqrt (n), интервал должен быть не менее n / sqrt (n), который равен sqrt (n). Когда f находится в этом интервале, алгоритм должен будет исследовать его со вторым яйцом, и это должно быть сделано поэтапно, напоминая случай с 1 яйцом. ПРОТИВОРЕЧИЕ.

к яиц

Алгоритм, представленный для 2 яиц, может быть легко расширен до k яиц. Отбрасывайте каждое яйцо с постоянными интервалами, которые следует принимать в качестве степеней k-го корня n. Например, для n = 1000 и k = 3, ищите интервалы в 100 этажей с первым яйцом, 10 с вторым яйцом и 1 с последним яйцом.

Точно так же мы можем доказать, что ни один алгоритм не быстрее Θ(n**(1/k)), индуцируя из k = 2 доказательства.

Точное решение

Мы выводим рецидив, оптимизируя, куда бросить первое яйцо (пол g), предполагая, что мы знаем оптимальные решения для меньших параметров. Если яйцо разбивается, у нас есть этажи g-1 ниже, чтобы исследовать с яйцами k-1. Если яйцо выживет, у нас есть n этажей выше, чтобы исследовать его с k яйцами. Дьявол выбирает худшее для нас. Таким образом, при k> 1 повторение

E(k,n) = min(max(E(k,n-g), E(k-1,g))) minimised over g in 1..n
Полковник паника
источник
Если у меня есть k яиц, почему не время выполнения O(k*n**(1/k))в худшем случае? Так как в худшем случае мне приходится проходить n**(1/k) ровно kраз.
Rakete1111
2

Разве это не предполагает, что вы используете "Тот же кот"?

Вы можете приблизиться к нему математически, но это хорошо в математике ... с правильными предположениями, 0 может равняться 1 (для больших значений 0).

С практической точки зрения, вы можете получить «Похожие кошки», но вы не можете получить «Та же самая кошка».

Вы можете попытаться определить ответ эмпирически, но я думаю, что статистических различий будет достаточно, чтобы ответ был статистически бессмысленным.

Вы можете попытаться ИСПОЛЬЗОВАТЬ «Тот же самый кот», но это не сработает, так как после первого падения это уже не тот же кот. (Аналогично, никто не может дважды войти в одну и ту же реку)

Или вы можете собрать данные о состоянии здоровья кошки, взяв пробы через очень короткие промежутки времени и найти высоты, для которых кошка «в основном жива» (в отличие от «в основном мертвых» из «Невесты принцессы»). Кошки выживут в среднем (до последнего интервала).

Я думаю, что отклонился от первоначального намерения, но если вы идете эмпирическим путем, я голосую за то, чтобы начать как можно выше и продолжать сбрасывать кошек по мере уменьшения высоты, пока они статистически не выживут. А потом еще раз проверить выживших кошек, чтобы быть уверенным.

Марк
источник
0

Я выбрал немного другой метод, чтобы найти решение.

Я начал с определения максимального пола, который можно было бы покрыть, используя х кошек и у догадок , используя следующий метод.

Начните с 1 этажа и продолжайте увеличивать количество догадок, сохраняя при этом проверку этажей, которые предполагают, что они проверены, и сколько кошек осталось на каждом этаже.
Повторите это до у раз.

Это очень неэффективный код для вычисления данного ответа, но тем не менее полезный для небольшого количества кошек / этажей.

Код 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)

Для 2 кошек максимальные этажи, которые можно определить в x догадках:
1, 3, 6, 10, 15, 21, 28 ...

Для 3 кошек:
1, 3, 7, 14, 25, 41, 63 ...

Для 4 кошек:
1, 3, 7, 15, 30, 56, 98 ...

После обширных исследований (в основном связанных с набором последовательностей чисел в OEIS ), я заметил, что максимальные этажи для x соответствуют кусочно- комбинационной комбинации .

Для 2 кошек:
n <2: 2 ^ n - 1
n> = 2: C (n, 1) + C (n, 2)

Для 3 кошек:
n <3: 2 ^ n - 1
n> = 3: C (n, 1) + C (n, 2) + C (n, 3)

Для 4 кошек:
n <4: 2 ^ n - 1
n> = 4: C (n, 1) + C (n, 2) + C (n, 3) + C (n, 4)

Отсюда я взял простой подход простого увеличения n, пока не пройду необходимое количество этажей.

Код 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

Это дает правильное решение для (100, 2) = 14.
Для любого, кто хочет проверить что-то менее тривиальное, оно дает (1 000 000, 5) = 43.

Это работает в O (n), где n является ответом на проблему (чем больше кошек, тем лучше).
Однако я уверен, что кто-то с более высоким уровнем математики мог бы упростить кусочные формулы для вычисления в O (1).

threenplusone
источник
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
источник
-1

Я не могу прочитать об этом блог блогов Google (благодаря работам blogwall), но я не думаю, что прямой поиск в двоичном стиле будет лучше. Причина в том, что бинарный поиск основан на представлении о том, что искомый ответ имеет равные шансы оказаться при любом индексе индекса в списке. Однако в этом случае это не так. В этом случае ответ будет иметь более высокую вероятность быть ближе к одному концу диапазона, чем к другому. Я понятия не имею, как учесть это в поиске, но это интересная мысль.

drekka
источник
1
Я думаю, что вопрос задает лучший худший случай, поэтому распределение не имеет значения, пока возможен каждый этаж.
Стив Джессоп
-1

все эти сумасшедшие разговоры о кошках .. и это всего лишь угадать проблему числа с минимальными догадками (количество кошек). не должно быть необходимости искусственно (и неправильно) определять бесконечность как часть решения. переменная должна была иметь название upper-bound или max-try или что-то подобное. определение проблемы (вещь кошки) имеет некоторые серьезные проблемы, хотя люди реагируют на потенциал жестокого обращения с животными, а также на многие аспекты такой проблемы, возникающей в реальной жизни, например, аэродинамическое сопротивление, гравитация - ускорение и другие подобные параметры реальной жизни. проблемы. так что, возможно, это должно было быть задано совершенно по-другому.

Крис
источник
FWIW это может быть замаскированная проблема реальной жизни. Предположим, что у вас есть автоматический тест, который не проходит в версии 1234, но работает в версии 42. Кот мертв в 1234, но живет в версии 42. Какая ревизия убила его? Если обновление, например, с 42 до 43, происходит быстро и легко, но проверить и перестроить новую версию сложно, это начинает очень похоже на проблему кошки.
McDowella