Главная

Решение задач на определение фальшивой монеты взвешиванием

2013-02-18 в 8:21, admin, рубрики: Песочница, сортировка, метки: сортировка

Доброй ночи всемам.

Искал на днях ТЗ для углубления знаний по программированию и наткнулся на одном сайте на задачу о взвешиваниях монет для выявления фальшивой.

У этой задачи есть несколько разновидностей:
1) определить число взвешиваний для выявления фальшивой монеты (она легче или тяжелее)
2) определить алгоритм взвешивания
3) определение тяжелее или легче фальшивая монета
ну и компоновки разновидностей.

Можно было погуглить, но чем-то она меня зацепила, и после нескольких часов ночного осмысливания результатов удалось получить следующее:

1. Определяем количество взвешиваний

из 3 монет фальшивую можно определить за одно взвешивание (она будет либо одна из взвешиваемых, либо в остатке)
из 9 монет можно определить за 2 взвешивания
из 27 — за 3 взвешивания, и т. д.

Итого чтобы определить количество взвешиваний — n для A — количества монет, необходимо выполнение условия:
3ⁿ >= 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 взвешивания ( для определения группы и для определения монеты).