Подразделы

Другие разделы

Дата и время

05/01/2026 18:04:47

Авторизация

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

Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы

Задача поиска фальшивой монеты

Среди `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`.

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

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

Задача поиска фальшивой монеты