Поддельная проблема с монетами

Question

Классическая задача с 12 монетами (или мраморами), одна из которых фальшивая. Поддельная монета считается более легкой, чем настоящая.

Наличие весов для сравнения монет (или мраморов).

Можно сравнить один за другим и сравнить все 12 монет.

Более эффективно это можно сделать с помощью алгоритма уменьшения по коэффициенту. То есть разделите стопку монет на 2 и сравните 2 стопки на весах.

Большой O уменьшения в 2 раза равен log2n.

Есть более эффективный алгоритм уменьшения коэффициента 3 (log3n), но я пока не нашел его.

Если кто-нибудь объяснит это и почему это более эффективно, дайте мне знать.

Answer 1

Основная идея здесь состоит в том, чтобы использовать больше знаний о проблеме при настройке теста: если вы разделите на 3 вместо двух стеков и проведете взвешивание с двумя из этих стеков (каждый из которых содержит одинаковое количество монет), вы может иметь только два случая, учитывая, что одна поддельная монета может быть только в одном из этих трех стеков:

1.) Обе стороны имеют одинаковый вес: поддельная монета не может быть в двух взвешенных стопках, поэтому должна быть и в третьей: вы уменьшили проблемное пространство до 1/3

2.) Одна сторона весит больше, чем другая: так как есть только одна поддельная монета, она должна быть на стороне, которая весит меньше: опять вы уменьшили проблемное пространство до 1/3

Сполосните и повторите.

Answer 2

Алгоритм «уменьшение на 3» работает по принципу, согласно которому вы можете уменьшить набор шариков, которые вы должны сравнить, на 1/3, выполнив только 1 сравнение.

Разделите шарики на 3 группы, и вес 2 из них, скажем, группы 1 и 2.

1. Если вес группы 1 == вес группы 2, то в группе 3 есть поддельный мрамор
2. Если вес группы 1 <вес группы 2, то группа 1 имеет поддельный мрамор </li>
3. Если вес группы 1> вес группы 2, то в группе 2 есть поддельный мрамор

Конечно, это предполагает, что исходный набор шариков можно равномерно разделить на 3 группы. Если это не так, тогда разделите на 3 группы равномерно (каждая группа имеет одинаковое количество шариков) и оставьте оставшиеся (0,1 или 2) шарики сбоку и добавьте их обратно в группу шариков, которую вы должны рассмотреть после шага сравнения.