Меню

Найдите фальшивую монету уровень



Решение задач на определение фальшивой монеты взвешиванием 2.0

Сегодня я снова хочу вернуться к теме о задаче нахождении фальшивой монеты методом взвешивания на весах без циферблата.

Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:

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 — остаток.

По условию задачи

При первом взвешивании будут сравниваться две группы: правая (ПГ) — 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
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
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 — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.

Источник

Найдите фальшивую монету уровень

Если же одна из чаш весит больше другой, то возьмем ее и разобьем на две кучки по 25 монет. Если они весят одинаково, то фальшивая монета была на другой чаше, значит, фальшивая легче. Если же одна из чаш перевесит, то фальшивая монета была в этих 50, т.е. фальшивая тяжелее.

Покажем, что если в обоих взвешиваниях одна из чаш перевешивала, то за оставшееся взвешивание можно установить фальшивые монеты. Действительно, тяжелая монета не может лежать на легкой чашке, а легкая на тяжелой. Также тяжелая и легкая монеты не могли участвовать в одном взвешивании. Значит, в одном взвешивании участвовали тяжелая и настоящая, а в другом — настоящая и легкая. Т.е. оставшаяся монета настоящая. Остается сравнить ее с монетой с тяжелой чаши, например, в первом взвешивании.

Читайте также:  Монета 20 центов гонконг 1980

Очевидно, в обоих взвешиваниях чаши не могли находиться в равновесии.

Если же в одном из взвешиваний чаши находились в равновесии, то на ней лежали две настоящие монеты. Теперь взвесим настоящую и оставшуюся. Мы можем узнать тип этой монеты. А далее узнаем тип монет на чашах, находившихся в одном из первых двух взвешиваний не в равновесии.

У нас осталось 94 − 32=62 взвешивания.

Теперь возьмем все «легкие» монеты. Покажем, как за 31 взвешивание определить среди них самую легкую монету. Сначала положим на каждую чашу по монете. А далее будем повторять следующую операцию: после взвешивания будем убирать тяжелую монету, и класть вместо нее любую монету, которая еще не участвовала во взвешиваниях. Ясно, что всего будет проведено 31 взвешивание. А монета, которая останется на весах и будет самой легкой.

Аналогично за 31 взвешивание определим самую тяжелую монету.

Источник

Задача родом из СССР про фальшивые монеты, которую давали на собеседовании в МГУ

Задача не нова и хорошо пережевана во многих книгах ещё с советских времен. Кто-то наверняка вспомнит, что решал её ещё в 60-70-ых годах. Но от этого она не становится хуже или проще. Наоборот, раз она так долго рассказывается ученикам учителями, значит, хорошая, заставляет подумать.

Эту задачу любили раньше давать на собеседованиях в МГУ. Когда не было ЕГЭ, были внутренние экзамены, олимпиады, а потом собеседование. Там могли спросить что угодно: просто поболтать, проверить эрудицию в других областях, а не по специальности, спросить про родителей или дать какую-то несложную задачку на логику. Как правило, строго решения никто не требовал, достаточно было сказать идею и все всё и так понимали. Так что не думайте, что это сложная задача.

Имеется 10 мешков с большим количеством монет в каждом. В 9 мешках все монеты настоящие, а в одном — все фальшивые. Настоящая монета весит 10 граммов, а фальшивая — 9 граммов. В вашем распоряжении есть электронные весы с точностью до граммов, но воспользоваться ими можно всего один раз. Как определить мешок с фальшивками?

Как я уже сказал, ничего сложного в задаче нет. Но сначала лирическое отступление.

ЛитРес дарит мне, а я дарю вам промокод YELLOWDZEN. В течение двух дней после активации на весь каталог у вас будет действовать 25% скидка. А вообще промокод работает до 4 марта 2021 года. Пользуйтесь, покупайте в подарок книги на 23 февраля и 8 марта.

Ну а теперь решение. Пронумеруем мешки от одного до 10. Берем из первого мешка одну монету, из второго — две, из третьего — три и так далее. Всего у нас получится 55 монет. Если бы они все были настоящими, они бы весили 550 граммов. Но так как среди них есть фальшивые, общей вес будет меньше. Так вот на сколько граммов будет меньше вес, в том мешке и есть фальшивые монеты.

