Question

Вы работаете в 15-этажном здании и имеете три одинаковых жестких диска. Вы хотите определить – при броске с максимально какого этажа диск останется целым. Если он разобьется даже при броске с первого этажа, то ответ 0. Вы можете бросать имеющиеся диски с любого этажа, причем, если диск не разбился, то его можно бросать повторно. Какое минимальное количество бросков вам придется сделать в худшем случае? Можно было бы бросать всего один диск сначала с первого этажа, потом – второго и т.д., но, конечно, вы можете гарантированно решить задачу за меньшее число бросков.

Answer 1

Задача решена ввиде графа
Цвет стрелочки показывает номер действия
Значит максимально действий нужно 5

Answer 2

Для решения этой задачи вам необходимо использовать метод бинарного поиска. Этот метод является эффективным способом поиска в отсортированном списке и в данном случае позволяет определить максимальный этаж, с которого можно безопасно бросить диск, минимизируя количество бросков. 1. Сначала определите диапазон возможных этажей. В данном случае это будет от 1 до 15 этажа. 2. Затем, используя бинарный поиск, определите "серединный" этаж. Если количество этажей нечетное, выберите любой из середины. Например, если у вас 15 этажей, "серединный" этаж будет 8. 3. Сбросьте диск с "серединного" этажа. Если диск не разбился, это означает, что диск может выдерживать бросок с этажей выше "серединного". В этом случае вы можете исключить все этажи ниже "серединного" из рассмотрения. 4. Если диск разбился, это означает, что диск не может выдерживать бросок с "серединного" этажа. В этом случае вы можете исключить все этажи выше "серединного" из рассмотрения. 5. Повторяйте шаги 2-4, пока не останется только один этаж в рассмотрении. Этот этаж и будет ответом на ваш вопрос. В худшем случае, количество бросков, которые вам придется сделать, будет равно логарифму от количества этажей в двоичном представлении (что равно приближенно 4). Это происходит потому, что с каждым броском вы сокращаете количество возможных этажей примерно в два раза, что эквивалентно операции деления на 2. Обратите внимание, что этот метод предполагает, что все диски идентичны и могут выдерживать равное количество бросков. Если это не так, вам потребуется более сложный алгоритм, который учитывает уникальные характеристики каждого диска.