Т.е., метод работает с вероятностью 1/2, т.к. в "другой истории" к предложенному алгоритму требуется еще одно дополнительное взвешивание. Это не есть решение.Цитата:
Сообщение от Г_Росс
Вид для печати
Т.е., метод работает с вероятностью 1/2, т.к. в "другой истории" к предложенному алгоритму требуется еще одно дополнительное взвешивание. Это не есть решение.Цитата:
Сообщение от Г_Росс
В 12.5% попытокЦитата:
Сообщение от MMM
2-е взвешивание. Независимо от его результата получим 2 монеты, одна из которых - плохая.Цитата:
1 взвешивание: 4 и 4. Если равны - фальшивая в 4 оставшихся, если не равны - фальшивая в 8-ти взвешиваемых, из которых 4 назовём условно "тяжёлыми", а другие 4 условно "лёгкими".
Ветвеление 1. Если фальшивая в 4-х оставшихся -- сравниваем 2 из них с двумя нормальными,
и 3-е взвешивание определит плохую монету.Цитата:
а затем одну из ненормальных с одной нормальной. (описано выше)
2-взвешивание. И отложили 2 "легких" и 1 "тяжелую"Цитата:
Ветвление 2. На 1-ю чашу кладём 2 "лёгких" и 3 "тяжёлых" (запоминаем их), на 2-ю - 4 нормальных и 1 "тяжёлую".
А если чаша в равновесии, тоЦитата:
Если чаша с нормальными тяжелее, то выбор из 2 лёгких и 1 тяжёлой.
это в худшем случае - 2 взвешивания. Итого - 4.Цитата:
следует выбор либо из 2-х лёгких и 1 тяжёлой (чаши равны), либо из 3-х тяжёлых (чаша с нормальными легче).
в худшем случае 2 взвешиванияЦитата:
3 взвешивание: 1 лёгкая и 1 тяжёлая против 2-х нормальных (если выбор из 2+1),
Если в этом случае весы не в равновесии, то потребуется еще одно (четвертое) взвешивание, что бы решить, какая монета плохая, сравнив одну из них с хорошей, в силу того, что нам не известен знак отклонения пв весе плохой монеты.Цитата:
либо "тяжёлая" против "тяжёлой", если выбор из 3-х.
Как видим, далеко не все...Цитата:
Всё.
На самом деле задачка проста и сводится к задаче обычного бинарного (весы равноплечные) поиска одного элемента и множества N элементов. Для такой задачи известно, что если искомый элемент присутствует в множестве, то он может быть найден не более чем за Log(N) попыток, где логарифм берется по основанию 2 (поиск бинарный или двочный). В нашем случае множество состоит из 12-ти элементов, значит гарантировано "плохая" монета может быть найдена "чуть менее" чем за 4 попытки и "чуть более" чем за 3 попытки, т.е. за 4 попытки. А посему исходная задача (гарантированный поиск за 3 попытки) решения не имеет. За 3 попытки эту задачу можно решить только в случая некоторого везения, т.е. с определенной вероятностью, меньшей 1, или негарантированно.Цитата:
Сообщение от Г_Росс
Сама процедура бинарного поиска поиска в данной задаче выглядит так.
1 этап (не более 2-х взвешиваний) - сужение множества, содержащего плохую монету до 4-х элементов. Для этого делим монет на 3 равные кучи по 4 монеты. Взвешиваем 2 кучи из трех. Если весы в равновесии, то нам повезло и плохая монет находится в невзвешиваемой куче (мы сэкономили одну попытку, но вероятность такого везения -1/2). Если нет, то второе взвешивание гарантировано определит кучу с "плохой" монетой.
2 этап (не более 2-х взвешиваний) сужение множества, содержащего 4 монеты до искомой одной "плохой монеты". Сначала разделим чеиыре монеты на кучу из 3-х монет и одну "отложенную" монету. Далее для 3-монет используем алгоритм, аналогичный этапу 1, в котором слово "куча" заменено на слово "монета". При этом 2 взвешивания (3-е и 4-е) гарантировано покажут нам либо плохую монету (что и требовалось получить) либо ее отсутствие в куче из 3-монет. Но в последнем случае плохой будет "отложенная" монета, при этом мы не будем знать в какую сторону отличается ее вес от нормальной ( но этого исходная задача и не требовала), для этого потребуется дополнительное 5-е взвешивание.
