Интересная головоломка

hostagedown, 447 просмотров

-2

Слышал про одну задачку, которую давали на собеседование в Microsoft, хочу поделиться:

Есть небоскреб - 100 этажей. И есть только (!) два (абсолютно одинаковых) шарика.
Известно, что при выбрасывания шарика с некоторого этажа, шарик разбивается.
Требуется найти минимальное число операций, за которое можно определить номер этого этажа.

У меня получилось 13. Вообще, на работу брали людей, составивших алгоритм хотя бы из 20 операций.

Хотелось бы послушать еще мнения, может у кого-то меньше 13 получится?

Примечание:
Psych: что за задачка? интересно было бы подумать.))

Примечание:
sergio_vo: если сделать так, как предлагаете вы, то при условии, что если этот этаж = 100, то на это у вас уйдет 50 попыток..

Примечание:
katzyn: Да, у меня такой же способ.. Я не правильно просто просуммировал, 14 получается. Я просто начинал с низу подниматься с убывающим шагом (ошибочно я просто начинал с 13 этажа (в итоге до 91-го дошел бы)).. Первый бросок с 14 этажа - если разбивается, то понятно, 14 операций. Далее, бросаем с 27 (14+13) этажа - соответственно, тоже 14 операций максимум, далее, если не разбилось, то с 39 (14+13+12) этажа - тоже максимум 14 операций, и так далее.. бросаем с 50 (+11).. с 60 (+10).. с 69(+9) .. 77 (+8).. с 84 (+7).. с 90 (+6).. с 95 (+5).. с 99 (+4).. - итого каждый шаг уменьшается на единицу, а число операций остается постоянным - 14. Здесь в принципе здание могло бы быть высотой 105 этажей.

Ответы:

Psych

надо подумать, майкрос похоже любит такие задачи
мне про задачу с тюрьмой и рубильниками рассказывали

sergio_vo

я бы кидал начиная с низу с шагом в два этажа, пока шар бы не разбился. затем спустился назад на один этаж и скинул оттуда - если разбился значит это искомый этаж. нет-этаж выше. но тут вроде не минимально. думать надо

Psych

ее надо в несколько этапов рассказывать для пущего эффекта, общие условия есть тюрьма, в ней 100 заключенных, им предлагают иру:
у них есть ночь чтобы выработать стратегию, а наутро начинается игра, после начала игры каждый день случайным образом будут выбирать заключенного и приводить в комнату с неким количеством рубильников, с которыми он может делать все что угодно, на протяжении всей игры у заключенных нет возможности общаться, так же нет возможности узнать кого именно сегодня водили в комнату, игра заканчивается тогда когда очередной зашедший в комнату говорит что в ней побывали все, если он прав то всех отпускают, если нет всех в смертники

Psych

а вашу задачу на вскидку элементарно за 19 шагов решить, над дальнейшими оптимизациями надо подумать.. утром займусь )
но мне кажется что и 13 не предел

Psych

по заключенным мысли есть? а то я сечас спать и не успею вторую часть задачи сказать )

atributz

Разобьем 100 на некоторое количество одинаковых промежутков Y по X этажей(x*y=100), будем кидать первый шарик каждые x этажей, и если он разбивается кидаем второй шарик.
В худшем случае если шарик разбивается на (100 этаже а на 99 не разбивается) нам потребуется y+x-1 бросков.
Близкое к оптимальному значение видимо x=y, те x=10 y=10, бросаем первый шарик на каждом 10м этаже, это 19 бросков.(Если на каждом 9 или 11 этаже, то тоже 19 бросков.)

katzyn

Первый шар мы можем бросать с любого этажа, но если он разобъётся, то придётся вторым последовательно проверить все непроверенные этажи ниже этого, начиная с нижнего из них.

Иван Козначеев

13 попыток недостаточно, нужно хотя бы 14.
задача сводится к Игре 1 с N=99 (см. ссылку)

Psych

это решение с 14 шагами минимально возможное

Vovochkal

Я в своё время получил эту задачу в Микрософте, и быстро дошел до решения sqrt(n) - это элементарно.
Но это не лучшее решение - можно еще уменьшить сложность (complexity) если догадаться что промежутки не обязанны быть равными :) То есть шаг в 15, 14, 13 и т.п. А вот это уже похоже лучшее решение. Но даже при решении в sqrt(n) интервью я прошел.

15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.