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

Question

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

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

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

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

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

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

Answer 1

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

.

Answer 2

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

Это согласуется с результатом Google из ссылки Gaurav Saxena для (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) вычислений, но я уже немного сонный.

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

Answer 3

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

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

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

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

График вероятности гибели кошки в зависимости от высоты над землей выглядит следующим образом:
(заканчивается на 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

Answer 4

Впервые я прочитал эту проблему в Руководстве по разработке алгоритмов Стивена Скиены (упражнение 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 операций, что равно is (sqrt (n)).

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

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

k яиц

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

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

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

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

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

Answer 5

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

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

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

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

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

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

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

Answer 6

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

Answer 7

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

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

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

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

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 <br>n> = 2: C(n, 1) + C (n, 2)

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

Для 4 кошек:
n <4: 2 ^ n - 1 <br>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).

Answer 8

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

Answer 9

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