Tramvision
Всякая всячина => Головомойки и задачки => Тема начата: Почта сайта от 29 Август 2008, 00:30:09
-
Есть 15 арбузов, 2 из них радиоактивны (то есть несъедобны, ввиду нынешней политики на Кавказе). Есть помещение с датчиками, определяющее несъедобность любого товара, засунутого в эту камеру хранения. Но датчики не могут вычислить, какой именно арбуз несет в себе опасность - камера тупо реагирует на наличие радиоактивности в любой кучке арбузов, что вы будете пихать в нее.
Для удобства пользователя перед дверцей камеры установлена лампочка, которая срабатывает при наличии радиации и прочей фигни, то есть, приборы, установленные в камере, неспособны определить, какой именно арбуз смертелен для российского потребителя.
Ваша задача: вычислить опасные для здоровья арбузы.
Нужно изобрести способ проверки и обосновать методу, как отделить опасные арбузы С МИНИМАЛЬНЫМ числом заносов арбузов в камеру.
Любителей решать задачи умозрительно сразу предупреждаю - данная задача ОЧЕНЬ сложная даже для программистов.
Ну что, поехали?
PS Для любителей гуглить ответы скажу, что в данном случае ответ ничего не решает. Нужно объяснить, насколько вы сильны в алгоритмике, и есть ли у вас шанс трудоустроиться в компанию Google.
-
думаю нужно по 5 арбузов класть. 3 заноса(ну может быть и 2, если в первых двух пятерках находятся радиоактивные арбузы(РА), то третью уже нету смысла проверять). далее исход событий делится на 2 варианта:
1. допустим, что в 5 арбузах находятся 2 РА. тогда просто кладём по 2, 2, 1(максимум 4 заноса, миниум 3, чтобы выявить, какие 2 РА ) => всего 7 заносов максимум, 6 миниум.
2. допустим, что в одной пятерке 1 РА, и во второй или третей пятерки РА. опять же каждую пятерку проверяем по 2, 2, 1(максимум 3 заноса, миниум 2) => в итоге получается максиум 9 заносов, миниум 7.
вроде всё верно сформулировал)
-
Да ну нах... Дерево решений на целый лист получается... Вроде в 7 замеров можно уложиться. Завтра попробую выложить картинку с деревом.
-
Кощей, давайте посмотрим, как эту задачу решили "хабаровчане". Решение все равно сложное. Об этом я заявлял в условии задачи.
(http://www.tramvision.ru/daily/funpics/forums/300808.jpg)
-
теперь бы еще понять, что всё это значит.
и еще, в условии задачи написано: Нужно изобрести способ проверки и обосновать методу, как отделить опасные арбузы С МИНИМАЛЬНЫМ числом заносов арбузов в камеру.
я считаю, что лучше было бы поставить вопрос таким: Нужно изобрести способ проверки и обосновать методу, как 100% отделить опасные арбузы от остальных и с каким числом максимальных заносов это будет
Т.е. нужно найти самый наименьший максимум заносов, т.к. за миниум тогда можно считать и 2 заноса, просто вдруг из 15 арбузов, первые 2 будут опасными и мы их по одному занесём. ведь так может быть? может.
-
Хорошая картинка. У меня получилось нечто похожее, но я еще решал с вариантом двух групп, 7 и 8 арбузов в каждой.