Стоит четырехэтажный дом, в каждом этаже по восьми окон, на крыше - два слуховых окна и две трубы, в каждом этаже по два квартиранта. А теперь скажите, господа, в каком году умерла у швейцара его бабушка?
Вот всегда мне нравились задачи, вроде упомянутой некогда отбывавшим в наших краях, писателем про бравого солдата Швейка.
И ведь, что самое смешное, начинают решать задаваясь средним возрастом жителей дома в 1914 г! Там может вообще богадельня была, с контингентом, блудившим некогда с Евгением Савойским...
Сегодня, читая журнал некоего тофалара, я столкнулся с очередной порцией задач, самой
Задача 4.
У Вас есть два яйца неизвестной птицы, и есть доступ в стоэтажное здание. Каждое из яиц имеет скорлупу из неизвестного материала, оно может разбиться при падении с первого этажа, а может и не разбиться при падении с сотого этажа здания. Оба яйца одинаковы. Как определить, при падении с какого этажа яйцо разобьется? Нужно постараться определить этаж за минимальное количество тестов.
Минимальное количество тестов+этаж.
Поднимаемся на сотый, и кидаем оба. Таким образом, за одну попытку задача решена- нигде в условиях не сказано, что нужен "наименьший пробег испытателя" или "наименьший этаж".
Можно, разумеется,
Можно, конечно, начать вертеться ужом, напирая на:
оно может разбиться при падении с первого этажа, а может и не разбиться при падении с сотого этажа
Ну тогда процесс у нас выходит случайный, с двумя исходами равномерно вероятными: либо разобьётся- либо нет. Потому, кидать будем с 1 этажа- всё равно от высоты ничего не зависит.
Ну и не заглядывая во всякие методы Монте-Карло, полагаю, даже с моей невезучестью, попыток за 6 управиться.
Tags:
Задачи бородатые, но хорошие
Задача про яйца проверяет умение отличать то, чтозаказчик сказал оттого, что он имел в виду. Это умение для программиста важнее, чем знание какого-нибудь сто первого трёхбуквенного сокращения.
В оригинале там надо найти алгоритм с минимальным количеством бросков в худшем случае. Решается рекурсией, см. рекурсия. Начинать надо с 14-го этажа.
Re: Задачи бородатые, но хорошие
Но любую подобную "задачу" можно свести к "пикам точеным и удам дроченым".