Стеклянные шары и небоскрёб
Обновлено: 14 января 2024 (уточнены формулировки, исправлены неточности)
Изучая алгоритмы и решая различные задачи порой сталкиваешься с такими, которые простые лишь с виду. А на деле имеют весьма оригинальное решение, дойти до которого сходу ну никак нельзя.
Условие
Мы стоим возле высокого небоскрёба высотой в 100 этажей. Нам дали два стеклянных шара. Да таких, что их стекло достаточно прочное, чтобы выдержать падение с высоты нескольких десятков или даже сотен метров. Записка: «Есть этаж, начиная с которого эти шары начинают разбиваться. За какое минимальное количество бросков мы гарантированно определим этот этаж?».
Решение
Немного подумав, решим так: раз у меня есть два шара, то я могу бросить шар с какого-нибудь этажа и посмотреть, разобьётся он или нет. Будем хитрее и выберем 50-тый этаж. Ровно посередине.
«Итак, вперёд, идём в лифт… Стоп! А если шар разобьётся, что же тогда делать? У меня останется всего один шар, но зато я буду знать что искомый этаж максимум 50-тый. А если 49? Или 48? А может вообще первый? Можно бросить наугад, например, с 25-го. А если и он разобьётся? Тогда я точно не узнаю нужный этаж. Тут нужен правильный подход…».
Конечно, шар может и не разбиться с 50-го этажа. Тогда мы можем бросать дальше. Например, с 75-го. Здесь мы используем алгоритм двоичного поиска. Благодаря логарифмической сложности по времени и не без удачи сможем найти нужный этаж за небольшое количество бросков.
Например, если нужный нам этаж - 51, то для его определения может быть достаточно 3 броска:
- 50 (первый шар не разбился)
- 75 (первый шар разбился)
- 51 (второй шар разбился, уже не используем двоичный поиск; перебираем подряд, поднимаясь по одному этажу наверх)
Однако, здесь следует учесть, что для решения исходной задачи нужно брать во внимание наихудший случай. Для «удачных» вариантов, как в примере выше, считать броски не имеет смысла, так как наилучший случай: один бросок с первого этажа — шар разбился. Нам он не интересен.
Наихудшим случаем будет бросок с 50-го этажа (предполагаем, что нам хватило ума не кидать откуда-то с самого верха небоскрёба) и разбившийся от этого шар. А искомый этаж — 49. Единственным решением в этом случае будет бросать оставшийся второй шар, начиная с первого этажа до 49-го. В итоге мы потратим 1 + 49 = 50 бросков.
Много.
Разве нельзя меньше? Может стоит бросать по-другому? Очевидно, да.
Таким образом, мы ищем наилучший случай из наихудших. В данном случае — минимакс.
Предположим, что искомое количество бросков равно \(X\). Каждый раз бросая шар мы должны учитывать, что общее количество бросков не должно превысить \(X\).
Как этого достичь?
В примере выше, когда шар разбивается уже после первого броска, нам приходится бросать начиная с самого первого. Значит, первый бросок нужно сделать с расчётом, что нам понадобится перебирать этажи ниже него. А это возможно лишь в одном случае — если мы бросали с этажа под номером \(X\). Если же шар не разбился, то у нас осталось еще \(X-1\) бросков. Возникает та же ситуация: нам нужно бросить с такого этажа, чтобы в случае, если шар разобьётся, общее количество бросков не превысило \(X-1\). А значит нужно бросить с этажа на \(X-1\) выше. Таким “повышением” номера этажа мы покроем максимальное количество этажей, с которых шар потенциально может разбиться. Если шар вновь не разбился, то дальше лучшим решением будет бросить ещё на \(X-2\) этажей выше. И так будет повторяться каждый раз, пока мы не дойдем до вершины небоскрёба.
Нетрудно видеть, что в результате мы получим последовательность:
\[ X + (X - 1) + (X - 2) + … + 1 \]
Для получения уравнения достаточно приравнять эту последовательность к нашему числу этажей в небоскрёбе — 100. Однако, может получиться нецелое число, что, конечно, нам не подойдёт. Поэтому искомое неравество будет выглядеть:
\[ X + (X - 1) + (X - 2) + … + 1 \ge 100 \]
Cумма в левой части ни что иное, как сумма арифметической прогрессии. Получаем:
\[ \frac{X*(X+1)}{2} \ge 100 \]
Решив неравенство, получим:
\[ X \ge 14 \]
Нам нужно минимальное количество бросков, следовательно:
\[ X = 14 \]
Таким образом, следует бросать со следующих этажей:
\[ 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 \]
Рассмотрим пример. Если первый шар разбился, например, на 77 этаже (т.е. после седьмого броска), то продолжаем бросать так:
\[ 70, 71, 72, 73, 74, 75, 76 \]
В худшем случае, если искомый этаж 76 (шар с него разбился) или 77 (шар с 76 этажа не разбился), получим еще 7 бросков. Итого — 14.
Итоговое количество бросков будет тем меньше, чем ближе номер искомого этажа к левой границе отрезков \([1;14], [14;27], [27;39]\) и т.д.
Ответ
Для гарантированного определения этажа 100-этажного небоскрёба, с которого начинают разбиваться стеклянные шары, нужно минимум 14 бросков.
Реализация
Для вычисления минимального количества бросков можно использовать методику динамического программирования.