Алгоритм для нахождения минимального количества коэффициентов требуемым найти дефектный шар от ряда n шарами
Хорошо вот загадка, я сталкиваюсь с большим количеством времен - Данный ряд 12 шаров, один из которых является дефектным (это весит или меньше или больше). Вы, позволяют весить 3 раза, чтобы найти дефектное и также сказать, который весит меньше или больше.
Решение этой проблемы существует, но я хочу знать, можем ли мы алгоритмически определить, если данный ряд 'n' шары, что является минимальным количеством раз, которое необходимо было бы использовать баланс луча для определения, какой является дефектным и как (легче или более тяжелый).
3 ответа
Замечательный алгоритм Джека Верта можно найти здесь
(описан для случая, когда 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).
Можно использовать общий алгоритм планирования: http://www.inf.ed.ac.uk/teaching/courses/plan/
Трихотомия! :)
Пояснение: Дан набор из n шаров, разделите его на 3 набора A, B и C по n / 3 шаров.
Сравните A и B. Если они равны, то дефектный шар находится в C. и т. д.
Итак, ваше минимальное количество раз - это количество раз, когда вы можете разделить n на три (извините, я не знаю английского слова для этого).