Решение задач на определение фальшивой монеты взвешиванием 2.0
Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата. Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:
1) неизвестно какая она по весу;2) известно, что она легче/тяжелее остальных.
Или обратная задача: можно ли за определенное количество взвешиваний выявить фальшивую из заданного количества монет.
1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1. Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:
N >= log3A, где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону; A — количество монет.Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)Сам алгоритм решения простой, и я покажу его на примерах
1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее
Первым действием буде разделение монет на три группы, в двух из которых число монет будет одинаковым, важно только что бы в третьей группе — остатке — было меньше монет, чем в каждой из двух других групп. То есть частое округляется к большему натуральному числу. То есть
A = 2 * B + C, где A — количество монет; B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону; C — остаток.По условию задачи
26/3 = 8.666(6),
26 = 2×9 + 8,
При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.
Далее у нас возможны два варианта:
1) фальшивая монета в левой/правой группе (9 монет)2) фальшивая монета в остатке (8 монет)
для 1 варианта следующее деление на группы будет — 9 = 2×3 + 3; для 2 варианта — 8 = 2×3 + 2
Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее
Этот же результат я приведу в таблице
№ взвешивания Число монет ЛГ ПГ Остаток 1 26 9 9 8 2 8 3 3 2 2 9 3 3 3 3 2 1 1 0 3 3 1 1 1 по формуле — log326 =2.9656 — соответственно количество взвешиваний — 3.
еще пример: число монет- 71. По формуле log371 =3.8800 — количество взвешиваний — 4. Проверяем
№ взвешивания Число монет ЛГ ПГ Остаток 1 71 24 24 23 2 23 8 8 7 2 24 8 8 8 3 7 3 3 1 3 8 3 3 2 4 2 1 1 0 4 3 1 1 1 Ну с алгоритм решения этих задач, я думаю, понятен.
2. Теперь перейдем к задачам, в которых не известно легче монета или тяжелее. В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.A = 3 * B + C, где A — количество монет; B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону; C — остаток.Например, для 58-ми монет — это будет 58 = 3×19 + 1, для 23 = 3×7 + 2, для 15 = 3×5 + 0 и т. д.
Далее выполняем два взвешивания:1) первая и вторая группы;2) первая и третья группы; и анализируем результат.Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке. Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.
Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.Что касается формулы, то она примет следующий вид
N >= log3B + 2, где N — максимально необходимое количество взвешиваний, натуральное число; B — количество монет в группе после второго взвешивания.А если учесть, что B = A/3, где A — количество всех монет, тогда получим: log3B = log3A — 1, N >= log3A + 1 Итог: 1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле: N >= log3A 2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:
N >= log3A + 1 где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону; А — количество монет.
