В систему команд исполнителя Водолей входят 6 команд
Рабочая тетрадь по Информатике 8 класс Босова
of your page —>
Задание 96. В систему команд исполнителя Водолей входят 6 команд.
Объем сосуда А равен 4 л, сосуда В — 3 л. Как получить 2 л в одной из емкостей, используя не более 4 команд? В ответе запишите номера команд в нужном порядке. 1) Наполнить в сосуд В — 2
2) Перелить из В в А — 4 => в сосуде А 3 л.
3) Наполнить сосуд В — 2
4) Перелить из В в А — 4 (долить доверху)
5) В сосуде В осталось 2 литра.
Ответ: 2, 4, 2, 4
of your page —>
- Правообладателям
- Карта сайта
Какие команды сможет выполнить исполнитель водолей
В XXI веке перед человеком всё чаще возникают задачи, которые «непонятно, как решать». Наверное, такие задачи вам тоже встречались и в курсе математики, и в жизни. Это — хорошо, надо привыкать к решению таких задач, тренироваться. При этом человек приобретает опыт и в использовании некоторых общих подходов, методов решения задач, применимых в различных ситуациях.
Такие подходы занимают важное место в алгоритмическом (вычислительном) мышлении.
Проиллюстрируем наши общие соображения на примере.
Попробуй решить следующую задачу, сначала — без компьютера:
Задача 2. Имеются 8-литровый сосуд A и 5-литровый сосуд В . Отмерь 4 л воды.
Возможны следующие варианты:
1. Вы уже решали похожие задачи раньше, используя свой опыт, вы быстро находите решение. Очень хорошо, что вы получили это решение, надеемся, что оно верное. Но при этом мало что добавилось к вашему опыту решения совсем новых, неожиданных задач.
2. Попробовав разные варианты, вы постепенно нащупали решение. Опять-таки, надеемся, что решение — правильное. Вероятно, вы получили при этом больше удовольствия, чем, скажем, при решении примера «78302 х 239 =?». И очень важно, что вы приобрели опыт решения чего-то нового.
3. Найти решение так и не удалось. Это не значит, что вы потратили время зря. Опыт поиска решения в незнакомой ситуации полезен, даже если он не дал требуемого результата.
Теперь мы расскажем вам об одном общем подходе к решению самых разных задач, совсем не обязательно из информатики. Вот в чём он состоит:
• Предположите, что задача уже решена. В нашем случае —
что нужное количество воды отмерено, то есть состояние
наших сосудов — требуемое.
• Подумайте, какое состояние могло быть до этого, из которого
можно перейти в требуемое. Сделайте мысленный «шаг назад»
(чтобы сделать «шаг вперёд», может потребоваться несколько
команд).
• Подумайте, из какого состояния можно попасть в то, которое
вы себе представили.
• И т. д.
Возможно, вы сможете так добраться до ситуации, описанной в условии задачи. Но ведь это значит, что вы задачу решили: надо просто сделать нужную последовательность шагов в правильном порядке.
Может быть, вы уже знали этот способ или изобрели его в ходе решения задачи (что ещё лучше).
Можно представить себе наш ход мысли и несколько иначе. Мы можем, не сумев сразу решить какую-то задачу, свести её к другой, которая кажется нам более простой. «Свести» означает, что если мы решим более простую задачу, то решим и первоначальную.
Давайте попробуем так решать нашу задачу о переливании.
0. Наша исходная задача — получить 4 л в любом сосуде, например, в сосуде B .
1. Глядя на наши сосуды, мы видим, что достаточно получить 7 литров в сосуде A . После этого надо выполнить пару команд:
наполни B
перелей из B в A
При переливании из B в A сосуд A вместит дополнительно только 1 л
(7+1=8), а 5–1=4 л останется в сосуде B ,и исходная задача решена.
2. Как получить 7 литров в сосуде A ? Можно, например, сначала получить 2 л в сосуде A . Если в сосуде A 2 л воды, то после выполнения команд
наполни B
перелей из B в A
в сосуде A окажется 2+5=7 л воды.
3. Задача получения 2 л в сосуде A сводится к задаче получить 2 л в сосуде B . Если в сосуде B 2 л, то нужно выполнить пару команд:
вылей из А
перелей из B в A
4. А как можно получить 2 л в сосуде B ? Эта задача сводится к задаче получить 5 л в сосуде A . Если в сосуде А 5 л, то нужно выполнить пару команд:
наполни B
перелей из B в A
При переливании из B в A сосуд A заполнится до краёв и в B останется 2 л.
5. А задача получить 5 л в A совсем простая и решается так: если сосуд A пуст, то достаточно выполнить две команды:
наполни B
перелей из B в A
Но в начальный момент, по условию задачи, сосуд A пуст.
Проверим, привёл ли наш способ сведения задач и хода в обратную сторону к решению.
Итак, в условии задачи дано, что в начальный момент сосуд A пуст. Поэтому:
– выполнение в начальный момент пары команд из п. 5 решит задачу
получить 5 литров в сосуде A;
– последующее выполнение пары команд из п. 4 решит задачу
получить 2 литра в сосуде B;
– последующее выполнение пары команд из п. 3 решит задачу
получить 2 литра в сосуде A;
– последующее выполнение пары команд из п. 2 решит задачу
получить 7 литров в сосуде A;
– последующее выполнение пары команд из п. 1 решит исходную задачу
получить 4 литра в сосуде B.
Таким образом, исходная задача получить 4 л в сосуде B решается такой последовательностью из 10 команд:
наполни B
перелей из B в A
наполни B
перелей из B в A
вылей из А
перелей из B в A
наполни B
перелей из B в A
наполни B
перелей из B в A
Чтобы проверить эту программу в игре «Водолей», нужно еще по завершении программы опустошить сосуд A , то есть добавить в конец программы команду
вылей из А
Проверим это решение на компьютере. Компьютер подтверждает, что всё правильно (см. рисунок на следующей странице).
Итак, мы познакомились с одним из приёмов алгоритмического мышления — это решение задачи «с конца». Мы представляем себе цель, дальше понимаем, что цель будет достигнута, если мы дойдём до предыдущей цели и т. д. Этот приём является частным случаем более общего подхода: мы выделяем некоторую промежуточную цель, о которой можем не знать точно, а только надеяться, что она достижима. И дальше мы решаем уже две задачи: как достичь промежуточной цели и как из промежуточной достичь конечной.
Наконец, и этот подход можно обобщить: можно по исходной задаче создать систему новых задач, решение которых может нас привести к искомой цели. По ходу дела некоторые новые задачи могут оказаться нерешаемыми или ненужными, а заключительную цель приходится менять. Но в конце концов мы находим решение исходной задачи. И это всё — алгоритмическое мышление! Конечно, в алгоритмическом мышлении есть и другие элементы. О них будет идти речь на протяжении всего нашего учебника.
4. Алгоритмическое (вычислительное) мышление. Как можно проверить программу
Предположим, нам дали решение задачи «отмерить», показанное на рисунке выше:
наполни B
перелей из B в A
наполни B
перелей из B в A
вылей из А
перелей из B в A
наполни B
перелей из B в A
наполни B
перелей из B в A
вылей из А
Как проверить, что это решение правильное?
Если под руками есть интернет и компьютер, можно запустить игру «Водолей» и выполнить программу в этой игре. Но если компьютера под руками нет, можно проверить правильность программы «вручную». Вооружаемся карандашом и бумагой и составляем таблицу переливаний. В левой части таблицы выпишем в столбик все команды программы, а в правой части мы будем последовательно, строка за строкой, записывать в строке с каждой командой количество литров воды, которое оказалось в сосудах Водолея после выполнения этой команды. В начало таблицы включим дополнительную строку, в которой записано, сколько воды было в каждом сосуде до выполнения первой команды.
Заполнять эту таблицу будем последовательно, сверху вниз. Заполним строку 1. До выполнения команды наполни B оба сосуда были пусты. После выполнения команды сосуд A останется пустым, сосуд B наполнится до краёв, значит, вносим в таблицу в строку 1 числа 0 и 5. Повторяя эти действия, получаем такую таблицу:
Из таблицы видно, что после выполнения последней команды программы в сосуде B будет 4 л, а сосуд A будет пуст. Таким образом, таблица доказывает, что наша программа действительно даёт нужное решение задачи.
При составлении таблицы человек мог допустить ошибку. Как проверить, правильно ли составлена таблица? Можно попробовать составить её ещё раз и потом сравнить, что получилось. Можно поступить иначе. А именно, попросим кого-нибудь (но можем сделать это и сами) прочитать состояние сосудов в каждой строке (начиная с нулевой). Например (какая там команда — неважно):
Затем прочитать в следующей строке команду и состояние сосудов:
Теперь выполним команду. Видим, что состояние сосудов в следующей строке записано правильно: мы из B перелили в A 3 л, больше в A не поместилось, сосуд A заполнился, в B осталось 2 л. Значит, строка 4 заполнена правильно.
Проверь правильность строки 5 и строки 6.
Сейчас мы выявили ещё один важный элемент алгоритмического (вычислительного) мышления. Бывает так, что нам нужно проверить правильность конструкции или работы чего-то большого, например, машины, программы, космического корабля или даже какой-то системы общественного управления, природной системы. Иногда оказывается, что для этого достаточно проверить правильность работы каждого отдельного элемента системы и каждого взаимодействия связанных элементов. То есть правильность глобального (большого) объекта установлена, если мы установили правильность всех его элементов (локальную правильность). Это — очень ценная возможность, и часто большие объекты создаются так, чтобы возможность такой проверки имелась. Некоторые проверки можно делать в определённом порядке, а некоторые — параллельно.
5. Сколько нужно ресурсов: как Водолей расходует воду
При решении задачи 2 Водолей израсходовал 20 л воды из резервуара и вылил 16 л воды. А 4 л остались в сосуде B в качестве результата работы. Чтобы отмерить 4 л, мы израсходовали целых 20 л воды. Если бы мы попробовали получить 4 л с помощью сосудов 8 л и 7 л, то, как показывают эксперименты, пришлось бы израсходовать ещё больше воды (потребовалось бы не меньше 40 л). А что, если Водолей не будет выливать воду на землю, а будет аккуратненько возвращать её в тот резервуар, откуда он воду берёт? Оказывается, в этом случае удастся обойтись гораздо меньшим количеством воды. А именно, если в начальный момент у Водолея два пустых рабочих сосуда A и B и в резервуаре запасено ровно столько воды, сколько нужно для одновременного заполнения A и B , то Водолей может спокойно проводить все операции с сосудами A и B , не беспокоясь о том, что в резервуаре не хватит воды.
Действительно, суммарное количество воды в сосудах и резервуаре остаётся постоянным. Поэтому переполнение резервуара случиться не может, ведь в начальный момент вся вода помещалась в резервуаре. Стать пустым резервуар может. Но только в том случае, когда оба сосуда A и B полностью заполнены. Но в этом случае необходимости брать воду из резервуара нет, поскольку в сосудах нет свободного места.
Вы уже понимаете, что анализ ресурсов, необходимых для выполнения той или иной задачи, тоже — часть алгоримического (вычислительного) мышления.
6. Вопросы и упражнения
Если в условии задачи этого раздела не указано начальное количество воды в сосудах, то это означает, что все сосуды пусты.
Заполни таблицу переливаний, указав количество воды в каждом сосуде после выполнения каждой команды следующей программы:
Дана таблица переливаний для неизвестной программы из 9 команд, правая часть таблицы заполнена.
а) Догадайся, какая это была программа, и внеси её в таблицу.
б) Попробуй дописать программу так, чтобы в одном из сосудов получилось 5 л.
Метод решения задач для исполнителя Водолей с двумя сосудами с помощью кратных емкостей
Аннотация
В статье рассматривается простой и наглядный метод поиска решения задач для исполнителя Водолей (далее Водолей) с двумя сосудами с помощью построения таблицы с кратными емкостями.
Предлагаемый метод позволяет ученикам просто, быстро и, главное, осознанно находить оптимальное решение задач для Водолея, а учителям — тратить меньше времени на составление и проверку задач на переливания.
Метод опробован автором в течение ряда лет на уроках в 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 л в 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.
Для краткости и наглядности команды Водолея в таблице будем обозначать стрелками.
Справа от каждой команды будем показывать состояние сосудов после выполнения команды и сколько в сумме литров прошло (перекачено) через сосуды. Т.е. фактически сделаем ручную трассировку (прокрутку) программы.
Задача 1. Решение задачи с трассировкой
Какие команды сможет выполнить исполнитель водолей
Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полность наполняется.
Входные данные
Программа получает на вход три натуральных числа A, B, N, не превосходящих 10 4 .
Выходные данные
Необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст Impossible.
Количество операций в алгоритме не должно превышать 10 5 . Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 10 5 операций.
Тесты к этой задаче закрытые.