Алгоритм для поиска минимального количества весов, необходимых для поиска дефектного шара из набора n шариков

Question

Хорошо, вот головоломка, с которой я сталкиваюсь много раз. Учитывая набор из 12 шаров, один из которых неисправен (он весит либо меньше, либо более). Вы можете весить 3 раза, чтобы найти дефектный, а также рассказать, что весит меньше или больше.

Решение этой проблемы существует, но я хочу знать, можем ли мы алгоритмически определить, если задан набор «n» шаров, каково минимальное количество раз, когда вам нужно использовать баланс луча, чтобы определить, какой из них дефектный и как (легче или тяжелее).

Answer 1

Прекрасный алгоритм Джек Wert можно найти здесь

• http://www.cut-the-knot.org/blue/OddCoinProblems.shtml

(как описано для случая п имеет вид (3^к-3)/2, но является обобщенным к другому п см ниже) рецензии

сокращенному варианту и, вероятно, более читаемый вариант, что здесь

• http://www.cut-the-knot.org/blue/OddCoinProblemsShort.shtml

Для п вида (3^к-3)/2, указанное решение применяется совершенно и минимальное количество взвешиваний, необходимых равен к.

В других случаях ...

---

Адаптация алгоритма Jack Wert для всех п.

Для того, чтобы изменить выше алгоритм для всех п, вы можете попробовать следующее (я не пытался доказать свою правоту, хотя):

Сначала проверьте, если п из из (3^к -3)/2. Если это так, примените выше алгоритм.

Если нет, то

Если п = 3t (т.е. п кратно 3), вы найти наименьшее т> п такое, что т имеет вид (3^к-3)/2. Количество требуемых весов будет k. Теперь сформируем группы 1, 3, 3^2, ..., 3^(k-2), Z, где 3^(k-2) < Z < 3^(k-1) и повторим алгоритм от Джека решение.

Примечание: Мы также должны обобщить метод А (случай, когда мы знаем, если монета тяжелее зажигалки), для любого Z.

Если п = 3t + 1, попытаться решить для 3т (удерживая один мяч в сторону).Если вы не найдете нечетного шара среди 3t, тот, который вы оставили в стороне, неисправен.

Если n = 3t + 2, образуют группы для 3t + 3, но одна группа не имеет одной шаровой группы. Если вы приходите на сцену, когда вам нужно вращать одну группу мячей, вы знаете, что дефектный мяч является одним из двух мячей, и вы можете взвесить один из этих двух мячей против одного из известных хороших мячей (из других 3т) ,

Answer 2

Трихотомия! :)

Объяснение: Учитывая набор из n шаров, разделите его на 3 набора A, B и C из n/3 шаров.

Сравнить A и B. Если равны, то дефектный шар в С. и т.д.

Итак, ваше минимальное количество времени это количество раз, вы можете разделить п на три (извините, я делаю не знаю английского слова для этого).

Answer 3

Вы можете использовать алгоритм общего планирования: http://www.inf.ed.ac.uk/teaching/courses/plan/