Комментарии 13
из 3 монет фальшивую можно определить за одно взвешивание (она будет либо одна из взвешиваемых, либо в остатке)
А если неизвестно, легче или тяжелее монета?
—
UPD
Не совсем понятно, но похоже в статье имеется ввиду, что заранее известно, что фальшивая монета строго тяжелее (или строго легче). Тогда, имхо, не очень интересная задача.
Вот в каждой группе найдется такой человек… :)
Для того чтобы не возникало такого вопроса полезно вспомнить историю:
Монеты чеканились из драг. металлов (в основном золото)
Фальшивые монеты содержали меньше золота чем настоящие и в них добавлялись другие металлы для того чтобы обьем был тот же. Соответственно фальшивые монеты всегда были легче т.к. в качестве примеси использовался металл легче золота.
Монеты чеканились из драг. металлов (в основном золото)
Фальшивые монеты содержали меньше золота чем настоящие и в них добавлялись другие металлы для того чтобы обьем был тот же. Соответственно фальшивые монеты всегда были легче т.к. в качестве примеси использовался металл легче золота.
Да, известно, что монета легче/тяжелее.
Да! Сказал бы я месяц тому, пока меня дочка не попросила помочь с подготовкой к конкурсу по математике («Кенгуру» — юниор). Пришлось объяснять.
Тогда, имхо, не очень интересная задача
Да! Сказал бы я месяц тому, пока меня дочка не попросила помочь с подготовкой к конкурсу по математике («Кенгуру» — юниор). Пришлось объяснять.
Интересно, что на шагах 2-3 может получаться очень неравномерное разбиение, при этом алгоритм совершенно правильный. 82 монеты, например, разбиваются на (1, 1, 80). Если бы я решал конкретную задачу, мне бы в голову не пришло разбивать вначале таким образом.
Придирка по мелочи:
Проверка п.1 избыточна, он же в силу способа разбиения автоматически будет выполняться.
Придирка по мелочи:
5) Для группы, найденной в п.4 повторяем пп 1- 4 (A = D), пока количество монет больше 2 ( A > 2)
Проверка п.1 избыточна, он же в силу способа разбиения автоматически будет выполняться.
Интересно, что на шагах 2-3 может получаться очень неравномерное разбиение, при этом алгоритм совершенно правильный
Да, разбиение будет неравномерное, но согласитесь, если положить алгоритм на какой-нибудь язык программирования, то его проще реализовать, нежели учить железяку мыслить логически-рационально.
Мне кажется, что в пункте 1 у вас отсутствует доказательство. Просто приводится некоторая формула, в которую мы должны поверить просто в силу того, что она выполняется для A=3 и A=9.
Всё-таки строгое доказательство должно включать в себя доказательство «необходимости» и «достаточности» приведенного вами n.
«Достаточность» доказывается довольно просто приведением вполне конкретного описанного вами алгоритма (последовательное деление на 3 части). А вот «необходимость» доказать, видимо, сложнее. Почему вы так уверены, что не существует более оптимального алгоритма, по которому, например, для 10^100 монет миллиона взвешиваний будет достаточно?
Всё-таки строгое доказательство должно включать в себя доказательство «необходимости» и «достаточности» приведенного вами n.
«Достаточность» доказывается довольно просто приведением вполне конкретного описанного вами алгоритма (последовательное деление на 3 части). А вот «необходимость» доказать, видимо, сложнее. Почему вы так уверены, что не существует более оптимального алгоритма, по которому, например, для 10^100 монет миллиона взвешиваний будет достаточно?
Мне кажется, что в пункте 1 у вас отсутствует доказательство. Просто приводится некоторая формула, в которую мы должны поверить просто в силу того, что она выполняется для A=3 и A=9
Просто я взял по разложил числа от 27 до 3 (читайте — взвешивал монеты от 27 шт. до 3 шт.) и увидел некоторую закономерность, которую потом реализовал в виде алгоритма. Я пришел от практики к теории (так многие делают).
А вот «необходимость» доказать, видимо, сложнее. Почему вы так уверены, что не существует более оптимального алгоритма, по которому, например, для 10^100 монет миллиона взвешиваний будет достаточно?
А вот в этом я вовсе уверен. Просто предоставляю для свободного использования еще один алгоритм, а пользоваться им или нет — дело добровольное.
Почему вы так уверены, что не существует более оптимального алгоритма, по которому, например, для 10^100 монет миллиона взвешиваний будет достаточно?
1. Ну вообще-то следуя алгоритму, то для выявления одной фальшивой из 10^100 монет необходимо —
log(10^100) / log3 = 209,59
— максимум 210 взвешиваний. Но это не означает, что придется выполнять все взвешивания. Ведь может сложиться ситуация, когда на каком-нибудь 146 шаге группы монет на весах с сравняются, а в остатке будете одна, которая фальшивая (но это уже очень глубокие материи: "… если бы, да кабы").
2. Я бы не назвал оптимальным алгоритм, который решает эту же задачу за
миллион взвешиваний, если можно обойтись 210.
Или я неправильно вопрос понял?
Наверняка есть алгоритмы оптимальнее предоставленного, мне про то, увы, неизвестно. Если есть ссылки — поделитесь
Не хватает пояснений математики. Т.е. откуда именно
Итого чтобы определить количество взвешиваний — n для A — количества монет, необходимо выполнение условия:
3n >= A, или logA / log3 <= n,
Вот очень интересная задача — найти фальшивую монету среди 13 монет за три взвешивания. Если не знаешь, тяжелее она или легче.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение задач на определение фальшивой монеты взвешиванием