Comments 46
О, универсальная методика решения задач, ну наконец-то. Решите, пожалуйста, P = NP.
+15
Хотя я согласен с вашим общим настроем, но отмечу, что конкретно для этой задачки зависли на 2-й стадии (декомпозиции). Пока доказывают что-то для частных случаев, но «глобальной декомпозиции» пока провести не удалось.
P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)
P.S. не знаю, что там автор час думал, я в своё время решил минут за 5 — и был одним из последних в нашей группе ребят-олимпиадников, кто это сделал (выше городских не поднимался, да)
0
UFO just landed and posted this here
Вы упустили случай P=0, N — любое)
0
Мне учительница математики помню рассказывала.
Она подрядилась быть репетитором для старшекласника. Подготовка к поступлению в ВУЗ.
И вот на первом занятии она дает задает ему вопрос:
как можно преобразовать
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
На этом месте она поняла, что работы… предстоит много.
0
За 3 взвешивания необходимо найти фальшивую монетку и определить легче она или тяжелее.
Решение не до конца.
+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
+1
del
0
В любом случае из условий
Неизвестно легче или тяжелее— соответственно и относительный вес монеты будет найден.
0
К сожалению, нет. Я не буду проверять все варианты, но очевидно, что алгоритм не работает на примере 12 монеты. В посте решение о том, что она фальшивая принимается в результате цепочки, в которой 12 монета вообще ни разу не оказывается на весах — 1234 = 5678, 9 = 10, 10 = 11. В данном случае она может быть легче, тяжелее, и даже точно такого же веса.
+1
Тут было неправильное решение, я его, пожалуй, сотру. Спасибо людям из комментов ниже за указание на ошибку.
0
А если фальшивая монета легче чем оригинал?
UPD: О! Исправились:) Но не до конца.
И я тогда дополню.
Не известно же легче фальшивка или тяжелее)
UPD: О! Исправились:) Но не до конца.
И я тогда дополню.
Не известно же легче фальшивка или тяжелее)
0
Стоило потратить ещё минуту на внимательное чтение условия) вы решили не ту задачу.
+2
А почему из более тяжелой кучи? Может фальшивая монета легче?
0
Извините, в вашем решении так и не понял, как вы за одно взвешивание выделили целевую кучку из трех?
0
Раньше думал, эта задача имеет единственное решение. Теперь появилась новая задача — сколько решений имеет эта задача?
0
DEL
0
На самом деле выше я пропустил две ветви в самом конце решения. Вот тут полное дерево:
Решение
Как найти фальшивую монетку и определить легче она или тяжелее.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
монеты пронумерованы от 1 до 12, подчеркнутые номера — заведомо настоящие монеты по результатам предыдущих взвешиваний, CF — counterfeit, L — is lighter, H — is heavier. На линиях результат взвешивания и известная на данный момент информация.
0
Ну допустим я злоумышленник и подложил «облегчённую» монету №7 где для неё вариант?
И тут вообще только 16 вариантов из 24 (12* L-H) возможных.
Или я что-то упустил?
И тут вообще только 16 вариантов из 24 (12* L-H) возможных.
Или я что-то упустил?
0
Похоже что упустили. Если 7 (или 5, 6 или 8) монета легче сработает блок "… swap 1234 with 5678". Алгоритм то один и тот же на самом деле, я решил сэкономить место и не расписывать оба варианта. Просто поменяйте кучки 1234 и 5678 местами и продолжайте, теперь легкая монета будет иметь индекс 3. Прошу прощения за неочевидность.
0
Ок да, разобрался. Странноватый алгоритм, кажется что можно проще. Интересно, сколько вообще существует алгоритмов решения данной задачи?
0
Я пока знаю только одно решение, мое. Решение автора я не считаю решением первоначальной задачи, так как оно не отвечает на вопрос легче или тяжелее?
Вы знаете другие решения? Поделитесь?
Вы знаете другие решения? Поделитесь?
0
Решение автора отвечает на вопрос "легче или тяжелее" на втором-третьем взвешивании, в зависимости от результатов взвешивания. Единственное исключение — когда после первого взвешивания, фальшивая монета оказывается в третьей группе, и в последующие 2 взвешивания она не попадает. Тогда да, ее вес неизвестен.
0
Три, как минимум -> mathforum.org/library/drmath/view/55618.html. Мне второе больше всех нравится, хотя (во всех) коряво то, что монеты по условию выглядят одинаково, а если их пронумеровать, то выглядеть одинаково они перестанут.
0
Вместо сравнения 1 2 5 6 vs 4 8 11 12 достаточно сравнить 5 6 12 vs 4 7 8. И «тройки» сравнивать чуть легче, чем «четвёрки», и «лёгкость» фальшивой монеты более однородно по случаям распределится. У Вас в каждом из трёх случаев она может быть как легче, так и тяжелее нормальной. А в данном варианте в случае "=" монета всегда H, при сохранении неравенства ">" монета всегда L, и только при смене неравенства на "<" будут смешанные варианты.
0
Если не ошибаюсь, где-то во второй половине девяностых, целое семейство задач про монеты, с их подробным разбором было опубликовано в журнале Компьютерра. Я, тогда ещё школьник, здорово помучился, пока не сообразил, что, взвешивая две из трёх частей, мы не только сужаем количество монет, среди которых фальшивая, но и получаем гарантированно «настоящие» эталоны, которые можно использовать в последующих взвешиваниях.
+2
А почему нельзя так?
1 взвешивание 6vs6
2 взвешивание 3vs3
3 взвешивание 1vs1 и если равны то оставшаяся?
1 взвешивание 6vs6
2 взвешивание 3vs3
3 взвешивание 1vs1 и если равны то оставшаяся?
0
Потому что неизвестно, является ли фальшивая монета легче или тяжелее настоящей. Вы взвешиваете 6 vs 6 и одна группа монет тяжелее другой. Но что это значит? В тяжёлой группе есть тяжёлая фальшивая монета или же в лёгкой группе — лёгкая фальшивая монета? Ноль полезной информации.
0
UFO just landed and posted this here
2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».
Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:
- Равны. Фальшивая монета находится среди чисел: 6 7 8.
А двенадцатая монета куда подевалась?
0
UFO just landed and posted this here
Поставило в тупик «3 взвешивания» а в решении приводится далеко не 3!
0
UFO just landed and posted this here
Sign up to leave a comment.
Декомпозиция и понижение энтропии для программиста на примере головоломки «12 монет, 3 взвешивания найти фальшивую»