http://habrahabr.ru/post/243461/
Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.
Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:
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 |
по формуле — log
326 =2.9656 — соответственно количество взвешиваний — 3.
еще пример:
число монет- 71. По формуле log
371 =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 — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.