Comments 10
Мудрено как-то изложено :) Букаф многа, ни асилил.
Но если по-простому, то вот классическая задача. Дано: 8 монет одного достоинства, внешне неотличимых друг от друга. Одна монета ТЯЖЕЛЕЕ прочих. Есть стандартные весы с двумя чашами. За какое МИНИМАЛЬНОЕ количество взвешиваний можно найти эту монету?
Варианты 3 и 4 дополнительно предполагают вспомогательную подлинную монету на старте, благодаря чему можно обработать на одну монету больше. Т.е. при C взвешиваниях, в варианте 3 будет лимит N = (3^N + 1)/2 монет, а в варианте 4 лимит N = (3^N - 1)/2. Решение удобней анализировать именно с такой монетой, потому что после первого взвешивания мы всё равно приходим как раз к такой разновидности.
Скрытый текст
Тернарность результата взвешивания - рассмотрена?
Теперь - почитаю статью.
Еще хорошо бы доказать, что ваша стратегия взвешивания оптимальна. Например, в первом случае вы получаете ceil(log_3(N)) взвешиваний. С другой стороны, сделав K взвешиваний вы получаете 3^k возможных результатов (каждое взвешивание дает 3 исхода). Поэтому, чтобы каждая из N монет могла быть идентифицированна как фальшивка, вам надо чтобы 3^k >= N, т.е. k >= ceil(log_3(N)). Поэтому ваш способ точно оптимальный. В четвертом случае оценка снизу ceil(log_3(2*N)), потому что исходов в 2 раза больше - каждая их N монет может оказаться той самой и быть или легче или тяжелее. Вот в третьем варианте все сложно. Вроде как только для определения фальшивки получается тоже ceil(log_3(N)), но ваше решение требует больше взвешиваний, поэтому не очевидно, что оно оптимальное.
Головоломки с балансом. Поиск фальшивой монеты (часть 1)