to backspace
К задаче о монетах, вот мой алгоритм Вашего решения
Пусть есть три гипотезы
Первая гипотеза - Фальшивой является одна из A, B, C
Для проверки гипотезы распределим монеты по взвешиваниям таким образом
А X X X __________ X X X X
B X X X __________ X X X X
C X X X __________ X X X X
Где Х – любая другая монета
Вторая гипотеза – фальшивой является одна из D. E, F
Для проверки гипотезы распределим монеты по взвешиваниям таким образом
D F X X __________ X X X X
D E X X __________ X X X X
E F X X __________ X X X X
Третья гипотеза – фальшивой является одна из шести - G, H, I, K, L, M
Для проверки гипотезы разделим шесть монет на три группы – GH, IK, LM и распределим эти пары по взвешиваниям таким образом
G H X X __________ L M X X
I K X X __________ G H X X
L M X X __________ I K X X
Для каждой гипотезы можно определить события, подтверждающие ее истинность и соответственно найти фальшивую монету
Для первой – только в одном взвешивании из трех чашки не уравновешиваются
Для второй – в двух взвешиваниях из трех чашки не уравновешиваются, причем в обоих случаях правая чашка либо легче, либо тяжелее левой. Каждая из трех монет взвешивается два раза в комбинации с двумя остальными. Монета которая участвует в обоих неуравновешенных взвешиваниях - фальшивая
Для третьей – хотя бы в двух взвешиваниях из трех чашки не уравновешиваются. Причем в одном взвешивании левая тяжелее правой, а в другом случае правая тяжелее левой.
Для определения фальшивой монеты из пары используется третье взвешивание.
Остается только упаковать три наших способа проверки гипотез в три взвешивания.
Дополнение: Решил дополнить логику поведения в случае если третья гипотеза оказалась верной. Допустим фальшивой оказалась одна из двух монет GH. То есть допустим в первый раз левая чашка весов была легче правой, а во втором взвешивании наоборот
Вопрос: Как узнать какая из двух монет GH - фальшивая?
Допустим мы разложили монеты по взвешиваниям следующим образом
A G H I -------- D F L M
B I K L -------- D E G H
C L M G -------- E F I K
Тогда если в третьем взвешивании чашки весов не уравновешенны, значит G - фальшивая монета
Сообщение отредактировал erbolg: 27 March 2012 - 14:10