Методы уменьшения размера задачи

Среди `n` одинаково выглядящих монет одна — фальшивая. Будем считать, что фальшивая монета легче настоящей. На рычажных весах вы можете сравнить любые два множества монет и получить ответ, какое из множеств тяжелее (или что они равны по весу), но не на какую именно величину. Задача заключается в том, чтобы разработать эффективный алгоритм для поиска фальшивой монеты.

Наиболее естественный подход к решению данной версии задачи — разделить `n` монет на две кучки по `|__n//2__|` монет в каждой, отложив одну монету, если `n` — нечетное число. Если кучки имеют одинаковый вес, то отложенная монета и является фальшивой; если нет — мы выбираем более легкую кучку и выполняем описанные действия с ней. Хотя мы и разделили все монеты на две кучки, после взвешивания надо решить только одну задачу половинного размера. Следовательно, в соответствии с нашей классификацией методов проектирования алгоритмов, этот алгоритм относится к алгоритмам уменьшения размера задачи (вдвое), а не к алгоритмам на основе декомпозиции.

Легко записать рекуррентное уравнение для количества взвешиваний `W(n)`, необходимых алгоритму в наихудшем случае:
`W(n) = W(|__n//2__|) + 1` при `n> 1`, `W(1) = 0`.

Его решение `W(n) = |__log_2 n__|`.

Это решение — не самое эффективное. Мы можем поступить разумнее, если будем делить монеты на три кучки, примерно по `n//3` монет в каждой. После взвешивания двух кучек мы можем уменьшить размер экземпляра задачи в три раза, так что необходимое количество взвешиваний будет примерно равно `log_3 n`, что меньше, чем `log_2 n`.