Искал на днях ТЗ для углубления знаний по программированию и наткнулся на одном сайте на задачу о взвешиваниях монет для выявления фальшивой.
У этой задачи есть несколько разновидностей:
1) определить число взвешиваний для выявления фальшивой монеты (она легче или тяжелее)
2) определить алгоритм взвешивания
3) определение тяжелее или легче фальшивая монета
ну и компоновки разновидностей.
Можно было погуглить, но чем-то она меня зацепила, и после нескольких часов ночного осмысливания результатов удалось получить следующее:
1. Определяем количество взвешиваний
- из 3 монет фальшивую можно определить за одно взвешивание (она будет либо одна из взвешиваемых, либо в остатке)
- из 9 монет можно определить за 2 взвешивания
- из 27 — за 3 взвешивания, и т. д.
Итого чтобы определить количество взвешиваний — n для A — количества монет, необходимо выполнение условия:
3n >= A, или logA / log3 <= n,
где
- A — количество монет,
- n — количество взвешиваний (округленное в большую сторону целое)
- log — десятичный логарифм.
например:
- для 26-ти монет нужно log26/log3 = 2.966, n = 3 взвешиваний
- для 1563-х монет — log1563/log3 = 6.694 n = 7 взвешиваний
2. Алгоритм взвешивания
Теперь покажу общий алгоритм взвешивания A монет (дабы пояснить п.1) и буду использовать некое подобие алгоритмического языка. Пускай мы знаем, что фальшивая монета тяжелее/легче
1) Определяем количество взвешиваний. Как правило в задачах задается за какое количество взвешиваний нужно определить фальшивую монету, но мы таким образом проверим, имеет ли задача решение. Согласно п. 1 получаем число n.
logA / log3 <= n
2) Далее разделяем монеты на 2 группы следующим образом
если искомое число нечетное
B = A — 3(n — 1)
если искомое число четное
B = A — 3(n — 1) + 1
и вторая группа
C = A — B
3) группу B — делим по полам на две группы (левая группа — ЛГ, правая группа ПГ). У нас получится три группы
ЛГ, ПГ, C.
4) Группы ЛГ, ПГ — взвешиваем и определяем группу с фальшивой монетой (D). Возможны 3 варианта:
а) левая группа (ЛГ) монет на весах тяжелее/легче (D = ЛГ)
б) правая группа (ПГ) монет на весах тяжелее/легче (D = ПГ)
в) группы монет на весах одинаковые, тогда фальшивая монета в остатке (D = C).
5) Для группы, найденной в п.4 повторяем пп 1- 4 (A = D), пока количество монет больше 2 ( A > 2)
6) если осталось 2 монеты, выполняем последнее взвешивание (ЛГ = 1 и ПГ = 1)
7) фальшивая монета найдена.
Рассмотрим для наглядности задачу, пусть она будет с того же сайта: нужно разделить 12 монет за 3 взвешивания, фальшивая монета — легче.
1) количество взвешиваний
log12/log3 = 2.261
n = 3 (ну что же, задача решение имеет)
2) делим на группы
B = 12 — 3(3 — 1) + 1 = 4
C = 12 — 4 = 8
3) группу B делим пополам:
ЛГ = 2, ПГ = 2, остаток C = 8
4) Взвешиваем ЛГ и ПГ.
Варианты после 1-го взвешивания
а) ЛГ = 2 — с фальшивой монетой (переходим к п. 6)
б) ПГ = 2 — с фальшивой монетой (переходим к п. 6)
в) остаток (C=8) — с фальшивой монетой. повторяем пп.1-4 для 8-ми монет
A=8
1) количество взвешиваний
log8/log3 = 1.893
n = 2
2) делим на группы
B = 8 — 3(2 — 1) + 1 = 6
C = 8 — 6 = 2
3) группу B делим пополам:
ЛГ = 3, ПГ = 3, остаток C = 2
Варианты после 2-го взвешивания
а) ЛГ = 3 — с фальшивой монетой (повторяем пп.1-4 для 3-ми монет A=3)
б) ПГ = 3 — с фальшивой монетой (повторяем пп.1-4 для 3-ми монет A=3)
в) остаток (C=2) — с фальшивой монетой. переходим к п. 6)
Ну и 3-е взвешивание — из 2-х или 3-х монет определить фальшивую, причем для 3-х монет правило тоже сработает.
Еще пример для 25-ти монет
1) n = 2.93 = 3
2) B = 25 — 3(3 — 1) = 16
C = 25 — 16 = 9
3) ЛГ = 8, ПГ = 8, С = 9
Варианты после 1-го взвешивания
а) D = ЛГ = 8
б) D = ПГ = 8
в) D = C = 9
Взвешивание 8-ми монет показано в предыдущем примере (ну так выгодно случайно совпало), покажу для 9-ти.
A = 9
1) n = 2
2) B = 9 — 3(2 — 1) = 6
C = 9 — 6 = 3
3) ЛГ = 3, ПГ = 3, С = 3
ну и еще 2 взвешивания ( для определения группы и для определения монеты).
3. Определение тяжелее или легче фальшивая монета
Остался 3-й пункт задачи — определить тяжелее фальшивая монета или легче.
Этому решению будет посвящена отдельная статья (ну я так думаю, что будет).