Поиск всех тяжелых монет в 0 (log^2 (n))

Question

Предположим, вам даны n монет, некоторые из которых тяжелые, а остальные свет. Все тяжелые монеты имеют такой же вес, как и все легкие монеты, и вес тяжелой монеты строго больше веса легкой монеты. Как минимум одна из монет известна как свет. Вам дается баланс, , с помощью которого вы можете взвесить подмножество монет против другого непересекающегося подмножества монет. Покажите, как вы можете определить количество тяжелых монет с использованием взвешивания O (log2 n).

Answer 1

Я думаю, это должно быть обобщением проблемы, когда у вас есть 8 монет, а один из них свет. Таким образом, вы можете выполнить своего рода бинарный поиск, чтобы найти самую легкую монету, используя пару балансов весов. Тем не менее, странно, что вы должны одновременно найти несколько легких монет. В этом случае это, похоже, не масштабируется с помощью log2 n.

См. Пример ниже, чтобы понять мою точку зрения. В случае 8 монет, где один из них светлый. Вы должны выполнить три этапа:

Шаг 1) Разделите образец на две части и найдите самую легкую часть. => 1 взвешивание. [У вас есть образец с 4 монетами, которые легче)

Шаг 2) Разделите самую легкую часть предыдущей процедуры и весьте эти части, чтобы найти самую легкую часть. => + 1 вес [у вас есть образец с 2 монетами]

Шаг 3) Теперь у вас есть только две монеты. Вы должны только весить их, чтобы найти самый легкий.

Конечно, обобщение на образец размера n тривиально.

Доказательство того, что эта шкала с log2 n следует за двоичным поисковым доказательством.

Однако, если количество светлых монет отличается от 1, вы не можете сфокусироваться только в самой легкой части образца. [Отказ: Возможно, я ошибаюсь, но трудно сказать, что это будет масштабироваться с помощью log2 n. Например, рассмотрим ситуацию, когда количество света монет масштабируется с п (количество монет)]

На самом деле, самое красивое решение этой проблемы, чтобы найти самую легкую монету всего два взвешиваний:

Шаг 1) Разделите ваш образец на 3 части. Первая часть состоит из трех монет, вторая часть также имеет три монеты, а последняя - только 2.

Шаг 2) Вес первой и второй частей. Существует три ситуации:

a) Первая часть легче.

б) Вторая часть легче.

c) Первая и вторая части имеют одинаковый вес.

Если (a или b), проследите два из них. Если они имеют одинаковый вес, то другой, который не был взвешен, легче. С другой стороны, если они не имеют такого же веса, то один из них является лихтером

если (c) просто весом двух монет, чтобы найти более легкий.

Это также может быть обобщено, но обобщение намного сложнее.