Вы работаете в 15-этажном здании и имеете три одинаковых жестких диска. Вы хотите определить – при броске с максимально какого этажа диск останется целым. Если он разобьется даже при броске с первого этажа, то ответ 0. Вы можете бросать имеющиеся диски с любого этажа, причем, если диск не разбился, то его можно бросать повторно.
Какое минимальное количество бросков вам придется сделать в худшем случае? Можно было бы бросать всего один диск сначала с первого этажа, потом – второго и т.д., но, конечно, вы можете гарантированно решить задачу за меньшее число бросков.
Вы работаете в 15-этажном здании и имеете три одинаковых жестких диска. Вы хотите определить – при броске с максимально какого этажа диск останется целым. Если он разобьется даже при броске с первого этажа, то ответ 0. Вы можете бросать имеющиеся диски с любого этажа, причем, если диск не разбился, то его можно бросать повторно.
Какое минимальное количество бросков вам придется сделать в худшем случае? Можно было бы бросать всего один диск сначала с первого этажа, потом – второго и т.д., но, конечно, вы можете гарантированно решить задачу за меньшее число бросков.
Какое минимальное количество бросков вам придется сделать в худшем случае? Можно было бы бросать всего один диск сначала с первого этажа, потом – второго и т.д., но, конечно, вы можете гарантированно решить задачу за меньшее число бросков.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи можно воспользоваться методом бинарного поиска. Для этого разделим здание на блоки по 5 этажей, например:
Блок 1: этажи с 1 по 5
Блок 2: этажи с 6 по 10
...
Блок 3: этажи с 11 по 15
Затем начнем бросать первый диск с пятого этажа, потом десятого и т.д., пока не найдем этот блок, в котором диск разобьется. После этого возьмем второй диск и будем бросать его от нижней границы найденного блока до этажа, где первый диск разбился. Таким образом, мы уменьшим количество бросков в худшем случае до 6.