Показываю на примере. Допустим фальшивые монеты в четвертом мешке. Из него мы по приницпу, описанному выше, возьмем 4 монеты. Они будет весит не 40 граммов, а всего 36. В итоге общая сумма у нас получится 10·(1+2+3+5+6+7+8+9+10) + 9·4 = 546. 550 — 546 = 4. Вот и вся задачка.

Обычно на словах «пронумеруем мешки и возьмем из каждого столько монет, какой у него порядковый номер. » абитуриента останавливали, всем становилось понятно, что он понял, как решать. А вы решили? Этим способом или нашли какой-то другой?

Источник

Решение задач на определение фальшивой монеты взвешиванием

Искал на днях ТЗ для углубления знаний по программированию и наткнулся на одном сайте на задачу о взвешиваниях монет для выявления фальшивой.

У этой задачи есть несколько разновидностей:
1) определить число взвешиваний для выявления фальшивой монеты (она легче или тяжелее)
2) определить алгоритм взвешивания
3) определение тяжелее или легче фальшивая монета
ну и компоновки разновидностей.

Можно было погуглить, но чем-то она меня зацепила, и после нескольких часов ночного осмысливания результатов удалось получить следующее:

1. Определяем количество взвешиваний
  • из 3 монет фальшивую можно определить за одно взвешивание (она будет либо одна из взвешиваемых, либо в остатке)
  • из 9 монет можно определить за 2 взвешивания
  • из 27 — за 3 взвешивания, и т. д.

Итого чтобы определить количество взвешиваний — n для A — количества монет, необходимо выполнение условия:
3 n >= A, или logA / log3 (n — 1)

если искомое число четное
B = A — 3 (n — 1) + 1

и вторая группа

3) группу B — делим по полам на две группы (левая группа — ЛГ, правая группа ПГ). У нас получится три группы

Читайте также:  Изображение евро монет всех стран

4) Группы ЛГ, ПГ — взвешиваем и определяем группу с фальшивой монетой (D). Возможны 3 варианта:
а) левая группа (ЛГ) монет на весах тяжелее/легче (D = ЛГ)
б) правая группа (ПГ) монет на весах тяжелее/легче (D = ПГ)
в) группы монет на весах одинаковые, тогда фальшивая монета в остатке (D = C).

5) Для группы, найденной в п.4 повторяем пп 1- 4 (A = D), пока количество монет больше 2 ( A > 2)

6) если осталось 2 монеты, выполняем последнее взвешивание (ЛГ = 1 и ПГ = 1)

7) фальшивая монета найдена.

Рассмотрим для наглядности задачу, пусть она будет с того же сайта: нужно разделить 12 монет за 3 взвешивания, фальшивая монета — легче.
1) количество взвешиваний
log12/log3 = 2.261
n = 3 (ну что же, задача решение имеет)
2) делим на группы
B = 12 — 3 (3 — 1) + 1 = 4
C = 12 — 4 = 8
3) группу B делим пополам:
ЛГ = 2, ПГ = 2, остаток C = 8

4) Взвешиваем ЛГ и ПГ.

Варианты после 1-го взвешивания
а) ЛГ = 2 — с фальшивой монетой (переходим к п. 6)
б) ПГ = 2 — с фальшивой монетой (переходим к п. 6)
в) остаток (C=8) — с фальшивой монетой. повторяем пп.1-4 для 8-ми монет
A=8
1) количество взвешиваний
log8/log3 = 1.893
n = 2
2) делим на группы
B = 8 — 3 (2 — 1) + 1 = 6
C = 8 — 6 = 2
3) группу B делим пополам:
ЛГ = 3, ПГ = 3, остаток C = 2

Варианты после 2-го взвешивания
а) ЛГ = 3 — с фальшивой монетой (повторяем пп.1-4 для 3-ми монет A=3)
б) ПГ = 3 — с фальшивой монетой (повторяем пп.1-4 для 3-ми монет A=3)
в) остаток (C=2) — с фальшивой монетой. переходим к п. 6)

Ну и 3-е взвешивание — из 2-х или 3-х монет определить фальшивую, причем для 3-х монет правило тоже сработает.

