Комментарии 46
О, универсальная методика решения задач, ну наконец-то. Решите, пожалуйста, P = NP.
Хотя я согласен с вашим общим настроем, но отмечу, что конкретно для этой задачки зависли на 2-й стадии (декомпозиции). Пока доказывают что-то для частных случаев, но «глобальной декомпозиции» пока провести не удалось.
P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)
P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)
Вы упустили случай P=0, N — любое)
Мне учительница математики помню рассказывала.
Она подрядилась быть репетитором для старшекласника. Подготовка к поступлению в ВУЗ.
И вот на первом занятии она дает задает ему вопрос:
как можно преобразовать
six^2 x/cos^2 x
Получает ответ:
six^2 x/cos^2 x =
sixx/cos x =
sin/cos
in/co
На этом месте она поняла, что работы… предстоит много.
Она подрядилась быть репетитором для старшекласника. Подготовка к поступлению в ВУЗ.
И вот на первом занятии она дает задает ему вопрос:
как можно преобразовать
six^2 x/cos^2 x
Получает ответ:
six
six
in/co
На этом месте она поняла, что работы… предстоит много.
За 3 взвешивания необходимо найти фальшивую монетку и определить легче она или тяжелее.
Решение не до конца.
Хм, я уверен, что я тоже это видел, но похоже автор уже изменил условия чтобы они соответствовали его решению…
В любом случае, оригинальная задача показалась мне интереснее и я ее, кажется, решил:
В любом случае, оригинальная задача показалась мне интереснее и я ее, кажется, решил:
Решение
Как найти фальшивую монетку и определить легче она или тяжелее.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
image upload
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
image upload
del
В любом случае из условий
Неизвестно легче или тяжелее— соответственно и относительный вес монеты будет найден.
К сожалению, нет. Я не буду проверять все варианты, но очевидно, что алгоритм не работает на примере 12 монеты. В посте решение о том, что она фальшивая принимается в результате цепочки, в которой 12 монета вообще ни разу не оказывается на весах — 1234 = 5678, 9 = 10, 10 = 11. В данном случае она может быть легче, тяжелее, и даже точно такого же веса.
Тут было неправильное решение, я его, пожалуй, сотру. Спасибо людям из комментов ниже за указание на ошибку.
Извините, в вашем решении так и не понял, как вы за одно взвешивание выделили целевую кучку из трех?
Раньше думал, эта задача имеет единственное решение. Теперь появилась новая задача — сколько решений имеет эта задача?
DEL
На самом деле выше я пропустил две ветви в самом конце решения. Вот тут полное дерево:
Решение
Как найти фальшивую монетку и определить легче она или тяжелее.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
Ну допустим я злоумышленник и подложил «облегчённую» монету №7 где для неё вариант?
И тут вообще только 16 вариантов из 24 (12* L-H) возможных.
Или я что-то упустил?
И тут вообще только 16 вариантов из 24 (12* L-H) возможных.
Или я что-то упустил?
Похоже что упустили. Если 7 (или 5, 6 или 8) монета легче сработает блок "… swap 1234 with 5678". Алгоритм то один и тот же на самом деле, я решил сэкономить место и не расписывать оба варианта. Просто поменяйте кучки 1234 и 5678 местами и продолжайте, теперь легкая монета будет иметь индекс 3. Прошу прощения за неочевидность.
Ок да, разобрался. Странноватый алгоритм, кажется что можно проще. Интересно, сколько вообще существует алгоритмов решения данной задачи?
Я пока знаю только одно решение, мое. Решение автора я не считаю решением первоначальной задачи, так как оно не отвечает на вопрос легче или тяжелее?
Вы знаете другие решения? Поделитесь?
Вы знаете другие решения? Поделитесь?
Решение автора отвечает на вопрос "легче или тяжелее" на втором-третьем взвешивании, в зависимости от результатов взвешивания. Единственное исключение — когда после первого взвешивания, фальшивая монета оказывается в третьей группе, и в последующие 2 взвешивания она не попадает. Тогда да, ее вес неизвестен.
Три, как минимум -> mathforum.org/library/drmath/view/55618.html. Мне второе больше всех нравится, хотя (во всех) коряво то, что монеты по условию выглядят одинаково, а если их пронумеровать, то выглядеть одинаково они перестанут.
Вместо сравнения 1 2 5 6 vs 4 8 11 12 достаточно сравнить 5 6 12 vs 4 7 8. И «тройки» сравнивать чуть легче, чем «четвёрки», и «лёгкость» фальшивой монеты более однородно по случаям распределится. У Вас в каждом из трёх случаев она может быть как легче, так и тяжелее нормальной. А в данном варианте в случае "=" монета всегда H, при сохранении неравенства ">" монета всегда L, и только при смене неравенства на "<" будут смешанные варианты.
Если не ошибаюсь, где-то во второй половине девяностых, целое семейство задач про монеты, с их подробным разбором было опубликовано в журнале Компьютерра. Я, тогда ещё школьник, здорово помучился, пока не сообразил, что, взвешивая две из трёх частей, мы не только сужаем количество монет, среди которых фальшивая, но и получаем гарантированно «настоящие» эталоны, которые можно использовать в последующих взвешиваниях.
А почему нельзя так?
1 взвешивание 6vs6
2 взвешивание 3vs3
3 взвешивание 1vs1 и если равны то оставшаяся?
1 взвешивание 6vs6
2 взвешивание 3vs3
3 взвешивание 1vs1 и если равны то оставшаяся?
Потому что неизвестно, является ли фальшивая монета легче или тяжелее настоящей. Вы взвешиваете 6 vs 6 и одна группа монет тяжелее другой. Но что это значит? В тяжёлой группе есть тяжёлая фальшивая монета или же в лёгкой группе — лёгкая фальшивая монета? Ноль полезной информации.
2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».
Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:
- Равны. Фальшивая монета находится среди чисел: 6 7 8.
А двенадцатая монета куда подевалась?
Поставило в тупик «3 взвешивания» а в решении приводится далеко не 3!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Декомпозиция и понижение энтропии для программиста на примере головоломки «12 монет, 3 взвешивания найти фальшивую»