Нужен легкий код. На форуме уже видел решение, но большую его часть я не понял. У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции: Наполнить сосуд A (обозначается >A). Наполнить сосуд B (обозначается >B).
Вылить воду из сосуда A (обозначается A>). Вылить воду из сосуда B (обозначается B>). Перелить воду из сосуда A в сосуд B (обозначается как A>B). Перелить воду из сосуда B в сосуд A (обозначается как B>A). Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полность наполняется.
Входные данные Программа получает на вход три натуральных числа A, B, N, не превосходящих 10^4.
Код к задаче: «Исполнитель Водолей»
Листинг программы
const LIMIT=100000; var a,b,n:longint; min,max:char; reall:boolean; bV,aV,k:longint; begin read(a,b,n); min:=’A’; max:=’B’; reall:=false; if a>b then begin min:=’B’; max:=’A’; a:=a+b; b:=a-b; a:=a-b; end; aV:=0; bV:=0; k:=0; while k= a) then inc(bV,a) else begin bV:= a — (b — bV); inc(k,2); end; if (n = bV) then begin reall := true; break; end; end; if reall then begin bV:=0; while true do begin writeln(‘>’,min); writeln(min,’>’,max); if b-bV>=a then inc(bV,a) else begin bV := a-(b — bV); writeln(max,’>’); writeln(min,’>’,max); end; if (n = bV) then break; end; end else writeln(‘Impossible’); end.
Источник: studassistent.ru
КуМир исполнитель Водолей
Метод решения задач для исполнителя Водолей с двумя сосудами с помощью кратных емкостей
Аннотация
В статье рассматривается простой и наглядный метод поиска решения задач для исполнителя Водолей (далее Водолей) с двумя сосудами с помощью построения таблицы с кратными емкостями.
Предлагаемый метод позволяет ученикам просто, быстро и, главное, осознанно находить оптимальное решение задач для Водолея, а учителям — тратить меньше времени на составление и проверку задач на переливания.
Метод опробован автором в течение ряда лет на уроках в 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 | 8 | 16 | 24 | 32 | 40 | … | |
| В = 5 | 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. Решение задачи с трассировкой
Источник: ya-uchitel.ru
К. Поляков, 2010 -2011 1 Исполнитель Водолей Урок 0. Знакомство с исполнителем Водолей. — презентация
Презентация на тему: » К. Поляков, 2010 -2011 1 Исполнитель Водолей Урок 0. Знакомство с исполнителем Водолей.» — Транскрипт:
1 К. Поляков, Исполнитель Водолей Урок 0. Знакомство с исполнителем Водолей
2 Исполнитель Водолей К. Поляков, Система команд 1. наполни A 2. вылей A 3. перелей из A в B AB ABABAB AA AAAA
3 Исполнитель Водолей К. Поляков, Задачи из папки «Водолей» 3 «3»: 1.vod (за 4 шага) «4»: 1.vod (за 4 шага) 2.vod (за 4 шага) «5»: 1.vod (за 4 шага) 2.vod (за 4 шага) 3.vod (за 8 шагов) «6»: 1.vod (за 4 шага) 2.vod (за 4 шага) 3.vod (за 8 шагов) 4.vod (за 10 шагов)
4 К. Поляков, Исполнитель Водолей Урок 1. Как решать задачи для Водолея?
5 Исполнитель Водолей К. Поляков, Метод перебора 5 (0,0) (5,0)(0,3) (2,3)(3,0) (3,3) (5,1) (2,0)(0,3) (5,3) +A+A+B+B B A +B+B +B+B A B -B-A +A+A +A+A граф -A-A -A-A -A-A -B-B +A+A A A B B Граф – это набор узлов и соединяющих их рёбер (дуг)! ! Есть 5-литровый сосуд (A) и 3-литровый (B). Отмерьте 1 литр воды.
6 Исполнитель Водолей К. Поляков, Метод бильярда B A наполни B перелей из B в A перелей из A в B вылей A вылей B наполни A Есть 5-литровый сосуд (A) и 3-литровый (B). Отмерьте 1 литр воды. 1.наполни B 2.перелей из B в A 3.наполни B 4.перелей из B в A
7 Исполнитель Водолей К. Поляков, Общий алгоритм (бильярд) 7 пока (в сосуде A X) и (в сосуде B X) если B пуст, то наполни B если A полон, то вылей A перелей из B в A конец B A цикл Второй путь? ?
8 Исполнитель Водолей К. Поляков, Табличная запись решения 8 Есть 5-литровый сосуд (A) и 3-литровый (B). Отмерьте 1 литр воды. 1.наполни B 2.перелей из B в A 3.наполни B 4.перелей из B в A 1234 A (5 л) B (3 л) B B A +B B A
9 Исполнитель Водолей К. Поляков, Ещё один пример 9 Есть 6-литровый сосуд (A) и 3-литровый (B). Отмерьте 2 литра воды. Если объемы A и B имеют наибольший общий множитель X, то можно отмерить только объем, кратный X! ! Если объемы A и B – взаимно-простые числа (имеют НОД=1), то можно отмерить любой объем max(A,B)! ! B A 6
10 Исполнитель Водолей К. Поляков, Программа для Водолея в Кумире 10 использовать Водолей алг Отмерить 1 литр нач наполни B перелей из B в A наполни B перелей из B в A кон использовать Водолей алг Отмерить 1 литр нач наполни B перелей из B в A наполни B перелей из B в A кон начало алгоритма конец алгоритма подключить исполнителя название алгоритма название алгоритма
11 Исполнитель Водолей К. Поляков, Задачи из практикума «Водолей» 11 Урок 1. Линейные алгоритмы «3»: 1-1, 1-2 «4»: 1-1, , 1-4 «5»: 1-1, , , 1-6
12 К. Поляков, Исполнитель Водолей Урок 2. Циклы
13 Исполнитель Водолей К. Поляков, Задача 13 3 л3 л2 л AB Есть 3-литровый сосуд (A) и 2-литровый (B). Отмерьте 1 литр воды. наполни A перелей из A в B наполни A перелей из A в B A B
14 Исполнитель Водолей К. Поляков, Задача 14 7 л2 л AB Есть 7-литровый сосуд (A) и 2-литровый (B). Отмерьте 1 литр воды. наполни A перелей из A в B вылей B перелей из A в B вылей B перелей из A в B наполни A перелей из A в B вылей B перелей из A в B вылей B перелей из A в B A B вылей B команды повторяются 3 раза
15 Исполнитель Водолей К. Поляков, Цикл 15 Цикл – это многократное выполнение одинаковых действий. начало конец наполни A перелей из A в B вылей B цикл нет да Когда остановиться? ? В каких случаях работает? В каких – нет? ? сделали 3 раза? loop петля
16 Исполнитель Водолей К. Поляков, Цикл «N раз» 16 7 л7 л2 л AB Есть сосуд A (его объем – 7 литров) и 2-литровый сосуд (B). Отмерьте 1 литр воды. Сколько шагов цикла нужно сделать? ? использовать Водолей алг Отмерить 1 литр нач наполни A нц 3 раз перелей из A в B вылей B кц кон использовать Водолей алг Отмерить 1 литр нач наполни A нц 3 раз перелей из A в B вылей B кц кон Подходит ли для других задач? ? Esc, Р
17 Исполнитель Водолей К. Поляков, Вычисление количества шагов 17 A л2 л AB Есть сосуд A (его объем – нечетное число) и 2-литровый сосуд (B). Отмерьте 1 литр воды. размер A N div(размер A, 2) разделить размер A на 2 нацело Сколько шагов цикла нужно сделать? ? размер B
18 Исполнитель Водолей К. Поляков, Задачи из практикума «Водолей» 18 Урок 2. Циклы «N раз» «3»: 2-1, 2-2, 2-3 «4»: 2-1, 2-2, , 2-5 «5»: 2-1, 2-2, , , 2-7
19 К. Поляков, Исполнитель Водолей Урок 3. Циклы с условием
20 Исполнитель Водолей К. Поляков, Задача 20 7 л2 л AB Есть 7-литровый сосуд (A) и 2-литровый (B). Отмерьте 1 литр воды. наполни A перелей из A в B вылей B перелей из A в B вылей B перелей из A в B наполни A перелей из A в B вылей B перелей из A в B вылей B перелей из A в B A B вылей B при каком условии остановить цикл? Повторять пока в сосуде А 1 ! !
21 Исполнитель Водолей К. Поляков, Цикл 21 начало конец наполни A перелей из A в B вылей B цикл да нет В каких случаях работает? В каких – нет? ? в сосуде А 1? loop петля
22 Исполнитель Водолей К. Поляков, Программа в Кумире 22 использовать Водолей алг Отмерить 1 литр нач наполни A нц пока в сосуде A 1 перелей из A в B вылей B кц кон использовать Водолей алг Отмерить 1 литр нач наполни A нц пока в сосуде A 1 перелей из A в B вылей B кц кон начало цикла конец цикла если размер A = 12 размер B = 2 ? ? зацикливание Esc, П Как избежать зацикливания? ?
23 Исполнитель Водолей К. Поляков, Задачи из практикума «Водолей» 23 Урок 3. Циклы «пока» «3»: 3-1, 3-2 «4»: 3-1, , 3-4 «5»: 3-1, , , 3-6
24 К. Поляков, Исполнитель Водолей Урок 4. Переменные
25 Исполнитель Водолей К. Поляков, Задача 25 7 л2 л AB Есть 7-литровый сосуд (A) и 2-литровый (B). Отмерьте 1 литр воды. 1) использовать цикл пока 2) не использовать команду в сосуде А Нужно запоминать, как меняется объем воды в сосуде А! ! в сосуде А размер А уменьшить на 2
26 Исполнитель Водолей К. Поляков, Как хранить данные? 26 Оперативная память ячейка памяти нач цел N N:= 25 N:= размер А N:= N — 2 кон нач цел N N:= 25 N:= размер А N:= N — 2 кон ?25 75 переменная целого типа новое значение переменной уменьшить на 2 Переменная – это величина, имеющая имя, тип и значение. Значение переменной может изменяться во время работы программы.
27 Исполнитель Водолей К. Поляков, Переменные 27 использовать Водолей алг Отмерить 1 литр нач цел N наполни A N := размер A кон использовать Водолей алг Отмерить 1 литр нач цел N наполни A N := размер A кон нц пока N > 1 перелей из A в B вылей B N:= N — 2 кц нц пока N > 1 перелей из A в B вылей B N:= N — 2 кц объявление целой переменной запись нового значения в переменную Для каких задач работает? ?
28 Исполнитель Водолей К. Поляков, Трассировка 28 Трассировка – это отслеживание изменения значений переменных во время работы программы. F8 – выполнить один шаг. эта команда еще не выполнялась получено на предыдущем шаге цикла
29 Исполнитель Водолей К. Поляков, Задачи из практикума «Водолей» 29 Урок 4. Переменные «3»: 4 -1, 4-2 «4»: 4 -1, , 4-4 «5»: 4 -1, , , 4-6
30 К. Поляков, Исполнитель Водолей Урок 5. Ветвления
31 Исполнитель Водолей К. Поляков, Задача 31 3 л3 л2 л AB Есть два сосуда, один из них (неизвестно какой) имеет объем 3 литра, а другой – 2 литра. Отмерьте 1 литр воды. 2 л3 л AB или наполни A перелей из A в B наполни A перелей из A в B наполни B перелей из B в A наполни B перелей из B в A или Как выбрать из двух вариантов? ?
32 Исполнитель Водолей К. Поляков, Ветвление на блок-схеме 32 начало конец наполни A перелей из A в B ветвление да размер B = 2? нет наполни B перелей из B в A Ветвление – это выбор одного из двух вариантов в зависимости от выполнения некоторого условия.
33 Исполнитель Водолей К. Поляков, Ветвление в программе 33 использовать Водолей алг Отмерить 1 литр нач если размер B = 2 то наполни A перелей из A в B иначе наполни B перелей из B в A все кон использовать Водолей алг Отмерить 1 литр нач если размер B = 2 то наполни A перелей из A в B иначе наполни B перелей из B в A все кон наполни A перелей из A в B наполни B перелей из B в A размер B = 2 условие если условие выполнено (истинно) если условие НЕ выполнено (ложно) Esc, Е
34 Исполнитель Водолей К. Поляков, Задачи из практикума «Водолей» 34 Урок 5. Ветвления «3»: 5 -1, 5-2 «4»: 5 -1, , 5-4 «5»: 5 -1, , , 5-6 «6»: 5 -1, , , , 5-8
35 Исполнитель Водолей К. Поляков, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ 163, г. Санкт-Петербург В практикуме использованы разработки Д.П. Кириенко (
Источник: www.myshared.ru