![]() |
|||||
Самое читаемое:Облако тегов:Ссылки:
|
Задача о шариках и небоскребе
Опубликовано Gena в 28. январь 2008 - 12:09.
Эта задача предлагается для решения при собеседовании на позицию "программиста" в крупных компаниях. Для ее решения не нужно специальных знаний, хотя чтобы точно решить задачу в общем случае необходимы сведения из теории рядов. Есть два стеклянных шарика: красный и синий. Вы находитесь в 100-этажном доме. Вам нужно определить номер этажа, начиная с которого шарик при падении разбиваются. То есть, нужно точно указать, что при падении с N-го этажа шарик не разбивается, а при падении с (N+1)-го уже разбивается. За какое минимальное число шагов мы можем гарантированно определить этаж в самом худшем для нас случае? Какова стратегия быстрейшего поиска решения предложенной задачи? Решить задачу для случая L-этажного здания и m шариков. П.с.: Шаг - это один бросок одного шарика. Шарик начинает разбиваться с определённого этажа. Те кто знают, или думают что знают ответ, указывайте его в формате: {spoiler}ваш ответ{/spoiler], заменив { } на [ ]. »
|
Новые материалы:Новое в блогах:Прямой эфир: |
![]() |
MOZG.by (C), 2007-2008 admin@mozg.by |
Скрытый текст:
Для m шариков получаем формулу по этажам 2m. А потом делением полапам находим нужный этаж.
Не понял
А смысл синего и красного шарика? Какое значение имеет цвет или то что их 2?
Запутать
А это чтобы запутать посильнее.
И с "Матрицей" параллель провести...
кидалово)
Knight не согласен с приведенным тобой решением, объясняю почему:
например исходно шарик разбивается с 5го но целый с 4го, бросили с 4го - целый, бросили с 8го - разбился, бросаем с 6го - разбился, по приведенному решению получим N=5, а не 4.
да, ошибся
да, ошибся немного. Предложи свое решение, Lit!
борьба добра и зла
>Какова стратегия быстрейшего поиска решения предложенной задачи?
Как человек особо одаренный, вопроса не понял, уточните плз.
О шариках: очевидно*, реакция шариков не мгновенна, так что, падая с низких этажей, парашют раскрыть могут и не успеть. Шарик, не успевший раскрыть парашют – считается трупом. Этажи нумеруются сверху.
О цвете: мы все отлично понимаем, что важные дела не стоит пускать на самотек. Так что синяя таблетка - крашенная красная, и совершенно неважно, какие колеса глотал шарик.
простукивать надо все подряд, никаких фокусов
Пусть к - мин количество шагов, гарантирующих определение нужного этажа.
---m>=k
дихотомия** нам поможет - мы вполне проверим ею (2^k)-1 этаж
---m=j, шаг i
(Л2 =0) пусть на шаге i-1 успешно спустили шарик с этажа Лi, j-1 шариком за k-i шагов можно простучать pLk-ij этажей. Тогда не выбрасывайте шарк с > pLk-ij+Li+1 этажа - примета плохая. Спустить его с этажа < pLk-ij+Li +1 точно не лучше чем с pLk-ij+Li +1 (если чего-то можно проверить j1 шариком за k1 шагов на L1 этаже, то на L2 меньше L1 тоже можно, а вот обратное не факт)
---Суммируем, суммируем и понимаем, что m шариками за k>m шагов можно проверить не более pLmk=(2^k)-sum (C***ik,i от 1 до k-m)-1 этаж. То есть, надо угадать такое минимальное k, при котором это будет больше L. Угадав, бросаем шарик на pLk-1j+1 , L1+pLk-1j+1, ... , этаже, пока он не разобьется, или пока нам не дадут воспользоваться честной дихотомией. Дальше пользуемся все той же старой доброй прокуренной логикой (если разбился, получаем задачу с pLk-ij этажами, k-i шагами и j-1 шариком).
---* все остальное тоже очевидно
---** вообще-то, бинарный поиск, если кому-то от этого легче
---*** кто же не знает силовика Ньютона, с его биномом.
А ответ на главный вопрос жизни, вселенной и всего такого - все же 42, а не 14.
Да, если обобщенную задачу предлагают решать устно, то это садисты. Не идите к ним работать.
Советую найти
Советую найти ответ для случая 100 этажей и 2 шариков прежде, чем писать всякие замутные решения. На самом деле у этой задачи достаточно простое решение.
Кстати, первый раз я увидел задачу 2 года назад на открытом личном первенстве России по программированию. Гена, откуда информация, что ее используют на собеседованиях?
Собеседование
Про то, что такая задача встречалась на собеседовании моему приятелю рассказал его друг, которому эту задачу задали. Разумеется, ее не надо было решать в общем случае прямо на собеседовании. Нанимателя интересовала, в первую очередь, логика человека, его уменее анализировать ситуацию. Задачу, кстати, он решил, но на работу все равно не попал - срезали на других формальных критериях...
Для 2х шариков -
Для 2х шариков - простое.
А для m - извращенное и приведено не полностью и не строго.)
Да, и прошу прощения за ошибки в индексах, в первом ответе.
pLmk -> pLkm+1
(Л2=0) -> (L1=0)
Лi -> Li
а почему именно
а почему именно с 14, 27, 39,...,95,99 этажа?
просто не поняла