Вдогонку к задачке о Кощее, еще одна простенькая задачка.
Есть 100 очень дорогих одинаковых хрупких шариков. И есть лестница с сотней ступенек. Какой минимум шариков придётся разбить, чтобы выяснить предельную высоту (номер ступеньки от 1 до 100 — бросаем со ступенек на пол, а не по лестнице вниз), с которой можно ронять шарики целыми (т.е. чтобы они не разбились)? Конечно, если шарики не бьются даже с 100й ступеньки, то 0, но, несмотря на то, что мы этого заранее не знаем, интересен ответ во всех остальных случаях.
ОТВЕТ ПОД КАТОМ, НО НЕ СПЕШИТЕ ЗАГЛЯДЫВАТЬ ПОД КАТ
****************************************************************
Правильный ответ: 1
Если у вас получился другой ответ, то попробуйте решить задачку еще раз, зная ответ.
Кстати, неслабая подсказка содержится в заголовке.
ОБЪЯСНЕНИЕ НИЖЕ
****************************************************************
В современной науке очень трудно быть хорошим специалистом одновременно в разных областях. Поэтому физики вынуждены обращаться за помощью к математикам, а те в свою очередь к программистам. При этом приходится "переводить" задачу с "языка" одной предметной области на "язык" другой. Но в таких серьезных задачах, обычно, проводятся многочисленные согласования и проверки того, что все друг друга поняли правильно. А вот в простых задачках мозг сам переводит задачу на тот "язык", на котором привык думать. Обычно, это только облегчает нам жизнь, но не всегда.
Обычно, в этой задаче ошибаются программисты. Им часто приходиться иметь дело с задачами "быстрого поиска". Они применяют метод "деления отрезка пополам" (бросаем шарик с 50й ступеньки, если разобьется, то с 25й, если нет — то с 75й, и т.д.). Хотелось бы применить "сбалансированные деревья", да вот лестница "отсортирована" только по высоте. Метод "деления отрезка пополам" позволяет укорить "поиск", т.е очень эффективно уменьшить количество бросков. А теперь прочитайте условие задачи, где там сказано про "количество бросков"? Там говориться о минимизации потерь очень дорогих шариков.
Решение очевидно: бросаем шарик с 1й ступеньки, если не разбился, то со 2й, потом с 3й и т.д.
Самое интересное, что если эту задачку задать пятикласснику, то, скорее всего, он решит ее правильно.
© 2000–2012 NoNaMe