задачка

← →
Слоник (2006-03-24 11:34) [0]

есть 100 бутылок вина, 10 кроликов и 24 часа, чтобы определить единственную отравленную бутылку. яд начинает действовать через 24 часа.

← →
Курдль © (2006-03-24 11:38) [1]

Метод последовательного приближения. Однозначно!

← →
Sandman25 © (2006-03-24 11:40) [2]

Мне кажется, достаточно 7 кроликов.
1234567
0000000
0000001
0000010
и т.д.
Каждый кролик выпивает из той бутылки, где стоит 1 (или 0). Смотрим, какие кролики умерли и находим соответствующую бутылку.

← →
Sandman25 © (2006-03-24 11:45) [3]

Курдль © (24.03.06 11:38) [1]

Условия перечитайе, хоть они и корявые. Упрощенно говоря, время всего процесса распития спиртных напитков, равно нулю.

← →
Слоник (2006-03-24 11:52) [4]

> Sandman25 © (24.03.06 11:40) [2]
>
> Мне кажется, достаточно 7 кроликов.

шустро =)

> Условия перечитайе, хоть они и корявые. Упрощенно говоря,
> время всего процесса распития спиртных напитков, равно
> нулю.

ну да, требуемые допущения:
- распитие, смерть зверька и принятие решения не занимают времени
- бутылки и кролики бездонны =)

← →
Vlad Oshin © (2006-03-24 11:55) [5]

ага, 10 кроликов хватит для 1024 бутылок

← →
Sandman25 © (2006-03-24 11:57) [6]

Слоник (24.03.06 11:52) [4]

шустро =)

Это не моя заслуга, сработал стандартный подход.

Можно еще попытаться спасти побольше кроликов, если специально не использовать комбинации с 6 и 7 единицами (их будет 8). Умрет от 0 до 5 кроликов.

← →
Marser © (2006-03-24 11:58) [7]

> - распитие, смерть зверька и принятие решения не занимают
> времени

А как же условие действия яда через сутки?

← →
Слоник (2006-03-24 11:59) [8]

можно сократить смертность до трёх
разбиваем кролей на, скажем, тройки, каждой из них приписываем одну бутылку (комбинаций с запасом хватит - 10!/(3!*(10-3)!)=120) и соотв. поим тройку из неё. через сутки смотрим какая тройка сдохла. вуаля. можно и на 4, 5, 6 бить, но получится перерасход зверьков. =)

← →
Слоник (2006-03-24 12:01) [9]

Marser © (24.03.06 11:58) [7]
А как же условие действия яда через сутки?
имел в виду, что как только яд начинает действовать, кролик погибает, а не сторит из себя здорового

← →
Sandman25 © (2006-03-24 12:02) [10]

Слоник (24.03.06 11:59) [8]

Не понял. Можно наглядный пример?

← →
Sandman25 © (2006-03-24 12:03) [11]

Слоник (24.03.06 11:59) [8]

А, теперь понял. Красиво!

← →
oldman © (2006-03-25 13:05) [12]

кроликов жалко...
вина тем более...
хватит и одного мужика на 2400 часа как максимум...

← →
Слоник (2006-03-25 15:13) [13]

хватит и одного мужика на 2400 часа как максимум...
слабо коррелирует с желанием поберечь вино =)

← →
SergP © (2006-03-25 18:08) [14]

> слабо коррелирует с желанием поберечь вино =)

Зато хорошо коррелирует с желанием сберечь закуску...

← →
Sandman25 © (2006-03-27 10:48) [15]

Слоник (24.03.06 11:34)

А вообще деление на группы по N кроликов равноценно взятию комбинаций с N единицами, поэтому все алгоритмы сводятся к моему :)
И оптимально для спасения кроликов взять
1 комбинацию из 10 нулей, 10 комбинаций из 9 нулей и 1 единицы, 45 клмбинаций из 8 нулей и 2 единиц и остальное из 7 нулей и 3 единиц. Тогда умрут от 0 до 3 кроликов. Очевидно, наилучшим будет наличие 99 кроликов и 1 комбинация из 99 нулей и 99 комбинаций из 98 нулей и 1 единицы.

