Б. С. Михлин
ГБОУ «Школа Новокосино» имени Героя Советского Союза адмирала А. П. Михайловского, г. Москва, Россия
МЕТОД РЕШЕНИЯ ЗАДАЧ ДЛЯ ИСПОЛНИТЕЛЯ ВОДОЛЕЙ С ДВУМЯ СОСУДАМИ С ПОМОЩЬЮ КРАТНЫХ ЕМКОСТЕЙ.
Аннотация
В статье рассматривается простой и наглядный метод поиска решения задач для исполнителя Водолей (далее Водолей) с двумя сосудами с помощью построения таблицы с кратными емкостями.
Предлагаемый метод позволяет ученикам просто, быстро и, главное, осознанно находить оптимальное решение задач для Водолея, а учителям — тратить меньше времени на составление и проверку задач на переливания.
Метод опробован автором в течение ряда лет на уроках в 5 7 классах и является актуальным, т.к. в ряде распространенных учебных пособий, к сожалению, отсутствует описание способа поиска решения задач для Водолея, что приводит к переборному решению этих задач учениками и снижает образовательный потенциал этого исполнителя.
Для расширения образовательных возможностей Водолея в статье рекомендуется также использование в программах для исполнителя циклов и других конструкций программирования.
Метод поиска решения разбирается на примерах задач для двух сосудов (первоначально пустых и для случая, когда один из сосудов первоначально частично заполнен). Полученные решения проверяются в средах Водолей КуМир и Водолей Blockly.
Описанный метод предназначен, прежде всего, для учителей начального курса информатики (5 7 классы). Он также будет полезен учителям математики и родителям учеников.
Ключевые слова: исполнитель Водолей, Водолей-Blockly, КуМир, исполнители, алгоритмика, алгоритмизация и программирование, программирование исполнителей, информатика в 5-7 классах, начальный курс информатики, алгоритмическое мышление.
Посвящаю эту статью своей жене Людмиле
«Водолей?.. Это очень просто!»
«Лей воду с умом!» — девиз Водолея
«Во всем мне хочется дойти
До самой сути». Б.Л. Пастернак
Введение
Роль темы «Алгоритмизация и программирование» в школьной программе по информатике в последнее время заметно возрастает.
В 5–7 классах эта тема традиционно изучается на базе различных исполнителей с компьютерной поддержкой. Среди других исполнителей исполнитель Водолей (далее Водолей) изучается обычно одним из первых.
К сожалению, как в старых учебных пособиях [4], [5], [9], так и в недавно выпущенных (например, [1] [3], [6], [10]) в разделах о Водолее отсутствует описание метода поиска решения задач.
Это приводит к тому, что ученики часто решают задачи для Водолея, просто перебирая различные комбинаций команд. Учащиеся не могут объяснить, как нашли решение, является ли оно оптимальным (самым коротким) и есть ли другие решения. Некоторые задачи вызывают затруднения и у учителей.
Все это не позволяет полностью раскрыть образовательный потенциал Водолея, и он фактически занимает в школьной программе очень скромное место среди других исполнителей (Робот, Чертежник и др.).
Пробел в учебных пособиях по освещению методов поиска решения устраняет статья К.Ю. Полякова «Водолей + КуМир + практикум» [12] в которой рассматриваются различные методы решения задач для Водолея: перебора (построением графа (дерева) или таблицы), бильярда и через диофантовы уравнения. Существует также метод координатной плоскости и метод блок-схем.
Задачи для исполнителя Водолей обычно бывают с двумя или с тремя сосудами, которые первоначально пустые или содержат какое-то количество воды.
В данной статье рассматривается простой и наглядный метод поиска решения задач для Водолея с двумя сосудами.
Краткое описание предлагаемого метода решения
Основная идея решения состоит в том, чтобы заполнить таблицу из двух строк, где:
- строка A: исходная емкость сосуда A и несколько кратных ей емкостей,
- строка B: исходная емкость сосуда B и несколько кратных ей емкостей.
Затем надо найти в этой таблице два числа (одно в строке A, а второе в строке В) такие, чтобы их разность по модулю равнялась искомому количеству воды. Эта пара чисел (емкостей) и определяет решение задачи.
Разбор предлагаемого метода на примере задач
Рассмотрим предлагаемый метод поиска решения на примере двух классических задач для Водолея:
задача 1 с первоначально пустыми сосудами;
задача 2 с первоначально не пустым (частично заполненным) сосудом.
Оптимальным (лучшим) решением считается решение с меньшим количеством команд, которые выполнил Водолей для получения результата.
Задача 1. Первоначально пустые сосуды
Условие задачи.
Даны два сосуда :
А = 8 л;
В = 5 л.
Первоначально оба сосуда пустые.
Отмерить 1 л в любом сосуде.
Проверка существования решения.
Убедимся, что задача имеет решение (см., например, [4], [5], [9], [12]) .
Решение задачи существует, если количество воды, которое надо отмерить делится нацело на наибольший общий делитель емкостей A и B (НОД (А, В)).
НОД (5, 8) = 1. Количество воды, которое надо отмерить (1 л) делится нацело на НОД (5, 8) следовательно, задача имеет решение.
Поиск решения.
Построение рисунка.
Для наглядности сделаем рисунок заданных в условии задачи сосудов (рис. 1).
| |
|
|
| А = 8 л |
|
В = 5 л |
| Рис. 1. Задача 1. Исходные сосуды |
Построение таблицы кратных емкостей.
Заполним таблицу, например, пятью емкостями, кратными заданным в условии емкостям сосудов A и B (табл. 1).
Таблица 1
Задача 1. Кратные емкости
| Сосуд, л |
Пустые |
|
1 л в A |
|
|
|
|
| А = 8 |
0 |
8 |
16 |
24 |
32 |
40 |
… |
| В = 5 |
0 |
5 |
10 |
15 |
20 |
25 |
… |
| |
|
|
|
|
|
1 л в B |
|
Поиск решения по таблице.
Ищем по таблице емкость в строке A и емкость в строке B такие, чтобы их разность по модулю равнялась искомому 1 л воды. Найденные пары чисел выделены в таблице серым фоном и соединены стрелками, которые показывают направление переливания воды, а выбранные для решения числа еще и подчеркнуты. Как видим, в таблице 1 есть два решения задачи: (16, 15) и (25, 24).
Чем ближе найденная пара чисел (емкостей A и В) к левому краю таблицы, тем короче и, следовательно, лучше решение.
Из таблицы 1 также сразу видно, с наполнения какого сосуда надо начинать решение и в каком сосуде останется искомое количество воды.
Начинать надо с наполнения сосуда, в строке которого находится большее число из пары чисел с решением и в нем же останется искомое количество воды. Например, для решения (16, 15) надо начинать с сосуда A, т.к. 16 л находятся в строке A, а для решения (25, 24) надо начинать с сосуда B, т.к. 25 л находятся в строке В.
Чтобы не пропустить в таблице какое-либо решение (или чтобы вообще не строить таблицу) можно воспользоваться программой из Приложения 1, которая написана на языках Python (Пайтон), КуМир, PascalABC.NET. Программа выдаст пары чисел для решений, или сообщит, что решения нет (в рамках заданной максимальной кратности равной в программе, как и в таблицах, пяти).
Самое короткое решение задачи 1 будет для пары чисел (16, 15). Его и рассмотрим.
Давайте немного пофантазируем и временно изменим условие задачи.
Было бы здорово, если бы сосуд A был емкостью 16 л, а сосуд B – емкостью 15 л. Мы бы тогда наполнили сосуд A (16 л), затем перелили воду в сосуд B (т.е. от 16 л отлили 15 л) и 1 л воды остался бы в сосуде А. И все, задача решена!
Но, к сожалению, нам дано, что A = 8 л, а B = 5 л и мы физически не сможем за один раз вместить в восьмилитровый сосуд A 16 л воды и перелить в пятилитровый сосуд B 15 л воды. Но зато мы сможем это сделать в сумме за несколько раз (ведь 16 кратно 8, а 15 кратно 5). В этом и состоит ключевая идея решения задачи.
Т.е. мы можем за два раза в сумме перекачать через сосуд А 16 л с помощью заданного в задаче восьмилитрового сосуда А, а также за три раза перекачать через пятилитровый сосуд B в сумме 15 л воды.
При решении задачи для реальных (заданных в условии) значений емкостей сосудов A и B мы будем придерживаться алгоритма решения задачи с временно измененными (нафантазированными) условиями.
Решение начнем с наполнения сосуда A (А = 8 л). Затем все время переливаем воду в сосуд B (В = 5 л). Как только сосуд B станет полным – выливаем из него всю воду. Если в сосуде A осталась вода, то продолжаем переливать ее в сосуд B. Если сосуд A опустеет, то снова наполняем его доверху. В сумме через сосуд A должно пройти 16 л воды, а через сосуд B — 15 л воды.
Перенос найденного решения с таблицы на рисунок.
Дополним рисунок 1 найденным в таблице 1 решением для пары чисел (16, 15) и получим рисунок 2:
Наполняем A
2 раза х 8 л |
|
Все время переливаем из A в B |
|
Выливаем
2 раза х 5 л и 5 л оставляем в B |
| |
А = 8 л (Останется 1 л) |
|
В = 5 л |
|
| Рис. 2. Задача 1. Рисунок с решением для пары чисел (16, 15) |
Фактически задача уже решена, но она недостаточно формализована для Водолея. Он не может решать задачу по рисунку или таблице. Водолею нужны команды, которые он понимает, т.е. команды из его СКИ.
Построение таблицы с командами для Водолея и трассировкой.
Чтобы проверить найденное решение и подготовить его для реализации на компьютере, оформим решение в виде таблицы 2.
Для краткости и наглядности команды Водолея в таблице будем обозначать стрелками.
Справа от каждой команды будем показывать состояние сосудов после выполнения команды и сколько в сумме литров прошло (перекачено) через сосуды. Т.е. фактически сделаем ручную трассировку (прокрутку) программы.
Таблица 2
Задача 1. Решение задачи с трассировкой
|
