для тех, кто уже решил и не знает чем заняться, предлагаю задачу.
--------------------------------------------------------------------
однажды купец решил закатить пир горой. созвал кучу гостей, закупил кучу еды и 1000 бочонков вина.
до празднования оставалась всего пара часов, когда купцу донесли, что злые недруги отравили вино в одной из бочек.
купец не хотел отменять празднование и оставлять гостей без выпивки.
он знал, что признаки отравления проявляются уже через час после приема яда.
благодаря крепкой дружбе с тюремщиком, он смог договориться о "тестировании" вина на 10 смертниках.
> Есть 100-этажка. При броске с кирпича с определённого этажа кирпич ломается (и со всех более высоких этажей - тоже сломается, а с более низких - нет). У нас есть 2 одинаковых кирпича. Требуется как можно быстрее (за наименьшее число бросков) выяснить этот самый номер этажа, с которого кирпичи начинают ломаться. > За сколько бросков вы справились бы?
т.е. надо составить наиболее оптимальный алгоритм для произвольного этажа?
прошли уже сутки, поэтому даю ответ на задачу про 1000 бочек
эту задачу хорошо решать, будучи программистом, потому как решается она при помощи двоичной системы счисления.
любое число до 1024 можно представить в двоичном виде при помощи всего 10 разрядов.
например 1000 = "1111101000", 666 = "1010011010", 77 = "0001001101"
(для тех, кто не понял как я это сделал - при помощи стандартного калькулятора винды, "вид - инженерный")
нумеруем все бочки таким образом.
а каждый смертник будет отвечать за свой разряд.
потом поим из бочек по принципу - стоит 1 в твоем разряде - пьешь, стоит 0 - пропускаешь.
после часа некоторая часть - умрет. зная их разряды, ставим в соответствующие места 1, а в остальные - 0.
после чего переводим в 10 систему и имееем отравленную бочку.
-------------------------------
в среднем каждый перепробует 500 бочек,
а из каждой бочки - не более 9
эх... а я уже "доказал" что это невозможно и разработал формулу для общего случая...
----------------------------------
кстати, камрады, кто-нибудь в курсе, каким образом анализируются задачи на взвешивание?
задачи типа "среди 10 монет одна фальшивая. фальшивая более легкая. на весах без гирь за 3 взвешивания найти фальшивую".
так вот вопрос - а как определяется минимальное число взвешиваний при котором задача еще решается? особенно если монет скажем 40, фальшивых несколько, да и с весом непонятки.
Сейчас, сейчас