View Full Version : Задачка о прочности шариков
Давненько задачек небыло.
Вот одна забавненькая. Легенда гласит, что несколько лет назад ее давали во время собеседования с потенциальными сотрудниками Microsoft.
Есть 100этажное здание с окнами на каждом этаже. У вас есть шарик, про который известно, что если его выбросить из окна на kом этаже или ниже - он упадет на землю и не разобъется. Если выбростить с k+1го или выше - упадет и разобъется.
Задача - выяснить число k.
Для одного шарика эта эта задача решается элементарно: бросить шарик с первого этажа. Если не разбился - перейти на 2ой, бросить оттуда, и так далее подниматься, пока не разобъется. Таким образом не более чем за 100 бросков найдем число k, если оно есть.
Собственно задача: теперь у вас два шарика. Предложите способ точно определить число k за минимальное число бросков.
Математику:
Возможны обобщения: больше шариков, другая высота здания.
Mike BFD
10-07-2007, 11:31
"Артиллерийская вилка": делим этажи на сектора по количеству шариков, начинаем бросать с нижнего этажа каждого сектора...
Это тест при приеме в Мелкософт? Да-а-а...
"Артиллерийская вилка": делим этажи на сектора по количеству шариков, начинаем бросать с нижнего этажа каждого сектора...
Это тест при приеме в Мелкософт? Да-а-а...
Не возьмут тебя в Microsoft :D
Ну если это два одинаковых шарика, и смысл с помощью их найти число "к" за минимальное кол-во бросков, то можно, как мне кажется, выкидывать каждый раз шарик с каждого второго этажа. Если на 20-ом не разбился, а разбился на 22-ом, то выкидываем второй шарик на 21-ом. Если разбился и там, число "к" = 20; если нет, то "к" = 21... :)
Appolon, Шарики одинаковые.
Но ответ ничем не лучше предыдущего. Понадобится (в худшем случае) 51 бросок.
"Есть способ лучше".
Appolon, Шарики одинаковые.
Но ответ ничем не лучше предыдущего. Понадобится (в худшем случае) 51 бросок.
"Есть способ лучше".Мда..., это я поторопилси. :)
Блин, ну тогда с каждого десятого, а как разобъется, вторым шaриком искать этаж.
PS: И чем это я на работе занимаюсь?! Этажи считаю! Дожили. :lol:
PearLinShell
10-07-2007, 15:23
Я бы каждый раз делила этажи на 2.
Сначала с 50-го кидаем, если разобьётся, то.. да... в худшем случае будет 50 попыток..
А если нет, то кидаем с 75-го (уже вполовину меньше попыток будет)....
И т.д.......
Mike BFD
10-07-2007, 15:32
Я бы каждый раз делила этажи на 2.
Сначала с 50-го кидаем, если разобьётся, то.. да... в худшем случае будет 50 попыток..
А если нет, то кидаем с 75-го (уже вполовину меньше попыток будет)....
И т.д.......
Я уже предлагал то же самое ("вилку"), только в варианте для произвольного количества шариков, так Анк только усмехается...
А давай кидать с nго этажа, потом с 2nго, потом с 3nго, пока не разобьется, опосля чего хватит еще n бросков 2-го шарика, чтобы уточнить этаж.
Наглый вопрос: а "усталость" и прочие микроповреждения шарика с каждым броском не накапливаются?
по-моему, 19 бросков хватит, может и меньше можно...
по-моему, 19 бросков хватит, может и меньше можно...
Ну так в принципе в мной предложенным способе и получится как раз 19 бросков, если предположить, что шарик кокнется с 100-го этажа. Значит мыслим одинакого. :)
SannamannA
10-07-2007, 16:57
Для одного шарика эта эта задача решается элементарно: бросить шарик с первого этажа. Если не разбился - перейти на 2ой, бросить оттуда, и так далее подниматься, пока не разобъется. Таким образом не более чем за 100 бросков найдем число k, если оно есть.
Если k>100, то и за 100 бросков нипочем не найдешь.
А если так: проверяем этажи
14, 27(+13), 39(+12), 50(+11), 60(+10), 69, .... 99.
Итого хватит 14 попыток. Что характерно, если 100го этажа шарику мало, это определяется.
Возьмете меня в "мокрохвост"? Что дадут, то и раздолб... оптимизирую :) нафик
Ну так в принципе в мной предложенным способе и получится как раз 19 бросков, если предположить, что шарик кокнется с 100-го этажа. Значит мыслим одинакого. :)
Сорри, прозевал твой пост, но я еще лучше придумал :)
Я знал, что решит только Kaktus.
Жаль, что не я беру в Microsoft.
[russian.fi, 2002-2014]