Task 98. Количество взвешиваний
UniLecsЗадача: даны n шаров, все шары имеют одинаковый вес, кроме одного, ктр тяжелее. Необходимо за минимальное кол-во взвешиваний определить, какой из шаров является тяжелым. В данном случае операция взвешивания заключается в том, что на каждую из 2х чаш весов кладется одинаковое кол-во шаров. Если одна из чаш перевесила, то тяжелый шар среди положенных на нее. Если весы в равновесии, то тяжелый шар среди не лежащих на весах шарах.
Входные данные: n - натуральное число, где n больше 2.
Вывод: минимальное кол-во взвешиваний, необходимых для гарантированного обнаружения тяжелого шара.
Пример: n = 9
Answer = 2
Идея: разложим все шары на 3 одинаковые по кол-ву кучки. В случае, если N не делится на 3, то кучки будут отличаться не более чем на один шар. Далее положим одинаковые кучки на чаши весов. Таким образом за одно взвешивание мы определим в какой из 3х кучек находится тяжелый шар.
Получаем, что за одно взвешивание мы можем перейти от задачи с n шарами в общем случае к задаче с [n/3] шарами (округление в большую сторону).
В итоге, для гарантированного обнаружения тяжелого шара достаточно [log3(n)] взвешиваний (округление в большую сторону).
Рассмотрим пару примеров:
1. n = 3. В этом случае достаточно одного взвешивания.
2. n = 9. Разложим на кучки по 3 шара. Дальше сделаем одно взвешивание, после этого мы определим кучку в которой находится тяжелый шар. Делаем последнее взвешивание, после ктр мы точно сможем сказать, ктр шар тяжелый.
3. n = 8. Разложим кучи по 3 шара и одна кучка с 2мя шарами. Первое взвешивание будем выполнять с одинаковыми кучками по 3 шара.
Это самая простая задача из раздела задач на взвешивание, посмотреть подробнее вы можете тут:
Реализация:
https://gist.github.com/unilecs/eb3679be326d29ff2d49e525158b617a
Test: