Речь снова пойдет о задаче с собеседования в Google (и в Intel её тоже давали). Это реальная задача, которую предлагали соискателям на вакансию менеджера по продукту, опубликованная в сборнике бизнес-тренера Льюиса Линна, который помогает людям успешно проходить собеседования и устраиваться на хорошие должности.
Менеджер в данном случае — это не продавец, это управляющий. Человек, который руководит каким-то проектом, программистами, другими менеджерами поменьше, отвечает за разработку и успешность проекта в целом. Короче говоря, после ПТУ и ускоренных курсов по программированию на такую вакансию точно не возьмут.
Вот лишь один из вопросов, который задавали на собеседовании. Если сможете решить, вам откроется тайна поиска информации в Гугле. А в качестве эпиграфа к задаче расскажу вам одну притчу.
— А мне пригодится математика? — спрашивает ученик учителя.
— Нет, она нужна только умным детям, — отвечает учитель.
Вам дается два яйца неизвестного происхождения и имеется доступ в 100-этажный небоскреб. Яйца могут быть очень хрупкими и разбиться при падении с высоты первого этажа, а могут быть настолько крепками, что не разобьются даже, если упадут с сотого этажа.
Оба яйца идентичны по виду и прочности. Вам нужно узнать, с какого максимального этажа можно уронить яйцо, чтобы оно не разбилось. Разбить можно оба яйца (но запасных яиц у вас нет). Проблема в том, чтобы выяснить это за наименьшее число попыток. Проще говоря, надо найти не только этаж, но и сделать минимальное число (в худшем случае) попыток для выяснения этого.
Теперь о том, почему же я вдруг в заголовке написал "вот почему российских программистов ждут в США". Потому что эту задачу (очень-очень похожую) предлагали решить в некоторых советских сборниках задач. Если я не ошибаюсь, даже печатали в "Мурзилке" или каком-то другом аналогичном журнале. Я даже помню, как сам думал в детстве над этой задачей и как мы потом разбирали её с учительницей.
Решение
Вот такие поисковые задачи очень любят давать в технологичных IT-компаниях по всему миру. Благо большинство из них решается по одному и тому же алгоритму. Я бы даже сказал, что это классические поисковые задачи, которые были известны ещё задолго до того, как появились компьютеры и программисты.
Я покажу решение конкретно этой задачи для двух яиц и 100-этажного здания, а вы, если интересно, для закрепления попробуйте сделать то же самое для N-этажного здания и для d яиц.
Первый — самый очевидный — вариант
Очевидно, самый простой способ — взять одно яйцо и бросить его с первого этажа. Если не разобьется, то подняться и сбросить его со второго этажа. Если снова не разобьется, подняться ещё на этаж и сбросить с третьего. И так далее до тех пор, пока яйцо не разобьется. В лучшем случае мы узнаем результат за 1 попытку, в худшем — за 100 (когда доберемся до сотого этажа).
Плюс в том, что так мы разобьем только одно яйцо и сохраним второе. Минус в том, что мы можем потратить очень много времени. Да и в задаче говорится про минимальное количество попыток, так что такой вариант нам не пойдет и собеседование с таким подходом не пройдешь.
Второй вариант. Чуть лучше, но все равно не то
Можно начать с середины. Сбросить первое яйцо с пятидесятого этажа, а дальше действовать по приницпу первого варианта. То есть, если яйцо разбилось, то мы берем второе и проверяем все этажи, начиная с первого по очереди.
Если не разбилось, то продолжаем бросать с 51-го этажа, 52-го этажа, 53-го и так далее. В худшем случае нам придется сделать 50 бросков — уже лучше, но до оптимального решения всё ещё далеко.
Третий вариант. Уже горячо
А что, если разделить 100 этажей на 10 секторов по 10 этажей. Первый раз бросаем с 10-го этажа. Если яйцо разбилось, берем второе и идем бросать его с первого этажа, потом второго, третьего и так далее.
Если с 10-го этажа яйцо не разбилось, идём на 20-ый. Если разбилось, то берем второе яйцо и идем на 11 этаж, потом 12-ый, 13-ый и так далее.
Если и с 20-го этажа яйцо не разбилось, поднимаемся на 30-ый и так далее по одному и тому же алгоритму. Понятно, что в худшем случае у нас получится 19 попыток. Это уже очень хорошо. Намного меньше, чем делать 100 попыток или даже 50, не так ли? Но говорят, что это всё ещё не самый оптимальный вариант решения.
Четвертый вариант. Оптимальный
Можно попытаться ещё больше дробить данные 100 этажей на части. Например, 20 частей по 5 этажей в каждом. Но давайте прикинем, какие решения будут для разных случаев.
Если 2 этажа, то нужно бросить через один этаж, чтобы было наименьшее количество бросков.
Если 4 этажа, то бросать первый раз нужно на втором.
Если 8 этажей, то бросать нужно на третьем! Да, именно на третьем, а не на четвертом, потому что если бросить сначала на четвертом, то в худшем случае придется сделать 5 бросков, а не 4.
И тут бы пригодилось знание логарифма, потому что тут есть приращение числа. Выходит, что бросить яйцо надо с такого этажа, чтобы количество бросков внутри этого шага было не больше наихудшего варианта.
Таким образом, если N — это количество этажей, а k — это количество бросков, получается k•(k+1)/2≥N. Решаем это неравенство для N=100 этажей и получаем k=14.
Проверка
Давайте рассмотрим подробнее. Первым бросок совершаем с 14-го этажа. Второй, если яйцо не разбилось, с 14+13=27-го этажа. Третий, если яйцо всё ещё не разбилось, с 27+12=39 этажа. И так далее. Суть проста: каждый раз мы добавляем этажей на единицу меньше, чтобы суммарное число бросков не превысило 14 при самом плохом исходе. Поэтому бросаем с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99.
Допустим первое яйцо разбилось при броске с 50-го этажа. Выходит, что мы сделали уже 4 броска. За оставшиеся 10 (или раньше) мы точно поймём, начиная с какого этажа яйца будут биться. Второе яйцо мы попробуем разбить сначала с 40 (потому что с 39-го уже пробовали), потом с 41, 42, ..., 49 этажей. Либо второе яйцо разобьется на каком-то из этих этажей, либо нет. В последнем случае будет ровно 14 бросков (наихудший сценарий).
Полагаю, для программистов задача не составила большого труда, ведь именно такой способ решения приводится в самом начале настольной книги начинающего программиста "Искусство программирования" Кнута. Надеюсь, эпиграф к задаче был в тему и все, кто дочитал статью до конца, поняли, кому и зачем нужна математика.
Пишите в комментариях, получилось решить задачу без подсказок или нет? И как много времени ушло на раздумья? А вот, что ещё рекомендую почитать, если вам понравилась эта задача:
