Из трех монет одна фальшивая с помощью блок схемы



Составить блок-схему для задачи: Из трех монет одинакового достоинства

Составить блок-схему для задачи: Из трех монет одинакового достоинства одна фальшивая (более легкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?

Слайд 43 из презентации «Алгоритмы… Кругом алгоритмы»

Размеры: 720 х 540 пикселей, формат: .jpg. Чтобы бесплатно скачать слайд для использования на уроке, щёлкните на изображении правой кнопкой мышки и нажмите «Сохранить изображение как. ». Скачать всю презентацию «Алгоритмы… Кругом алгоритмы.ppt» можно в zip-архиве размером 1210 КБ.

Алгоритм

«Определение и свойства алгоритма» — Массовость. Запись последовательности команд. Свойства алгоритмов. Понятность. Определения алгоритма. Типы алгоритмов. Ларец. Способы описания алгоритма. Характеристика исполнителя. Определенность. Мышка. Исполнитель алгоритма. Конечность. Исполнитель. Примеры свойств. Алгоритм. Дискретность. Каша.

«Информатика «Понятие алгоритма»» — Материал для любознательных. Практическое задание. Может ли компьютер самостоятельно решить задачу. Куда может быть встроен компьютер. Этапы работы. Огромное количество задач разной сложности. Алгоритм. Как может использоваться компьютер. Компьютер. Разрабатывать алгоритмы может только человек. Что такое алгоритм.

«Выполнение алгоритмов компьютером» — Этапы выполнения программы. Почему компьютер можно назвать формальным исполнителем? Какие особенности выполнения программы на ЯМК компьютером? Создание программы на языке, понятном человеку (ЯПВУ). Результат. Основные вопросы: Исполнение программы на ЯМК. В чём отличие формального исполнителя от интеллектуального?

«Выполнение алгоритмов» — Робот действует на клетчатой доске. Материалы. Сверху свободно. Снизу свободно. Поиск алгоритма минимальной длины. Сдвиг влево. Обратный ход. Поезд. Нарисуем. Система команд. Код команды. Команды. Тип «строка». Слева свободно. Действие. Выполнение алгоритмов для исполнителя. Длина. Система команд исполнителя.

«Задания по теме алгоритмы» — 1. Набрать 3-литровый кувшин. 1. Набрать 8 литров. По шагам. 4. Проверить пенал. Составьте алгоритм сбора портфеля. Разработать алгоритм может только человек! 1. Взвесить любые две монеты. Алгоритм. 1. Набрать 3-х литровый кувшин. Составь алгоритм, в котором описывается, как должна действовать падчерица.

«Свойства алгоритма» — Любая последовательность действий является алгоритмом. Тестирование. Для любых задач можно разработать алгоритм. Свойство «дискретность» определяет строгую последовательность команд. Повторить алгоритм «высеивания» простых чисел от1 до 100. «Массовость» является желательным свойством алгоритма. Проверка домашнего задания Новый материал «Алгоритмы» Решение задач Тестирование.

Источник

Представьте с помощью блок — схемы алгоритм решения следующей задачи : «Из трех монет одинакового достоинства одна фальшивая (более легкая)?

Информатика | 5 — 9 классы

Представьте с помощью блок — схемы алгоритм решения следующей задачи : «Из трех монет одинакового достоинства одна фальшивая (более легкая).

Как ее найти с помощью одного взвешивания на чашечных весах без гирь?

Взвешиваем две любые монеты — Чашки в равновесии — Да Третья монета фальшивая — Нет Фальшивая монета в более легкой чашке.

Имеется 9 одинаковых с виду монет?

Имеется 9 одинаковых с виду монет.

Из них одна монета фальшивая, которая легче настоящих.

Одна из монет прилипла в одной из чаш чашечных весов.

Отодрать ее не возможно.

Как за два взвешивания найти фальшивую монету?

Имеется 1000 монет, из которых одна монета фальшивая (легче других)?

Имеется 1000 монет, из которых одна монета фальшивая (легче других).

Придумайте способ нахождение фальшивой монеты за 7 взвешиваний на чашечных весах без гирь.

ПОМОГИТЕ ПОЖАЛУЙСТА?

С помощью блок схемы или паскаля Составьте алгоритм для решения следующей задачи : Среди N произвольных вещественных чисел найдите количество не равных нулю.

Алгоритм построение дома с помощи блок схеми?

Алгоритм построение дома с помощи блок схеми.

Имеется два мешка c монетами, в каждом из которых находиться по одной фальшивой монете (более легкой)?

Имеется два мешка c монетами, в каждом из которых находиться по одной фальшивой монете (более легкой).

Для определения фальшивой монеты в первом мешке потребовалось произвести 6 взвешиваний, во втором мешке — 4 взвешивания.

Сколько всего монет было в двух мешках?

1024 80 10 24 512.

ПОМОГИТЕ ПОЖАЛУЙСТА РЕШИТЬ ЗАДАЧИ И ПЛИЗЗЗ ПОБЫСТРЕЕЗадача1?

ПОМОГИТЕ ПОЖАЛУЙСТА РЕШИТЬ ЗАДАЧИ И ПЛИЗЗЗ ПОБЫСТРЕЕ

Среди 27 одинаковых по виду монет есть одна фальшивая, и она легче остальных.

Как взвесив монеты на чашечных весах без гирь три раза, выявить фальшивую?

Как из крана набрать 2 литра воды при помощи 4 — и 3 — литрового баллонов?

Кот Матроскин и пёс Шарик нашли клад, который состоял из 5 одинаковых монт?

Кот Матроскин и пёс Шарик нашли клад, который состоял из 5 одинаковых монт.

В коробке, в которой лежали монеты, друзья обнаружили записку : «При помощи чашечных весов без гирь найдите среди этих 5 монет одну золотую и купите почтальону Печкину велосипед.

Сделайте это при помощи двух взвешиваний.

Золотыя монета более тяжёлая».

Дядя Фёдор помог своим друзьям справится с этим заданием.

Как он действовал?

Впишите действия Дяди Фёдора в блок схему.

Имеется 8 шариков одинаковой формы и размеров?

Имеется 8 шариков одинаковой формы и размеров.

Один из них легче, чем остальные, другие 7 одинаковые.

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

Составте алгоритм с повторением и записать его с помощью блок схемы?

Составте алгоритм с повторением и записать его с помощью блок схемы.

Ответ к задаче : из трёх монет одинакого достоинства одна фальшивая (более легкая)?

Ответ к задаче : из трёх монет одинакого достоинства одна фальшивая (более легкая).

Как её найти с помощью одного взвешивания на чашечных весах без гирь?

Вы открыли страницу вопроса Представьте с помощью блок — схемы алгоритм решения следующей задачи : «Из трех монет одинакового достоинства одна фальшивая (более легкая)?. Он относится к категории Информатика. Уровень сложности вопроса – для учащихся 5 — 9 классов. Удобный и простой интерфейс сайта поможет найти максимально исчерпывающие ответы по интересующей теме. Чтобы получить наиболее развернутый ответ, можно просмотреть другие, похожие вопросы в категории Информатика, воспользовавшись поисковой системой, или ознакомиться с ответами других пользователей. Для расширения границ поиска создайте новый вопрос, используя ключевые слова. Введите его в строку, нажав кнопку вверху.

Источник

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

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

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

1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.

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

1. Давайте сначала разберемся с 2 вариантом, который является частным случаем варианта 1.

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

N >= log₃A,

где 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 монет легче/тяжелее

Этот же результат я приведу в таблице

по формуле — log₃26 =2.9656 — соответственно количество взвешиваний — 3.

еще пример:
число монет- 71. По формуле log₃71 =3.8800 — количество взвешиваний — 4. Проверяем

Ну с алгоритм решения этих задач, я думаю, понятен.

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 >= log₃B + 2,

где N — максимально необходимое количество взвешиваний, натуральное число;
B — количество монет в группе после второго взвешивания.
А если учесть, что B = A/3, где A — количество всех монет, тогда получим:

log3B = log₃A — 1,

N >= log₃A + 1

1) если известно, что фальшивая монета легче/тяжелее, тогда максимальное число взвешиваний определяется по формуле:

N >= log₃A

2) если не известно, какая фальшивая, тогда максимальное число взвешиваний определяется по формуле:

N >= log₃A + 1

где N — максимально необходимое количество взвешиваний, натуральное число, округленное в большую сторону;
А — количество монет.

Источник

Универсальная методика к решению задач на примере головоломки «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. первая группа тяжелее;
2. вторая группа тяжелее;
3. равны.

1) Если группы равны, то фальшивая монета находится в третьей группе. Необходимо найти фальшивую монету из 4 монет за два взвешивания.

Делим третью группу на две: 9 10 11 12

Сравниваем 9 и 10:

• если они равны, то фальшивая монета во второй группе – сравниваем 9 и 11. Если 9 и 11 равны — то фальшивая – 12, если нет -11
• если они не равны, то фальшивая в первой группе – сравниваем 10 и 12. Если 10 и 12 равны – фальшивая – 9, если нет – 10.

Таким образом мы нашли фальшивую монету.

2) Рассмотрим второй случай. Если первая группа тяжелее второй, то присваиваем первой группе знак «>», второй группе знак « Заключение

При поступлении задачи на доработку или отладку хорошо применить рассмотренный выше подход:

1. Определиться, что дано?
2. На какие элементарные случаи\задачи можно разложить?
3. Что неизвестно для решения задачи? Какие эксперименты нужно провести, чтобы снизить энтропию?
4. Выполнить.
5. Задача решена? Нет? Вернуться к шагу 1.

Успешных решений.

Источник