Еще пример для 25-ти монет
1) n = 2.93 = 3
2) B = 25 — 3 (3 — 1) = 16
C = 25 — 16 = 9
3) ЛГ = 8, ПГ = 8, С = 9
Варианты после 1-го взвешивания
а) D = ЛГ = 8
б) D = ПГ = 8
в) D = C = 9
Взвешивание 8-ми монет показано в предыдущем примере (ну так выгодно случайно совпало), покажу для 9-ти.
A = 9
1) n = 2
2) B = 9 — 3 (2 — 1) = 6
C = 9 — 6 = 3
3) ЛГ = 3, ПГ = 3, С = 3
ну и еще 2 взвешивания ( для определения группы и для определения монеты).

Источник

Простая задача о взвешивании монет

Задача

Хорошо известна задача о взвешивании монет на простых рычажных весах, с целью найти одну фальшивую монету за минимальное число взвешиваний.

Например, у Вас имеется 100 одинаковых по виду монет. Все они одинакового веса, кроме одной фальшивой монеты, которая легче остальных монет. Спрашивается, за какое минимальное число взвешиваний на рычажных весах можно найти фальшивую монету.

Алгоритм

Алгоритм решения этой задачи довольно простой. Берем ближайшее большее число к 100, которое делится на 3. Это число 102. Делим 102 на 3, получаем 34. На обе чаши весов кладем по 34 монеты, а 32 монеты оставляем лежать на столе.

Если чаши весов уравновешены, значит, на нах находятся только настоящие монеты, а фальшивая монета среди 32 монеты, которые остались на столе. В этом случае работаем только с этими 32 монетами. А если какая-то из чаш весов с 34 монетами оказалась легче другой чаши, то работаем далее с теми 34 монетами, где находится более легкая монета.

И далее повторяем весь алгоритм заново. То есть, если число монет не делится на 3, то находим ближайшее целое число, которое превышает число монет и которое делится без остатка на три. Делим это число на 3, чтобы получить, сколько монет нужно положить на обе чаши весов. А оставшиеся монеты оставляем лежать на столе. Это число монет всегда меньше или равно числу монет на одной из чаш весов. Проводим взвешивание, чтобы определить, с какой из этих трех групп монет работать дальше.

Допустим, у нас обе чаши весов с 34 монетами уравновешены. Значит, работаем с оставшимися на столе 32 монетами. Ближайшее большее число, которое делится на 3, будет 33. Делим 33 на 3 и получаем, что на обе чаши весов надо положить по 11 монет, а 10 монет оставить на столе.

А если легче оказалась чаша весов с 34 монетами, то ближайшее большее целое, которое делится на 3, будет 36. Поэтому берем из этой легкой кучи из 34 монет по 12 монет на каждую чашу весов, а 10 монет оставляем лежать на столе.

Разное число минимальных взвешиваний

Перебирая таким алгоритмом все возможные варианты, мы получаем, что надо сделать или 4 или 5 взвешиваний. Какое именно число взвешиваний надо будет сделать, 4 или 5, это уж как повезет.

Например, как получается 4 взвешивания. Если после второго взвешивания нам придется работать с 10 монетами, которые при втором взвешивании оставались на столе, то в третьем взвешивании кладем на обе чаши весов по 4 монеты. Две монеты оставляем на столе. Если в третьем взвешивании чаши весов уравновешены, то остается сделать только одно четвертое взвешивание, поместив на каждую чашу весов по одной монете из двух оставшихся на столе монет.

Читайте также:  Не монета чтобы всем нравится

А если на третьем взвешивании нам не повезет, и, допустим, дальше надо будет работать не с 2 монетами, а с 4 монетами, то 4 взвешиваний уже не хватит. На 4-м взвешивании мы кладем на обе чаши весов по 2 монеты, а на столе ничего не остается. И затем делаем 5-е взвешивание с чашами весов по одной монете.

Можете сами проверить другие разветвления после второго взвешивания, когда придется работать не с 10 монетами, а с 11 или с 12 монетами, что данный алгоритм дает максимум 5 взвешиваний, но если повезёт, то и 4 взвешивания.

Одно число минимальных взвешиваний

А бывает ли так, чтобы число взвешиваний по данному алгоритму было бы строго определенным числом и не зависело бы от везения?

