На столе N монет, одна из которых фальшивая. Она отличается от остальных лишь по массе. За какое минимальное число взвешиваний на чашечных весах можно обнаружить фальшивую монету?
Решение:
Возьмем за число взвешиваний k, тогда:
kmin -- минимальное число взвешиваний. А как взвешивать, это уже совсем другая история %)
Ответ не имеет смысла, если не рассказать о хотя бы одном способе взвешивания.
ReplyDeleteИмеет, так как он позволяет вывести минимальное число взвешиваний. Иногда важен ответ, а не то как мы его получили.
DeleteА алгоритм в принципе простой. Это всего лишь дерево их трех состояний: больше, меньше или равно. Вот такая трихотомия :)