Замечательный алгоритм Джека Верта можно найти здесь
(как описано для случая n в форме (3 ^ k-3) / 2, но оно обобщается на другие n, см. Рецензию ниже)
Более короткая версия и, возможно, более читаемая версия здесь
Для n формы (3 ^ k-3) / 2 вышеупомянутое решение применимо идеально, и минимальное количество необходимых взвешиваний равно k.
В других случаях ...
Адаптация алгоритма Джека Верта для всех n.
Чтобы изменить приведенный выше алгоритм для всех n, вы можете попробовать следующее (хотя я не пытался доказать правильность):
Сначала проверьте, не n ли из (3 ^ k-3) / 2. Если это так, примените приведенный выше алгоритм.
Если нет,
Если n = 3t (т. Е. N кратно 3), вы найдете наименьшее m> n такое, что m имеет вид (3 ^ k-3) / 2. Количество необходимых взвешиваний будет k. Теперь сформируйте группы 1, 3, 3 ^ 2, ..., 3 ^ (k-2), Z, где 3 ^ (k-2)
Примечание: нам также нужно было бы обобщить метод A (случай, когда мы знаем, тяжелее ли монета легче), для произвольного Z.
Если n = 3t + 1, попробуйте решить за 3t (оставив один мяч в стороне). Если вы не найдете лишний шар среди 3t, то тот, который вы оставили в стороне, неисправен.
Если n = 3t + 2, сформируйте группы для 3t + 3, но у одной группы не должно быть одной группы шаров. Если вы выходите на сцену, когда вам нужно вращать группу из одного шара, вы знаете, что дефектный шар - это один из двух шаров, и вы можете затем взвесить один из этих двух шаров против одного из известных хороших шаров (из числа других 3t). .