Да, такое бывает, когда каждый раз на столе остается столько же монет, сколько и на каждой чаши весов. Это бывает тогда, когда на каждом взвешивании число монет всё время делится на 3 без остатка. То есть, начальное число монет должно быть равным степени числа 3. Это числа

Степень тройки показывает, сколько взвешиваний нужно сделать.

Например, число 27, это 3 в 3-й степени (3 3 =27). Значит, найти фальшивую монету среди 27 монет можно за 3 взвешивания. На первом взвешивании кладем на обе чаши весов по 9 монет и еще 9 монет оставляем на столе. На втором взвешивании 9 монет делим на три кучки по 3 монеты, и кладем на обе чаши весов по 3 монеты и еще 3 монеты оставляем на столе. И, наконец, на последнем третьем взвешивании по одной монете кладем на обе чаши весов и одну монету оставляем на столе.

Нетрудно проверить, что для 27 монет взвешиваний всегда будет 3, где бы случайно не оказалась фальшивая монета на каждом взвешивании, на одной из чаш весов или на столе.

Общее правило

Общее правило определения числа минимальных взвешиваний следующее. Если дано N монет, среди которых одна монета отличается по весу, и это число N не является степенью числа 3, то надо найти ближайшие к N два числа, которые являются степенями числа 3. Показатели степеней числа 3 для этих двух чисел и будут равны числу минимальных взвешиваний. Если N точно является степенью числа 3, то показатель степени числа 3, будет одним минимальным числом взвешиваний.

В нашем примере N=100. Данное число не является степенью числа 3. Значит, ищем ближайшие к 100 степени числа 3. Это числа 81 и 243. При этом 3 4 =81 и 3 5 =243. Значит, числа 4 и 5 являются минимальным числом взвешиваний для поиска фальшивой монеты среди 100 монет.

Если число монет 59’049, то это число является точной степенью числа 3, а именно: 3 10 =59049. Значит, для поиска фальшивой монеты среди 59’049 монет нужно будет сделать точно 10 взвешиваний.

Понятно, что это правило и этот же алгоритм будут работать, если фальшивая монета не легче настоящей, а тяжелее её. Но в общем случае нужно обязательно заранее знать, какая из монет тяжелее, настоящая или фальшивая, чтобы правильно определять, с какой группой монет работать на следующем взвешивании.

Сложная задача о взвешивании монет

Это была очень простая задача о взвешивании монет. А как Вам теперь такая задача.

Имеется N мешков с монетами. Все монеты на вид не отличаются друг от друга. В каждом мешке находятся монеты только одного какого-нибудь вида, или настоящие монеты или какой-нибудь один сорт фальшивых монет. Известно, сколько весит каждый сорт монет, то есть известен вес настоящей монеты и веса всех сортов фальшивых монет. Неизвестно в каких именно мешках находятся настоящие монеты, а в каких мешках находятся фальшивые монеты.

Вопрос: Как ОДНИМ взвешиванием определить, в каких мешках находятся настоящие монеты, а в каких мешках находятся какие сорта фальшивых монет? Весы обычные, которые показывают вес, например, в граммах.

Считается, что в мешках достаточное количество монет, чтобы брать оттуда любое количество монет.

Обратите внимание, что фальшивые монеты не обязательно должны быть легче, чем настоящие. Например, может быть, что всего 7 сортов монет со следующими весами в граммах: 4, 5, 8, 9, 10, 13 и 16. Настоящая монета имеет вес 10 грамм, а все остальные фальшивые. Кроме того, у нас не обязаны все 7 сортов этих монет присутствовать. Может быть такая ситуация, что во всех N мешках находятся только одни настоящие монеты, или во всех N мешках находятся только фальшивые монеты с весом 9 грамм. Или могут быть любые более сложные ситуации, когда часть мешков занята одним сортом монет, часть мешков другим сортом монет и т.д. И нам неизвестно в каком порядке чередуются в этих мешках эти монеты.

На первый взгляд, эта задача кажется не имеющая решения. И, тем не менее, за одно взвешивание можно определить всё распределение всех сортов монет по всем мешкам.

Решение этой красивой задачи смотрите здесь.

Источник