(no subject)
Сегодня на CareerCup встретил интересную задачку: "Имея два яйца (куриных), определить наиболее высокий этаж в 100-этажном здании, с которого можно бросать яйца так, чтобы они не бились."
Поначалу впал в ступор - никак не мог понять, как можно вообще это определить. Потом дошло, что если яйцо не разбилось при броске с какого-то этажа, то им можно пользоваться дальше:-)). Последовало первое очевидное решение.
1. Подниматься последовательно на каждый этаж (снизу) и бросать яйцо с этого этажа. Как только яйцо разобьётся - значит искомый этаж был ниже. Если яйцо не разбилось ни разу - этот этаж 100-й. В худшем случае (если это сотый этаж) решение задачи занимает 100 подъёмов.
Встаёт вопрос - зачем тогда второе яйцо? После этого я придумал другое решение.
2. Подняться на 50-й этаж и бросить одно яйцо. Если оно бьётся - решение где-то снизу. Тогда идём на первый этаж и с оставшимся яйцом повторяем процедуру, описанную в пункте 1. Если яйцо, брошенное с 50-го этажа не разбилось, переходим на 75-й этаж и снова бросаем яйцо. И т.д. В худшем случае (если это 49-й этаж) решение задачи занимает 50 подъёмов.
Ничего лучше этого я не придумал и за обедом поделился задачей с коллегой. Он сразу придумал алгоритм чуть хуже моего: проходить чётные этажи. Если яйцо, сброшенное с одного из этих этажей, разбилось, то следует попробовать бросить оставшееся яйцо с нечётного этажа, находящегося под чётным, при броске с которого первое яйцо разбилось. Если яйцо разбилось и при этом броске, то искомый этаж - предпоследний чётный (надеюсь, я всё это понятно излагаю). Если не разбилось, то искомый этаж - последний нечётный. В худшем случае (если это 98-й этаж) решение задачи занимает 51 подъём. Дальше фантазия уже подсказала ему проходить этажи, номера которых делятся на три, в этом случае худшее решение (кажется, всё тот же 98-й этаж) займёт уже 35 подъёмов (вроде так, в принципе, легко можно проверить).
А дальше обед закончился и мы пошли работать.
Вернувшись, я открыл ту же страницу и тут же увидел ответ, оказавшийся правильным. Но сначала немного о странице, на которой все попытки (и наши тоже) перечислены с довольно подробным разбором:
http://www.datagenetics.com/blog/july22012/index.html
3. Если имеется бесконечное количество яиц (противоречит условию задачи, но это просто допущение), то решение находится простейшим двоичным поиском: бросаем с 50-го этажа, в зависимости от того, бьётся яйцо или нет, бросаем либо с 75-го, либо с 25-го и т.д. - каждый раз область поиска сокращается в два раза. Худшее решение (1-й этаж или 100-й) будет найдено не меньше чем за log2(100) ходов, что меньше 7 (то есть 7 - максимальное число подъёмов).
4. Если подниматься с периодом в 10 этажей (10-й, 20-й и т.д.), то в худшем случае (99-й этаж) решение найдётся за 19 подъёмов. Идея этого подхода состоит в том, что когда находится этаж, при броске с которого яйцо разбивается (например, 60-й), то надо перебрать все этажи с 51-го по 59-й, чтобы найти искомый этаж. В условиях реальной задачи (когда есть всего два яйца) это выглядит прорывом по сравнению с 35, 50 или 100 подъёмами.
Но этот результат тоже можно улучшить.
5. Можно заметить, что если яйцо было брошено и разбилось с этажа номер 'n', то мы можем проверить (n-1) этажей ниже него по очереди в поисках интересующего нас этажа.
Пусть N - максимальное число попыток, которое мы можем предпринять в поиске нужного этажа. Поступим следующим образом: взберёмся на N-й этаж и бросим яйцо (это первая попытка, осталось ещё (N-1)). Если яйцо разбилось, перебираем по очереди (N-1) нижних этажей и находим решение. Если яйцо не разбилось, то надо взобраться на этаж (N-1), чтобы оставить в запасе (N-2) между пройденными этажами и бросить яйцо с него. В случае, если решение не находится, повторять эту процедуру, постепенно уменьшая интервал подъёма на очередной этаж. Таким образом, получится сумма:
N + (N-1) + (N-2) + ... + 1 = N(N+1)/2
Эта сумма должна покрывать 100 этажей, чтобы решение было найдено. Наименьшим целым N, удовлетворяющим этому условию, является N=14. Так-то!
Кстати, в той статье всё написано гораздо подробнее и даже описан метод для произвольного количества яиц! Я в нём ещё не успел разобраться (лучше писать программу для полного понимания), но он определённо заслуживает прочтения.
P.S. В начале поста сообщается, что задача задавалась на собеседовании то ли в Microsoft, то ли в Google.
Поначалу впал в ступор - никак не мог понять, как можно вообще это определить. Потом дошло, что если яйцо не разбилось при броске с какого-то этажа, то им можно пользоваться дальше:-)). Последовало первое очевидное решение.
1. Подниматься последовательно на каждый этаж (снизу) и бросать яйцо с этого этажа. Как только яйцо разобьётся - значит искомый этаж был ниже. Если яйцо не разбилось ни разу - этот этаж 100-й. В худшем случае (если это сотый этаж) решение задачи занимает 100 подъёмов.
Встаёт вопрос - зачем тогда второе яйцо? После этого я придумал другое решение.
2. Подняться на 50-й этаж и бросить одно яйцо. Если оно бьётся - решение где-то снизу. Тогда идём на первый этаж и с оставшимся яйцом повторяем процедуру, описанную в пункте 1. Если яйцо, брошенное с 50-го этажа не разбилось, переходим на 75-й этаж и снова бросаем яйцо. И т.д. В худшем случае (если это 49-й этаж) решение задачи занимает 50 подъёмов.
Ничего лучше этого я не придумал и за обедом поделился задачей с коллегой. Он сразу придумал алгоритм чуть хуже моего: проходить чётные этажи. Если яйцо, сброшенное с одного из этих этажей, разбилось, то следует попробовать бросить оставшееся яйцо с нечётного этажа, находящегося под чётным, при броске с которого первое яйцо разбилось. Если яйцо разбилось и при этом броске, то искомый этаж - предпоследний чётный (надеюсь, я всё это понятно излагаю). Если не разбилось, то искомый этаж - последний нечётный. В худшем случае (если это 98-й этаж) решение задачи занимает 51 подъём. Дальше фантазия уже подсказала ему проходить этажи, номера которых делятся на три, в этом случае худшее решение (кажется, всё тот же 98-й этаж) займёт уже 35 подъёмов (вроде так, в принципе, легко можно проверить).
А дальше обед закончился и мы пошли работать.
Вернувшись, я открыл ту же страницу и тут же увидел ответ, оказавшийся правильным. Но сначала немного о странице, на которой все попытки (и наши тоже) перечислены с довольно подробным разбором:
http://www.datagenetics.com/blog/july22012/index.html
3. Если имеется бесконечное количество яиц (противоречит условию задачи, но это просто допущение), то решение находится простейшим двоичным поиском: бросаем с 50-го этажа, в зависимости от того, бьётся яйцо или нет, бросаем либо с 75-го, либо с 25-го и т.д. - каждый раз область поиска сокращается в два раза. Худшее решение (1-й этаж или 100-й) будет найдено не меньше чем за log2(100) ходов, что меньше 7 (то есть 7 - максимальное число подъёмов).
4. Если подниматься с периодом в 10 этажей (10-й, 20-й и т.д.), то в худшем случае (99-й этаж) решение найдётся за 19 подъёмов. Идея этого подхода состоит в том, что когда находится этаж, при броске с которого яйцо разбивается (например, 60-й), то надо перебрать все этажи с 51-го по 59-й, чтобы найти искомый этаж. В условиях реальной задачи (когда есть всего два яйца) это выглядит прорывом по сравнению с 35, 50 или 100 подъёмами.
Но этот результат тоже можно улучшить.
5. Можно заметить, что если яйцо было брошено и разбилось с этажа номер 'n', то мы можем проверить (n-1) этажей ниже него по очереди в поисках интересующего нас этажа.
Пусть N - максимальное число попыток, которое мы можем предпринять в поиске нужного этажа. Поступим следующим образом: взберёмся на N-й этаж и бросим яйцо (это первая попытка, осталось ещё (N-1)). Если яйцо разбилось, перебираем по очереди (N-1) нижних этажей и находим решение. Если яйцо не разбилось, то надо взобраться на этаж (N-1), чтобы оставить в запасе (N-2) между пройденными этажами и бросить яйцо с него. В случае, если решение не находится, повторять эту процедуру, постепенно уменьшая интервал подъёма на очередной этаж. Таким образом, получится сумма:
N + (N-1) + (N-2) + ... + 1 = N(N+1)/2
Эта сумма должна покрывать 100 этажей, чтобы решение было найдено. Наименьшим целым N, удовлетворяющим этому условию, является N=14. Так-то!
Кстати, в той статье всё написано гораздо подробнее и даже описан метод для произвольного количества яиц! Я в нём ещё не успел разобраться (лучше писать программу для полного понимания), но он определённо заслуживает прочтения.
P.S. В начале поста сообщается, что задача задавалась на собеседовании то ли в Microsoft, то ли в Google.