Время на прочтение
3 мин
Количество просмотров 204K
Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.
Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:
1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.
Или обратная задача: можно ли за определенное количество взвешиваний выявить фальшивую из заданного количества монет.
1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.
Некоторое время назад, я на Хабре уже описывал решение такой задачи, но в одном из комментариев было замечание о немного странном первом разделении монет, по-этому предлагаю другой алгоритм решения. Хотя результат будет тот же и формула решения задачи остается та же:
N >= log3A,
где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
A — количество монет.
Которая выведена на основании опытов (за 1 взвешивание можно найти одну фальшивую из 3-х монет, за 2 — из 9, за 3 — из 27 и т.д.)
Сам алгоритм решения простой, и я покажу его на примерах
1) Пусть у нас есть 26 монет. Нужно найти одну, которая легче/тяжелее
Первым действием буде разделение монет на три группы, в двух из которых число монет будет одинаковым, важно только что бы в третьей группе — остатке — было меньше монет, чем в каждой из двух других групп. То есть частое округляется к большему натуральному числу. То есть
A = 2 * B + C,
где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в большую сторону;
C — остаток.
По условию задачи
26/3 = 8.666(6),
26 = 2 * 9 + 8,
При первом взвешивании будут сравниваться две группы: правая (ПГ) — 9 монет и левая (ЛГ) — 9 монет.
Далее у нас возможны два варианта:
1) фальшивая монета в левой/правой группе (9 монет)
2) фальшивая монета в остатке (8 монет)
для 1 варианта следующее деление на группы будет — 9 = 2 * 3 + 3;
для 2 варианта — 8 = 2 * 3 + 2
Ну и за одно взвешивание можно определить какая из 2 или 3 монет легче/тяжелее
Этот же результат я приведу в таблице
| № взвешивания | Число монет | ЛГ | ПГ | Остаток |
| 1 | 26 | 9 | 9 | 8 |
| 2 | 8 | 3 | 3 | 2 |
| 2 | 9 | 3 | 3 | 3 |
| 3 | 2 | 1 | 1 | 0 |
| 3 | 3 | 1 | 1 | 1 |
по формуле — log326 =2.9656 — соответственно количество взвешиваний — 3.
еще пример:
число монет- 71. По формуле log371 =3.8800 — количество взвешиваний — 4. Проверяем
| № взвешивания | Число монет | ЛГ | ПГ | Остаток |
| 1 | 71 | 24 | 24 | 23 |
| 2 | 23 | 8 | 8 | 7 |
| 2 | 24 | 8 | 8 | 8 |
| 3 | 7 | 3 | 3 | 1 |
| 3 | 8 | 3 | 3 | 2 |
| 4 | 2 | 1 | 1 | 0 |
| 4 | 3 | 1 | 1 | 1 |
Ну с алгоритм решения этих задач, я думаю, понятен.
2. Теперь перейдем к задачам, в которых не известно легче монета или тяжелее.
В данном случае я предлагаю такое первое действие: разделить монеты на четыре группы, три — с максимально одинаковым количеством монет, а в четвертой группе — остаток. Причем в остатке должны быть 1 или 2 монеты. То есть при делении на 3 частное округляется до меньшего натурального числа.
A = 3 * B + C,
где A — количество монет;
B — частное от деления количества монет на 3, натуральное число, округленное в меньшую сторону;
C — остаток.
Например, для 58-ми монет — это будет 58 = 3 * 19 + 1, для 23 = 3 * 7 + 2, для 15 = 3 * 5 + 0 и т. д.
Далее выполняем два взвешивания:
1) первая и вторая группы;
2) первая и третья группы;
и анализируем результат.
Здесь возможны четыре варианта:1, 2, 3 — это первая, вторая или третья группа отличаются по весу от двух остальных, или они равны, тогда нам повезло, так как фальшивая — в остатке. Так же два взвешивания помогают определить определить тяжелее фальшивая монета или легче. Кстати, если в остатке две монеты, то нужно выполнить еще 2 взвешивания для определения фальшивой монеты.
Теперь у нас есть задача: определить одну фальшивую монету из группы, которая легче/тяжелее.
Что касается формулы, то она примет следующий вид
N >= log3B + 2,
где N — максимально необходимое количество взвешиваний, натуральное число;
B — количество монет в группе после второго взвешивания.
А если учесть, что B = A/3, где A — количество всех монет, тогда получим:
log3B = log3A — 1,
N >= log3A + 1
Итог:
1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:
N >= log3A
2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:
N >= log3A + 1
где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.
Как найти фальшивую монету двумя взвешиваниями — логическая задача
Загадки на логику
Перед нами логическая задача, чтобы решить которую нужно немного пораскинуть мозгами.
Итак условия задачи следующие:
На столе лежат 9 монет. Известно, что одна из монет фальшивая. Фальшивая монета весит меньше чем остальные. У нас имеются весы для взвешивания.
Вопрос:
Как при помощи двух взвешиваний найти фальшивую монету?
.jpg)
Внимание!
Ниже приведен правильный ответ!
Правильный ответ:
Вначале на каждую чашу весов нужно положить по три монеты.
Если после этого весы приходят в равновесие, значит среди этих монет нет фальшивой, берем две из трех оставшихся монет, кладем на разные чаши весов. Если фальшивая монета среди этих двух, то мы поймем на какой она чаше, эта чаша поднимется выше.
А если весы снова придут в равновесие, значит фальшивая монета осталась на столе.
Если же при первом взвешивании весы не пришли в состояние равновесия, значит фальшивая монета уже находится на весах, берем 2 монеты из тех трех, что оказались легче, кладем по 1 на каждую чашу, если одна чаша поднялась выше, значит фальшивая монета на ней, если чаши уравновесились, значит фальшивая — оставшаяся третья.
Похожие новости
Все загадки
Все загадки
Все загадки
Все загадки
Все загадки
Все загадки
Задача имеет решение, но оно будет актуально только для весов с достаточно вместительной чашей для взвешивания.
Из каждого следующего мешочка с монетами необходимо взять на одну монету больше, чем из предыдущего.
- из первого мешочка одна монета
- из второго мешочка две монеты
- из третьего мешочка три монеты
- из четвертого мешочка четыре монеты
- из пятого 5 монет
- из шестого 6 монет
- из седьмого 7 монет
- из восьмого 8 монет
- из девятого 9 монет
- из десятого десять монет
Итого у нас будет: 1+2+3+4+5+6+7+8+9=45 монет
Выкладываем их, не смешивая между собой, на чашу весов. Полученный вес в граммах сообщит нам в каком мешочке лежали фальшивые монеты. Если бы все монеты являлись настоящими, то на весах у нас должно было быть 45*10=450 грамм, любое отклонение в граммах укажет нам номер мешочка с фальшивками.
- 449 грамм — фальшивые монеты в первом мешочке
- 448 грамм — фальшивые монеты во втором мешочке
- 447 грамм -фальшивые монеты в третьем мешочке
- 446 грамм — фальшивые монеты в четвертом мешочке
- 445 грамм — фальшивые монеты в пятом мешочке
- 444 грамм — фальшивые монеты в шестом мешочке
- 443 грамма — фальшивые монеты в седьмом мешочке
- 442 грамма — фальшивые монеты в восьмом мешочке
- 441 грамм — фальшивые монеты в девятом мешочке
- 440 грамм — фальшивки в десятом мешочке
Универсальная методика к решению задач на примере головоломки «12 монет, 3 взвешивания» +23
Алгоритмы, Мозг, Занимательные задачки
Рекомендация: подборка платных и бесплатных курсов Java — https://katalog-kursov.ru/
Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку.
Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.
Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым.
Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?
Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».
Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.
1. Подсказки
В процессе решения поможет:
1) Понижение энтропии (меры неопределенности) и ответы на вопросы:
- Что узнали на предыдущем шаге?
- Что снижает неопределённость?
- Какой информацией располагаем?
- Что еще нужно узнать?
Вопросы подходят для любой задачи, проектов. Ответы на них помогают в снижении рисков срыва сроков, перерасхода бюджета и получения нагоняя от начальства.
2) Декомпозиция. Подход от простого к сложному. Если подготовить решение простейших случаев, затем использовать их для решения задачи (алгоритм разделяй и властвуй) то, будет проще, чем представлять всю ситуацию в голове.
Алгоритмы «разделяй и властвуй» разбивают задачу на две или более подзадачи того же типа, но меньшего размера до элементарных задач и объединяют их решения для получения ответа к исходной задаче.
Составьте вопросы для декомпозиции. Какие бы вы предложили?
2. Декомпозиция
Какие вопросы вы сформулировали для декомпозиции? Есть совпадения?
1) Какая ситуация самая элементарная? Что можем сделать за одно взвешивание?
За одно взвешивание можем определить, какая монета тяжелее, равен ли вес монет.
2) Если у нас 2 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо взвесить монеты, и в зависимости от стрелки весов определить фальшивую.
3) Если у нас 2 монеты, и, не известно, фальшивая тяжелее или легче, как за одно взвешивание определить фальшивую?
Взвесив одну из 2-х представленных монет с третьей монетой, про которую известно, что она подлинная.
4) Если у нас 3 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо сравнить любые две из этих монет, если они равны, фальшивой является третья монета.
5) Если у нас 3 монеты, и, неизвестно, фальшивая тяжелее или легче. Можно ли определить фальшивую за одно взвешивание?
К сожалению, нет.
6) Если у нас 4 монеты, и, неизвестно фальшивая тяжелее или легче, можно определить фальшивую за одно взвешивание?
К сожалению, нет.
7) Если у нас 4 монеты, и, неизвестно, фальшивая тяжелее или легче, за сколько взвешиваний можно определить фальшивую?
За два взвешивания.
Далее из элементарных случаев соберем ситуации из 8, 9, 10, 11 и 12 монет. Как вы видите решение?
Ниже полное решение.
3. Решение
Первый шаг: разделим монеты на 3 группы по 4: 1 2 3 4, 5 6 7 8, 9 10 11 12.
Сравним первые две группы. Возможны три варианта:
- первая группа тяжелее;
- вторая группа тяжелее;
- равны.
1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.
Делим третью группу на две: 9 10 11 12
Сравниваем 9 и 10:
- если они равны, то фальшивая монета во второй группе – сравниваем 9 и 11. Если 9 и 11 равны — то фальшивая – 12, если нет -11
- если они не равны, то фальшивая в первой группе – сравниваем 10 и 12. Если 10 и 12 равны – фальшивая – 9, если нет – 10.
Таким образом мы нашли фальшивую монету.
2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак «<», третьей группе – «0».
Делим монеты на группы 1 9 10 11 и 5 2 3 4, взвешиваем. Возможны три варианта:
- Равны. Фальшивая монета находится среди чисел: 6 7 8. Сравниваем 6 и 7, если равны – фальшивая — 8, если 6 больше, то фальшивая – 7, если 7 больше, то фальшивая – 6, так как в данном случае фальшивая монета легче.
- Первая группа тяжелее, то фальшивая монета либо 1, либо 5. Сравниваем 1 и 9, если они равны – фальшивая монета — 5, если нет — 1.
- Первая группа легче, то фальшивая среди монет 2 3 4, так как известно, что 9, 10 и 11 настоящие, и перевесить вторая группа может только за счет монет 2, 3 и 4. Сравниваем 2 и 3, если равны – фальшивая 4, если 2 тяжелее, то фальшивая – 2, иначе 3-я является фальшивой.
3) Случай когда вторая группа тяжелее первой, аналогичен второму.
Общая диаграмма «Дерева решений» представлена ниже.
Заключение
При поступлении задачи на доработку или отладку хорошо применить рассмотренный выше подход:
- Определиться, что дано?
- На какие элементарные случаизадачи можно разложить?
- Что неизвестно для решения задачи? Какие эксперименты нужно провести, чтобы снизить энтропию?
- Выполнить.
- Задача решена? Нет? Вернуться к шагу 1.
Успешных решений.
Как тремя взвешиваниями найти фальшивую монету
Это достаточно популярная логическая задачка. Есть двадцать одинаковых с виду монет, одна из которых фальшивая, и весы с чашками без гирь. Известно, что фальшивая монета весит меньше чем настоящая. Необходимо найти фальшивую монету за три взвешивания.
Вам понадобится
- — двадцать монет;
- — чашечные весы.
Инструкция
Разделите монеты на три части: в двух будет по семь монет, и в оставшейся – шесть. На чашечные весы положите две равные кучки. Если весы уравновешены, значит, в двух кучках по семь монет все монеты настоящие, а фальшивая находится среди оставшихся шести монет. Если же равновесие нарушилось, пропустите следующий пункт решения.
Возьмите кучку из шести монет, разделите ее на три части. В каждую чашку весов положите по 2 монеты, еще 2 оставьте. Это второе взвешивание. Если весы уравновешены, значит, фальшивая монета осталась среди двух, лежащих на столе. Если равновесие нарушилось, значит, фальшивая монета среди тех двух монеток, которые оказались легче. Таким образом, вы обнаружили пару монет, одна из которых фальшивая, и ее легко найти третьим взвешиванием, просто положив в каждую чашку весов по одной монете.
Возьмите ту часть из семи монет, которая оказалась легче. Напомним, что это вы делаете в том случае, если при первом взвешивании равновесие на весах нарушилось. Разделите монеты на три части: в двух будет по три монеты и в оставшейся – одна. В каждую чашку весов положите по три монеты. Это второе взвешивание. Если равновесие весов не нарушено, значит, оставшаяся монета и есть фальшивая. Задача решена даже быстрее благодаря везению! Если же одна чашка весов оказалась легче, проведите последнее взвешивание.
Положите в каждую чашку весов по одной монете из той части, которая оказалась легче. Третья монета останется лежать на столе. Если весы уравновешены, значит, оставшаяся монета и есть фальшивая. Если же одна из чашек весов легче, то фальшивая монета находится в ней.
Полезный совет
Вы можете столкнуться с разными вариантами подобной задачи: монет может быть сколько угодно, и определить фальшивую нужно будет за минимальное число взвешиваний. Хитрость решения состоит в том, что делить монеты нужно не на две, а на три части, так как уравновешивание чашек весов позволяет сделать определенный вывод не только о тех монетах, которые лежат на весах, но и о тех, которые остались на столе.
Источники:
- Логические задачи и головоломки
Войти на сайт
или
Забыли пароль?
Еще не зарегистрированы?
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.