Замечательный алгоритм Джека Верта можно найти здесь
(как описано для случая 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) ‹ Z ‹ 3^(k-1) и повторите алгоритм Джека. решение.
Примечание: нам также потребуется обобщить метод A (случай, когда мы знаем, тяжелее или легче монета) для произвольного Z.
Если n = 3t+1, попробуйте решить для 3t (оставив один шар в стороне). Если вы не найдете лишнего шара среди 3t, значит, тот, что вы отложили в сторону, бракованный.
Если n = 3t+2, сформируйте группы по 3t+3, но пусть в одной группе не будет группы с одним мячом. Если вы дойдете до стадии, когда вам нужно вращать одну группу шаров, вы знаете, что дефектный шар — это один из двух шаров, и вы можете затем взвесить один из этих двух шаров против одного из заведомо исправных шаров (из числа остальных 3t). .
person
Community
schedule
13.07.2010