← →
Слоник (2006-03-27 11:51) [16]

> А вообще деление на группы по N кроликов равноценно взятию
> комбинаций с N единицами, поэтому все алгоритмы сводятся
> к моему :)

ну мой не отличается от твоего =) только у меня кодируются равномерно

> 1 комбинацию из 10 нулей, 10 комбинаций из 9 нулей и 1 единицы,
> 45 клмбинаций из 8 нулей и 2 единиц и остальное из 7 нулей
> и 3 единиц. Тогда умрут от 0 до 3 кроликов. Очевидно, наилучшим
> будет наличие 99 кроликов и 1 комбинация из 99 нулей и 99
> комбинаций из 98 нулей и 1 единицы.

не поверишь - ехал на работу, думая как нужно кодировать, чтобы спасти побольше =)) до итоговых чисел, правда, не дошёл - за жизнь приходилось бороться в транспорте

← →
Sandman25 © (2006-03-27 12:00) [17]

Слоник (27.03.06 11:51) [16]

Я тоже за кроликов сильно переживал. Даже подумал, что следует провести химанализ, или, в крайнем случае, задействовать мышей. Мышей не так жалко, как кроликов :)

Вообще, мне кажется, большинство людей склонно тем больше жалеть млекопитающее, чем это млекопитающее больше по размерам :)

← →
euru © (2006-03-27 12:24) [18]

Для спасения максимального количества кроликов можно поступить следующим образом:
1. Разделить 100 бутылок на 10 групп по 10 бутылок.
2. Каждого кролика приписываем к одной группе бутылок и даём ему попробовать вино из всех бутылок этой группы.
3. Ждём 24 часа.
4. Смотрим, какой кролик умер. В группе бутылок, из которых пробовал этот кролик, есть бутылка с ядом.
5. Оставшимся 9 кроликам раздаём по бутылке из ядовитой группы и даём каждому из них попробовать из своей бутылки. Одна бутылка остаётся нераспробованной.
6. Ждём 24 часа (чтобы не было томительно, можно распить 90 бутылок, не входящих в ядовитую группу).
7. Смотрим, какой кролик умер. Если есть такой кролик, значит, бутылка, из которой он пробовал, содержит яд. Если все кролики живы, значит, с ядом бутылка, которую на втором этапе кролики не пробовали.

Итого: 1-2 погибших кролика.

euru © (27.03.06 12:24) [18]

Алгоритм можно существенно улучшить :)

Result := 1; for I := 2 to 100 do begin дать_единственному_кролику_выпить_из_бутылки(I); sleep(24часа); if кролик_умер then begin Result := I; break; end; end;

Один кролик нужен, с вероятностью 0.99 он умирает.

← →
Слоник (2006-03-27 12:37) [20]

> 3. Ждём 24 часа.

всё бы ничего, но через 24 часа уже планируется застолье и братва расчитывает попить винца, закусив выжившими зверятами

← →
Слоник (2006-03-27 12:48) [21]

ещё вот
коза, волк, капуста в японии
http://freeweb.siol.net/danej/riverIQGame.swf
эту хрень по слухам давали японцам при приёме на работу

Слоник (27.03.06 12:48) [21]

эту хрень я еще в начальных классах решал. японцы на работу школьников набирают, или они с секундомером рядом с ищущим решение стоят? :)

> имел в виду, что как только яд начинает действовать, кролик
> погибает, а не сторит из себя здорового

:))))))))))))))))))))))

Гринписа на вас не хватет :)

> Sandman25 © (27.03.06 12:35) [19]
>
> Алгоритм можно существенно улучшить :)

Времени может тогда уйти много. Можно считать, что у меня экспресс-анализ, дающий 100% результат через двое суток и сохраняющий жизнь максимальному количеству кроликов. :)

euru © (27.03.06 13:35) [24]

А у меня через 99 суток максимум, но зато действительно максимальное сохранение. Остальных кроликов можно задействовать на других фронтах работ :)

← →
Kaban (2006-03-27 14:12) [26]

кроме того, если не делить кроликов по группам, существует вероятность, что количество кроликов вскоре станет превышать количество бутылок

задачка Найти похожие ветки