Решение задач на определение фальшивой монеты взвешиванием
Искал на днях ТЗ для углубления знаний по программированию и наткнулся на одном сайте на задачу о взвешиваниях монет для выявления фальшивой.
У этой задачи есть несколько разновидностей:
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 взвешивания ( для определения группы и для определения монеты).
Источник
Нарисуйте блок — схему алгоритма поиска фальшивой монеты среди десяти монет?
Информатика | 10 — 11 классы
Нарисуйте блок — схему алгоритма поиска фальшивой монеты среди десяти монет.
В вашем распоряжении имеются лабораторные весы (с двумя чашечками) без гирь.
Известно, что фальшивая монета всего одна, и она легче настоящих.
Блок — схема в приложении.
Есть шесть монет, среди которых две фальшивые, которые легче настоящих(и имеют одинаковый вес)?
Есть шесть монет, среди которых две фальшивые, которые легче настоящих(и имеют одинаковый вес).
Как при помощи чашечных весов найти фальшивые монеты?
Постарайтесь обойтись при помощи наименьшего числа взвешиваний.
Есть 2014 одинаковых по виду монет и чашечные весы без гирек?
Есть 2014 одинаковых по виду монет и чашечные весы без гирек.
Среди монет есть одна фальшивая, которая по весу отличается от настоящей.
Предложите способ определите , легче или тяжелее фальшивая монета чем настоящая, за наименьшее число взвешивании.
Пожалуйста помогите решить»!
Имеется 1000 монет из которых одна фальшивая(легче других)?
Имеется 1000 монет из которых одна фальшивая(легче других).
Придумайте способ нахождения фальшивой монеты за 7 взвешиваний на чашечных весах без гирь.
В каждом из двух мешков с монетами находится по одной фальшивой монете для определения фальшивой монеты в первом мешке потребовалось 6 взвешиваний на чашечных весах без гирь, во втором — 4взвешивания?
В каждом из двух мешков с монетами находится по одной фальшивой монете для определения фальшивой монеты в первом мешке потребовалось 6 взвешиваний на чашечных весах без гирь, во втором — 4взвешивания.
Сколько настоящих монет в двух мешках.
Нарисуйте блок — схему алгоритма поиска фальшивой монеты среди десяти монет?
Нарисуйте блок — схему алгоритма поиска фальшивой монеты среди десяти монет.
В вашем распоряжении имеются лабораторные весы (с двумя чашечками) без гирь.
Известно, что фальшивая монета всего одна, и она легче настоящих.
Среди 32 монет — одна фальшивая (более легкая)?
Среди 32 монет — одна фальшивая (более легкая).
Укажите минимальное количество взвешиваний на двухчашечных весах без гирь, которое потребуется для поиска фальшивой монеты.
Помогите решить задачу на сообразительность : Есть 23 внешне одинаковые монеты : 20 настоящих и 3 фальшивые?
Помогите решить задачу на сообразительность : Есть 23 внешне одинаковые монеты : 20 настоящих и 3 фальшивые.
Как за два взвешивания на чашечных весах без гирь найти 7 заведомо настоящих монет?
Известно, что все настоящие монеты весят одинаково, все фальшивые также весят одинаково, но фальшивая монета легче настоящей.
Есть 2014 одинаковых по виду монет и чашечные весы без гирек среди монет есть одна фальшивая, которая по весу отличается от настоящей предложите способ определить легче или тяжелее фальшивая монета че?
Есть 2014 одинаковых по виду монет и чашечные весы без гирек среди монет есть одна фальшивая, которая по весу отличается от настоящей предложите способ определить легче или тяжелее фальшивая монета чем настоящая за наименьшее число взвешиваний.
Можете составить алгоритм в виде блок схем?
Можете составить алгоритм в виде блок схем.
Одна из них фальшивая , она легче настоящей (все настоящие весят одинаково).
Как за два взвешивания на чашечных весах без гарь найти фальшивую монету ?
Задача?
Среди четырех монет одна фальшивая.
Она отличается массой, однако неизвестно, легче она или тяжелее.
Масса настоящей монеты 5 г.
Как при помощи двух взвешиваний на чашечных весах обнаружить фальшивую монету, если имеется одна гиря массой 5 г?
Можно ли при этих условиях опознать, легче фальшивая монета или тяжелее?
Помогите пожалуйста напишите правильное решения этой задачи по действиям.
На этой странице находится вопрос Нарисуйте блок — схему алгоритма поиска фальшивой монеты среди десяти монет?, относящийся к категории Информатика. По уровню сложности данный вопрос соответствует знаниям учащихся 10 — 11 классов. Здесь вы найдете правильный ответ, сможете обсудить и сверить свой вариант ответа с мнениями пользователями сайта. С помощью автоматического поиска на этой же странице можно найти похожие вопросы и ответы на них в категории Информатика. Если ответы вызывают сомнение, сформулируйте вопрос иначе. Для этого нажмите кнопку вверху.
Источник
Найти фальшивую монету блок схема
Вопрос по информатике:
Нарисуйте блок-схему алгоритма поиска фальшивой монеты среди десяти монет. В вашем распоряжении имеются лабораторные весы (с двумя чашечками) без гирь. Известно, что фальшивая монета всего одна, и она легче настоящих.
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок — бесплатно!
Ответы и объяснения 1
Фотка во вложении.
Знаете ответ? Поделитесь им!
Как написать хороший ответ?
Чтобы добавить хороший ответ необходимо:
- Отвечать достоверно на те вопросы, на которые знаете правильный ответ;
- Писать подробно, чтобы ответ был исчерпывающий и не побуждал на дополнительные вопросы к нему;
- Писать без грамматических, орфографических и пунктуационных ошибок.
Этого делать не стоит:
- Копировать ответы со сторонних ресурсов. Хорошо ценятся уникальные и личные объяснения;
- Отвечать не по сути: «Подумай сам(а)», «Легкотня», «Не знаю» и так далее;
- Использовать мат — это неуважительно по отношению к пользователям;
- Писать в ВЕРХНЕМ РЕГИСТРЕ.
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи — смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.
Источник
Универсальная методика к решению задач на примере головоломки «12 монет, 3 взвешивания»
Дано: 12 монет, одна из них фальшивая, отличается только весом. Неизвестно легче или тяжелее. Даны рычажные весы, которые показывают, что груз с одной из сторон тяжелее. За 3 взвешивания необходимо найти фальшивую монетку.
Из опыта советую не спешить, решать письменно. Головоломка «12 монет, 3 взвешивания» несколько раз возникала в моей жизни. Первый раз ее задал мне мой товарищ-олимпиадник, решил я ее после олимпиады и пришлось пару часиков поломать голову. И через несколько лет она далось мне не сразу. Если желаете решить самим — делайте на листочке.
Ниже будет разбор и этапы решения. Этапы проведут по универсальной методике решения задач, которая применима как к программированию, так и к жизни. Благодаря подходу решение головоломки станет простым.
Предлагаю вам, прежде чем читать предложить решение. У вас есть ответ? Проверенный?
Если бы это было программного обеспечения вопросы были бы следующие: «Вы запрограммировали, протестировали алгоритм? Рассмотрели тестовые случаи и проверили их?».
Как показывает опыт, чтобы решить требуется нарисовать дерево решений и проверить все 12 случаев.
В процессе решения поможет:
1) Понижение энтропии (меры неопределенности) и ответы на вопросы:
- Что узнали на предыдущем шаге?
- Что снижает неопределённость?
- Какой информацией располагаем?
- Что еще нужно узнать?
Вопросы подходят для любой задачи, проектов. Ответы на них помогают в снижении рисков срыва сроков, перерасхода бюджета и получения нагоняя от начальства.
2) Декомпозиция. Подход от простого к сложному. Если подготовить решение простейших случаев, затем использовать их для решения задачи (алгоритм разделяй и властвуй) то, будет проще, чем представлять всю ситуацию в голове.
Алгоритмы «разделяй и властвуй» разбивают задачу на две или более подзадачи того же типа, но меньшего размера до элементарных задач и объединяют их решения для получения ответа к исходной задаче.
Составьте вопросы для декомпозиции. Какие бы вы предложили?
Какие вопросы вы сформулировали для декомпозиции? Есть совпадения?
1) Какая ситуация самая элементарная? Что можем сделать за одно взвешивание?
За одно взвешивание можем определить, какая монета тяжелее, равен ли вес монет.
2) Если у нас 2 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо взвесить монеты, и в зависимости от стрелки весов определить фальшивую.
3) Если у нас 2 монеты, и, не известно, фальшивая тяжелее или легче, как за одно взвешивание определить фальшивую?
Взвесив одну из 2-х представленных монет с третьей монетой, про которую известно, что она подлинная.
4) Если у нас 3 монеты, и, известно, фальшивая тяжелее или легче. Как за одно взвешивание определить фальшивую?
Необходимо сравнить любые две из этих монет, если они равны, фальшивой является третья монета.
5) Если у нас 3 монеты, и, неизвестно, фальшивая тяжелее или легче. Можно ли определить фальшивую за одно взвешивание?
К сожалению, нет.
6) Если у нас 4 монеты, и, неизвестно фальшивая тяжелее или легче, можно определить фальшивую за одно взвешивание?
К сожалению, нет.
7) Если у нас 4 монеты, и, неизвестно, фальшивая тяжелее или легче, за сколько взвешиваний можно определить фальшивую?
За два взвешивания.
Далее из элементарных случаев соберем ситуации из 8, 9, 10, 11 и 12 монет. Как вы видите решение?
Ниже полное решение.
Первый шаг: разделим монеты на 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) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак « Заключение
При поступлении задачи на доработку или отладку хорошо применить рассмотренный выше подход:
- Определиться, что дано?
- На какие элементарные случаи\задачи можно разложить?
- Что неизвестно для решения задачи? Какие эксперименты нужно провести, чтобы снизить энтропию?
- Выполнить.
- Задача решена? Нет? Вернуться к шагу 1.
Успешных решений.
Источник