Разработка алгоритмического мышления — одна из ключевых задач для начинающих программистов, и система КуМир предлагает отличный способ погрузиться в этот процесс. Среди множества исполнителей в этой среде особое место занимает "Водолей", который представляет собой виртуальную лабораторию для решения классических задач с переливаниями.
"Водолей" — это исполнитель, моделирующий процесс переливания воды между сосудами разной ёмкости. Он воплощает знаменитую головоломку о необходимости отмерить определённое количество жидкости, имея в распоряжении только несколько сосудов известного объема и отсутствие мерных приборов. На первый взгляд, "Водолей" может показаться простым, но за этой простотой скрывается мощный инструмент для развития логики и алгоритмического мышления. Решение задач на переливание требует анализа, планирования и понимания последовательности действий — все это фундаментальные навыки программирования.
В отличие от других исполнителей КуМира, "Водолей" имеет особую привлекательность — ведь задачи на переливание интуитивно понятны даже людям далеким от программирования. Они встречаются в фильмах (вспомните хотя бы знаменитую головоломку из "Крепкого орешка 3"), книгах, и даже в повседневной жизни. Практическая ценность навыков, получаемых при работе с "Водолеем", выходит далеко за рамки программирования. Они полезны везде, где требуется последовательное решение задач, разбиение сложной проблемы на простые шаги и алгоритмическое мышление.
В курсе информатики исполнитель "Водолей" часто используется для демонстрации сразу нескольких ключевых концепций:- формализация алгоритмов.
- цикличность процессов.
- поиск оптимальных решений.
- ветвления в алгоритмах.
Важно понимать, что хотя сама задача переливаний может показаться немного искуственной (в реальном мире мы обычно пользуемся мерными стаканами!), математическая модель, лежащая в её основе, имеет широкое применение в различных областях — от логистики до криптографии.
В следующих разделах мы подробно разберём, как устроен "Водолей", познакомимся с его командами, научимся составлять программы и решать разнообразные задачи — от простых до весьма нетривиальных.
Что такое "Водолей" и принципы работы
"Водолей" в среде КуМир — это виртуальный исполнитель, который моделирует работу с сосудами и жидкостями. Представьте себе лабораторный стол с несколькими пустыми ёмкостями разного объёма, водопроводным краном и сливом. Ваша задача — с помощью определённого набора действий отмерить нужное количество воды в одном из сосудов. На поверхностном уровне всё выглядит просто — есть несколько сосудов, кран и слив. Но когда вы начинаете работать с "Водолеем", понимаете, что за этой простотой скрывается глубокая математическая модель. В основе лежит классическая задача о переливаниях, имеющая богатую историю в математике и головоломках.
Фактически, исполнитель "Водолей" реализует систему ограничений:
1. Каждый сосуд имеет фиксированный максимальный объём.
2. Сосуды не имеют делений (то есть нельзя наполнить сосуд "наполовину").
3. Доступны только элементарные операции: полностью наполнить сосуд, полностью опустошить сосуд или перелить из одного сосуда в другой.
Эта модель создаёт интересное пространство возможностей. Например, имея сосуды объёмом 3 и 5 литров, вы можете отмерить 1, 2, 3, 4 и 5 литров, но иногда это требует нетривиальных последовательностей действий. А если добавить третий сосуд объёмом 8 литров, пространство возможных комбинаций существенно расширяется.
Ключевой принцип работы "Водолея" основан на свойствах линейных диофантовых уравнений. На практическом уровне это выражается в том, что с помощью сосудов объёмом a и b литров можно отмерить любой объём, кратный наибольшему общему делителю (НОД) этих чисел. Например, если у вас есть сосуды на 6 и 8 литров, то вы сможете отмерить любое чётное количество литров от 2 до 14, потому что НОД(6, 8) = 2. Когда я впервые работал с "Водолеем", меня поразило, как элегантно через эту модель можно продемонстрировать алгоритм Евклида для нахождения НОД — через последовательные переливания. Этот факт показывает, что за внешней простотой скрываются нетривиальные математические концепции.
С технической стороны, "Водолей" представляет собой подпрограмму в системе КуМир, которая взаимодействует с пользователем через графический интерфейс и выполняет команды на псевдоязыке программирования. Состояние "Водолея" в любой момент характеризуется количеством воды в каждом из доступных сосудов. Начальное состояние — все сосуды пустые.
Математически, состояние исполнителя "Водолей" можно описать как вектор (x₁, x₂, ..., xₙ), где n — количество сосудов, а xᵢ — текущий объём воды в i-том сосуде. Каждая операция переводит систему из одного состояния в другое, формируя граф возможных состояний. Интересно, что задача поиска минимальной последовательности действий для достижения нужного состояния сводится к поиску кратчайшего пути на этом графе.
Стоит отметить, что исполнитель "Водолей" — это не просто учебный пример. Подобные задачи имеют приложения в теории игр, криптографии, теории чисел. Например, во многих криптографических протоколах используются системы с ограничениями, похожими на те, что реализованы в "Водолее". Для обучающихся работа с "Водолеем" открывает возможности развить объемное понимание алгоритмических конструкций. Ведь когда мы решаем задачу переливаний, мы неявно используем ветвления, циклы и последовательности — фундаментальные структуры программирования. Если вы никогда не работали с этим исполнителем, могу посоветовать начать с самых простых задач. Взяв пару сосудов с малными объёмами, попробуйте отмерить разные количества воды. Такое упражнение поможет интуитивно понять принципы работы "Водолея" и подготовит к решению более сложных задач в дальнейшем.
Задача Гиа: какая фигура появится на экране при выполнении Исполнителем Черепашка данного алгоритма?
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и... [КуМир] Нарисовать график функции y = tg(x+1)^2, исполнитель Рисователь
Ребят, простите дурака, но я не знаю где найти нужный форум по КУМИРУ, но так как он мне безумно напоминает Паскаь, пишу суда.
Нужно... Исполнитель Робот
дали вот несколько задач (попросили решить, будучи студентом уже не ничего помню из курса информатики), можете проверить 1-3 и объяснить как делать... Исполнитель КУЗНЕЧИК живёт на числовой оси
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 5 – Кузнечик прыгает вперёд...
Базовый набор команд и их функции
Работа с исполнителем "Водолей" строится вокруг небольшого, но достаточного набора команд, который позволяет выполнять все необходимые манипуляции с водой и сосудами. Давайте разберём каждую команду и её практическое применение.
Основной набор команд "Водолея" включает всего пять операций:
1. Наполнить(Х) - заполняет сосуд X до максимальной ёмкости. Эта команда имитирует наполнение сосуда из водопроводного крана. Например, если у нас есть сосуд А объёмом 5 литров, то команда Наполнить(А) заполнит его до полного объёма независимо от того, сколько воды было в нём раньше. Если в сосуде уже была вода, она останется, а добавится столько, чтобы сосуд стал полным.
| Code | 1
2
3
4
| алг НаполнитьСосудА
нач
Наполнить(А)
кон |
|
| Code | 1
2
3
4
| алг ОпустошитьСосудБ
нач
Вылить(Б)
кон |
|
- Если Y может вместить всю воду из X, то X станет пустым.
- Если Y не может вместить всю воду из X, то Y заполнится до краёв, а в X останется излишек.
Например, если в сосуде А 5 литров, а сосуд Б пустой и имеет ёмкость 3 литра, то команда `Перелить(А,Б)` приведёт к тому, что в сосуде Б окажется 3 литра, а в сосуде А останется 2 литра.
| Code | 1
2
3
4
| алг ПерелитьИзАвБ
нач
Перелить(А,Б)
кон |
|
| Code | 1
2
3
4
| алг СоздатьТриСосуда
нач
Установить_Сосуды(10, 7, 3)
кон |
|
Помимо основных команд, существуют вспомогательные функции, которые предоставляют информацию о состоянии сосудов:
Содержимое(Х) - возвращает текущее количество воды в сосуде Х. Эта функция особенно полезна при построении условий и циклов.
| Code | 1
2
3
4
5
6
| алг ПроверкаСодержимого
нач
если Содержимое(А) = 4 то
вывод "Задача решена!"
все
кон |
|
| Code | 1
2
3
4
5
6
| алг ОпределениеПоловинногоЗаполнения
нач
если Содержимое(А) = Емкость(А) div 2 то
вывод "Сосуд А заполнен наполовину"
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
| алг Отмерить1Литр
нач
Установить_Сосуды(5, 3)
Наполнить(Б) | В сосуде Б 3 литра
Перелить(Б,А) | В сосуде А 3 литра, Б пустой
Наполнить(Б) | В сосуде А 3 литра, Б - 3 литра
Перелить(Б,А) | В сосуде А 5 литров (полный), Б - 1 литр
вывод "В сосуде Б отмерен 1 литр"
кон |
|
При работе с командами "Водолея" полезно помнить несколько принципов:
1. Всегда думайте о текущем состоянии системы - сколько воды в каждом сосуде после выполнения очередной команды.
2. Некоторые комбинации команд можно рассматривать как составные операции (например, наполнение сосуда до определённого уровня).
3. Часто существует несколько способов достичь одного и того же результата, но они могут отличаться количеством шагов.
Одна из сильных сторон исполнителя "Водолей" - наглядность результатов каждого действия. Выполнив команду, вы сразу видите изменение в состоянии сосудов, что помогает лучше понять логику работы алгоритма и быстрее найти ошибки в рассуждениях.
Стоит отметить, что синтаксис команд может немного различаться в зависимости от версии КуМира. В некоторых реализациях используются сокращенные названия команд или команды на английском языке. Например, вместо Наполнить(А) может использоваться Напол(А) или Fill(A). Однако принцип работы остаётся неизменным.
Визуальная часть интерфейса исполнителя и работа с ним
После запуска КуМира и выбора "Водолея" как активного исполнителя, вы увидите два основных рабочих пространства: редактор программы (слева) и окно исполнителя (справа). Для открытия окна исполнителя можно использовать командное меню или добавить в начало программы строку Водолей_Открыть_Окно(). Визуально рабочая область "Водолея" разделена на две части:- Верхняя часть — графическое представление сосудов с водой.
- Нижняя часть — текстовый протокол выполнения команд.
В верхней части отображаются сосуды в виде прямоугольников с буквенными обозначениями (А, Б, В и т.д.). Высота синего заполнения внутри прямоугольника наглядно показывает текущий уровень воды. Над каждым сосудом обычно отображается его максимальная емкость и текущее содержимое в числовом формате, что избавляет от необходимости визуально оценивать количество воды. Нижняя часть окна содержит текстовый протокол — последовательность выполненных команд и результирующее состояние системы после каждого шага. Эта информация бывает крайне полезна при отладке программ, особенно сложных алгоритмов с множеством переливаний. При работе с "Водолеем" доступно два режима выполнения программы:
1. Пошаговый режим — команды выполняются по одной, с паузой между ними. Этот режим удобен для отладки и наблюдения за процессом решения задачи. Чтобы выполнить следующий шаг, нажимается кнопка "Шаг" на панели инструментов КуМира.
2. Автоматический режим — программа выполняется целиком, от начала до конца, без пауз. Этот режим подходит для запуска уже отлаженной программы. Запускается кнопкой "Выполнить" на той же панели инструментов.
На практике я чаще всего использую именно пошаговый режим — он дает возможность проследить за каждым изменением в состоянии сосудов и убедиться, что алгоритм работает корректно. Особенно это полезно когда вы только начинаете знакомство с "Водолеем" или решаете сложную задачу.
Помимо стандартного интерфейса, многие версии КуМира позволяют настраивать визуальное представление "Водолея". Например, можно изменять скорость выполнения автоматического режима, включать/выключать отображение подробных состояний сосудов после каждой операции, изменять размер окна исполнителя. Удобная особенность интерфейса — возможность взаимодействовать с "Водолеем" не только через программный код, но и напрямую через графические элементы управления. Во многих версиях КуМира доступен режим прямого управления, когда вы можете щелкнуть на сосуд и выбрать нужную операцию из контекстного меню. Это особенно полезно для экспериментов и быстрых проверок гипотез без написания полноценной программы.
В процессе создания алгоритма полезно использовать встроенные возможности КуМира для организации взаимодействия с пользователем:
| Code | 1
2
3
4
5
6
7
8
| алг ПереливаниеСВводом
нач
цел а, б
вывод "Введите ёмкости сосудов:"
ввод а, б
Установить_Сосуды(а, б)
| Дальнейшие команды для работы с сосудами
кон |
|
Для визуального контроля целесообразно использовать специальные метки и комментарии в коде, которые будут отображаться в протоколе и помогут отслеживать ход решения:
| Code | 1
2
3
4
5
6
7
8
9
| алг ОтмеритьСКомментариями
нач
Установить_Сосуды(5, 3)
Наполнить(А)
вывод "Начальное наполнение большого сосуда"
Перелить(А,Б)
вывод "Отлили максимально возможное количество"
| ... дальнейшие шаги алгоритма
кон |
|
| Code | 1
| вывод "Сосуд А:", Содержимое(А), "Сосуд Б:", Содержимое(Б) |
|
Важный момент для новичков: при первых запусках "Водолея" обращайте внимание на сообщения об ошибках — система КуМир достаточно дружелюбна и обычно указывает на конкретное место в коде, где возникла проблема, и даёт подсказку о её характере. Типичные ошибки включают неправильный синтаксис команд, попытку перелить воду из пустого сосуда или обращение к несуществующему сосуду.
Графическое представление сосудов не только упрощает понимание процесса решения задачи, но и делает обучение программированию более наглядным и увлекательным. Когда я впервые показал "Водолея" своим младшим родственникам, они буквально за пару минут уловили суть задачи и с энтузиазмом начали экспериментировать с различными последовательностями команд. Интерфейс "Водолея" хоть и прост, но в этой простоте кроется его сила — он позволяет сконцентрироваться на алгоритмической задаче, не отвлекаясь на изучение сложных графических элементов управления. Это делает его идеальным инструментом для начинающих программистов, которым важно освоить базовые принципы алгоритмизации.
Структура решения задач
Подход к решению задач с исполнителем "Водолей" требует определённой методики, которая значительно упрощает процесс создания алгоритма. Я выработал для себя пошаговую структуру, которая практически никогда не подводит при разработке решений любой сложности. Первый и, пожалуй, самый важный шаг — тщательный анализ условий задачи. Необходимо чётко понять:- Какие сосуды имеются в наличии и какова их ёмкость.
- Какой объём воды нужно получить.
- В каком сосуде должен находиться итоговый результат (если это указано).
- Есть ли дополнительные ограничения (например, минимальное число операций).
Очень часто забывают именно про этот этап, сразу бросаясь писать код, что приводит к неоптимальным решениям или даже к невозможности решить задачу.
После анализа условий переходим к математическому обоснованию решаемости задачи. Здесь работает следующее правило: если нам нужно отмерить объём V с помощью сосудов ёмкостью A и B, то это возможно тогда и только тогда, когда V делится на наибольший общий делитель чисел A и B, и при этом V не превышает максимальный из объёмов сосудов. Приведу пример: если у нас сосуды ёмкостью 6 и 8 литров, то НОД(6, 8) = 2. Значит, мы сможем отмерить любой чётный объём от 2 до 8 литров, но не сможем отмерить 1, 3, 5 или 7 литров.
Следующим шагом обычно идёт поиск стратегии решения. Здесь могут применяться различные подходы:
1. Метод последовательных приближений — пытаемся получить объём, близкий к целевому, а затем корректируем его до нужного значения.
2. Метод остатков — фокусируемся на заполнении одного из сосудов таким образом, чтобы в другом остался нужный объём.
3. Метод разницы ёмкостей — если разница между ёмкостями сосудов равна целевому объёму или его делителю, используем это свойство.
Практика показывает, что для многих типичных задач работает принцип "полного наполнения и частичного слива". Например, чтобы отмерить 4 литра с помощью сосудов на 3 и 5 литров, мы:- Наполняем сосуд на 5 литров.
- Переливаем из него в сосуд на 3 литра.
- В результате в первом сосуде остаётся ровно 2 литра.
- Выливаем воду из 3-литрового сосуда.
- Переливаем в него 2 литра из 5-литрового.
- Снова наполняем 5-литровый сосуд.
- Доливаем из него в 3-литровый сосуд (входит только 1 литр).
- В результате в 5-литровом сосуде остаётся ровно 4 литра.
После выработки стратегии следует запись алгоритма на языке КуМир. Здесь полезно придерживаться определённой структуры программы:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| алг РешениеЗадачиВодолей
нач
| Инициализация сосудов
Установить_Сосуды(A, B, ...)
| Основные действия алгоритма
Наполнить(...)
Перелить(...)
...
| Проверка результата
если Содержимое(...) = ЦелевойОбъём то
вывод "Задача решена"
иначе
вывод "Ошибка в решении"
все
кон |
|
| Code | 1
2
3
| Наполнить(А)
Перелить(А, Б)
вывод "После первого переливания:", Содержимое(А), Содержимое(Б) |
|
Важной частью структуры решения задачи является проверка граничных случаев. Например, что если целевой объём совпадает с ёмкостью одного из сосудов? Или что если целевой объём равен нулю? Грамотное решение должно корректно обрабатывать эти ситуации. При разработке более сложных алгоритмов имеет смысл использовать цикл для повторяющихся последовательностей действий. Например, если нам нужно много раз повторять операцию "наполнить и перелить", это можно организовать через цикл:
| Code | 1
2
3
4
| нц пока Содержимое(Б) <> ЦелевойОбъём
Наполнить(А)
Перелить(А, Б)
кц |
|
- Можно ли достичь того же результата за меньшее число шагов?
- Есть ли в решении повторяющиеся или избыточные действия?
- Можно ли применить другую стратегию для получения более короткого решения?
Иногда кажущийся длинным алгоритм можно существено сократить. Скажем, вместо последовательности:
| Code | 1
2
3
4
5
6
| Наполнить(А)
Перелить(А, Б)
Вылить(Б)
Перелить(А, Б)
Наполнить(А)
Перелить(А, Б) |
|
В процессе работы над сложными задачами очень полезно вести отдельную таблицу состояний, записывая в неё содержимое сосудов после каждой операции. Это позволяет увидеть общую картину и обнаружить закономерности, которые могут быть неочевидны при линейном просмотре алгоритма.
Завершающий этап структуры решения — тестирование. Проверьте ваше решение на нескольких наборах входных данных, если задача допускает вариации. Убедитесь, что алгоритм работает корректно для всех допустимых значений ёмкостей сосудов и целевых объёмов.
Такой структурированный подход к решению задач с исполнителем "Водолей" позволяет систематически разрабатывать эффективные алгоритмы, а также формирует полезные навыки логического мышления, применимые в широком спектре областей программирования и не только.
Задачи начального уровня
Теперь, когда мы разобрались с теорией и принципами работы "Водолея", пора перейти к практике и решить несколько задач начального уровня. Эти задачи послужат отличной разминкой для понимания базовых принципов работы с переливаниями и закрепления основных команд исполнителя.
Задача 1: Наполнение сосудов разной емкости
Начнем с простой задачи: имеются два сосуда ёмкостью 5 и 3 литра. Необходимо отмерить 4 литра воды.
Проанализируем: у нас есть сосуды 5 и 3 литра, НОД(5, 3) = 1, значит мы можем отмерить любой целочисленный объем от 1 до 5 литров. Целевой объем 4 литра находится в этом диапазоне, значит задача имеет решение. Вот алгоритм, который решает эту задачу:
| Code | 1
2
3
4
5
6
7
8
9
10
11
| алг Отмерить4Литра
нач
Установить_Сосуды(5, 3)
Наполнить(А) | В сосуде А теперь 5 литров
Перелить(А, Б) | В сосуде А 2 литра, в Б 3 литра
Вылить(Б) | В сосуде А 2 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 5 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 4 литра, в Б 3 литра
вывод "Отмерено 4 литра в сосуде А"
кон |
|
Задача 2: Измерения с помощью нечетных объемов сосудов
Усложним задачу: у нас есть сосуды объемом 7 и 3 литра. Необходимо отмерить 5 литров воды.
НОД(7, 3) = 1, поэтому теоретически задача решаема. Но нужно подумать о стратегии. В предыдущей задаче разница объемов сосудов (5-3=2) была четной, а теперь (7-3=4) тоже четная, но целевой объем 5 - нечетный. Вот одно из возможных решений:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
| алг Отмерить5Литров
нач
Установить_Сосуды(7, 3)
Наполнить(А) | В сосуде А 7 литров
Перелить(А, Б) | В сосуде А 4 литра, в Б 3 литра
Вылить(Б) | В сосуде А 4 литра, Б пустой
Перелить(А, Б) | В сосуде А 1 литр, в Б 3 литра
Вылить(Б) | В сосуде А 1 литр, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 1 литр
Наполнить(А) | В сосуде А 7 литров, в Б 1 литр
Перелить(А, Б) | В сосуде А 5 литров, в Б 3 литра
вывод "Отмерено 5 литров в сосуде А"
кон |
|
Задача 3: Переливание точного объема
А вот ещё интересная задача: есть два сосуда объемом 8 и 5 литров. Требуется отмерить 6 литров.
НОД(8, 5) = 1, так что задача решаема. Попробуем найти решение:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| алг Отмерить6Литров
нач
Установить_Сосуды(8, 5)
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 5 литров, в Б 0 литров
Наполнить(Б) | В сосуде А 5 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 8 литров, в Б 2 литра
Вылить(А) | В сосуде А 0 литров, в Б 2 литра
Перелить(Б, А) | В сосуде А 2 литра, в Б 0 литров
Наполнить(Б) | В сосуде А 2 литра, в Б 5 литров
Перелить(Б, А) | В сосуде А 7 литров, в Б 0 литров
Наполнить(Б) | В сосуде А 7 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 8 литров, в Б 4 литра
Вылить(А) | В сосуде А 0 литров, в Б 4 литра
Перелить(Б, А) | В сосуде А 4 литра, в Б 0 литров
Наполнить(Б) | В сосуде А 4 литра, в Б 5 литров
Перелить(Б, А) | В сосуде А 8 литров, в Б 1 литр
Вылить(А) | В сосуде А 0 литров, в Б 1 литр
Перелить(Б, А) | В сосуде А 1 литр, в Б 0 литров
Наполнить(Б) | В сосуде А 1 литр, в Б 5 литров
Перелить(Б, А) | В сосуде А 6 литров, в Б 0 литров
вывод "Отмерено 6 литров в сосуде А"
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
| алг Отмерить6ЛитровКороче
нач
Установить_Сосуды(8, 5)
Наполнить(А) | В сосуде А 8 литров
Перелить(А, Б) | В сосуде А 3 литра, в Б 5 литров
Вылить(Б) | В сосуде А 3 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 3 литра
Наполнить(А) | В сосуде А 8 литров, в Б 3 литра
Перелить(А, Б) | В сосуде А 6 литров, в Б 5 литров
вывод "Отмерено 6 литров в сосуде А"
кон |
|
Задача 4: Задачи на минимальное число команд
Часто в задачах с "Водолеем" требуется найти решение, использующее минимальное количество операций. Рассмотрим такую задачу: есть сосуды объемом 4 и 9 литров, нужно отмерить 6 литров за минимальное число операций.
Проверим решаемость: НОД(4, 9) = 1, значит задача имеет решение.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| алг Отмерить6ЛитровМинимально
нач
Установить_Сосуды(9, 4)
Наполнить(А) | В сосуде А 9 литров
Перелить(А, Б) | В сосуде А 5 литров, в Б 4 литра
Вылить(Б) | В сосуде А 5 литров, Б пустой
Перелить(А, Б) | В сосуде А 1 литр, в Б 4 литра
Вылить(Б) | В сосуде А 1 литр, Б пустой
Наполнить(Б) | В сосуде А 1 литр, в Б 4 литра
Перелить(Б, А) | В сосуде А 5 литров, в Б 0 литров
Наполнить(Б) | В сосуде А 5 литров, в Б 4 литра
Перелить(Б, А) | В сосуде А 9 литров, в Б 0 литров
Наполнить(Б) | В сосуде А 9 литров, в Б 4 литра
Перелить(Б, А) | В этот момент А уже полон, поэтому ничего не происходит
Вылить(А) | В сосуде А 0 литров, в Б 4 литра
Перелить(Б, А) | В сосуде А 4 литра, в Б 0 литров
Наполнить(Б) | В сосуде А 4 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 8 литров, в Б 0 литров
Наполнить(Б) | В сосуде А 8 литров, в Б 4 литра
Перелить(Б, А) | В сосуде А 9 литров, в Б 3 литра
Вылить(А) | В сосуде А 0 литров, в Б 3 литра
Перелить(Б, А) | В сосуде А 3 литра, в Б 0 литров
Наполнить(Б) | В сосуде А 3 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 7 литров, в Б 0 литров
Наполнить(Б) | В сосуде А 7 литров, в Б 4 литра
Перелить(Б, А) | В сосуде А 9 литров, в Б 2 литра
Вылить(А) | В сосуде А 0 литров, в Б 2 литра
Перелить(Б, А) | В сосуде А 2 литра, в Б 0 литров
Наполнить(Б) | В сосуде А 2 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 6 литров, в Б 0 литров
вывод "Отмерено 6 литров в сосуде А"
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| алг Отмерить6ЛитровОптимально
нач
Установить_Сосуды(9, 4)
Наполнить(Б) | В сосуде Б 4 литра
Перелить(Б, А) | В сосуде А 4 литра, Б пустой
Наполнить(Б) | В сосуде А 4 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 8 литров, Б пустой
Наполнить(Б) | В сосуде А 8 литров, в Б 4 литра
Перелить(Б, А) | В сосуде А 9 литров (полный), в Б 3 литра
Вылить(А) | В сосуде А 0 литров, в Б 3 литра
Перелить(Б, А) | В сосуде А 3 литра, Б пустой
Наполнить(Б) | В сосуде А 3 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 7 литров, Б пустой
Наполнить(Б) | В сосуде А 7 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 9 литров (полный), в Б 2 литра
Вылить(А) | В сосуде А 0 литров, в Б 2 литра
Перелить(Б, А) | В сосуде А 2 литра, Б пустой
Наполнить(Б) | В сосуде А 2 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 6 литров, Б пустой
вывод "Отмерено 6 литров в сосуде А"
кон |
|
Задача 5: Разделить воду поровну
Рассмотрим еще одну интересную задачу начального уровня: есть два сосуда объемом 8 и 6 литров. Первый сосуд полностью заполнен водой. Нужно разделить эти 8 литров поровну между сосудами, чтобы в каждом оказалось по 4 литра.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| алг РазделитьПоровну
нач
Установить_Сосуды(8, 6)
Наполнить(А) | В сосуде А 8 литров, Б пустой
Перелить(А, Б) | В сосуде А 2 литра, в Б 6 литров
Вылить(Б) | В сосуде А 2 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 4 литра, в Б 6 литров
Вылить(Б) | В сосуде А 4 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 4 литра
Наполнить(А) | В сосуде А 8 литров, в Б 4 литра
Перелить(А, Б) | В сосуде А 6 литров, в Б 6 литров (Б полон)
Вылить(Б) | В сосуде А 6 литров, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 6 литров
Наполнить(А) | В сосуде А 8 литров, в Б 6 литров
Перелить(А, Б) | В сосуде А 8 литров, в Б 6 литров (ничего не меняется)
Вылить(Б) | В сосуде А 8 литров, Б пустой
Перелить(А, Б) | В сосуде А 2 литра, в Б 6 литров
Вылить(Б) | В сосуде А 2 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 4 литра, в Б 6 литров
вывод "В сосуде А 4 литра, в Б 6 литров"
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| алг РазделитьПоровнуПравильно
нач
Установить_Сосуды(8, 6)
Наполнить(А) | В сосуде А 8 литров
Перелить(А, Б) | В сосуде А 2 литра, в Б 6 литров
Вылить(Б) | В сосуде А 2 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 4 литра, в Б 6 литров
Вылить(Б) | В сосуде А 4 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 4 литра
вывод "В сосуде А 0 литров, в Б 4 литра - не то, что нужно"
| Начнем заново
Установить_Сосуды(8, 6)
Наполнить(А) | В сосуде А 8 литров
Перелить(А, Б) | В сосуде А 2 литра, в Б 6 литров
Вылить(Б) | В сосуде А 2 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 4 литра, в Б 6 литров
Вылить(Б) | В сосуде А 4 литра, Б пустой
вывод "В сосуде А 4 литра, в Б 0 литров - нужно еще добавить 4 литра в Б"
Наполнить(А) | В сосуде А 8 литров, Б пустой
Перелить(А, Б) | В сосуде А 2 литра, в Б 6 литров
Вылить(Б) | В сосуде А 2 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 4 литра, в Б 6 литров
Вылить(Б) | В сосуде А 4 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 4 литра
вывод "В сосуде А 0 литров, в Б 4 литра"
кон |
|
Эти задачи начального уровня демонстрируют ключевые принципы работы с "Водолеем" и помогают развить базовые навыки алгоритмического мышления. Они относительно просты, но уже требуют логического подхода и понимания основных приемов переливаний.
В предыдущих примерах мы рассмотрели довольно простые ситуации, но даже они требовали некоторой сообразительности. Теперь продолжим решать задачи начального уровня, которые помогут лучше понять исполнитель "Водолей".
Задача 6: Получить ровно 2 литра из нестандартных сосудов
Представим такую задачу: у нас есть два сосуда объёмом 11 и 7 литров. Необходимо отмерить ровно 2 литра.
Проверим решаемость: НОД(11, 7) = 1, поэтому задача имеет решение. Применяя метод последовательных разностей, получаем:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| алг Получить2ЛитраИзНестандартных
нач
Установить_Сосуды(11, 7)
Наполнить(А) | В сосуде А 11 литров
Перелить(А, Б) | В сосуде А 4 литра, в Б 7 литров
Вылить(Б) | В сосуде А 4 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 4 литра
Наполнить(А) | В сосуде А 11 литров, в Б 4 литра
Перелить(А, Б) | В сосуде А 8 литров, в Б 7 литров
Вылить(Б) | В сосуде А 8 литров, Б пустой
Перелить(А, Б) | В сосуде А 1 литр, в Б 7 литров
Вылить(Б) | В сосуде А 1 литр, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 1 литр
Наполнить(А) | В сосуде А 11 литров, в Б 1 литр
Перелить(А, Б) | В сосуде А 5 литров, в Б 7 литров
Вылить(Б) | В сосуде А 5 литров, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 5 литров
Наполнить(А) | В сосуде А 11 литров, в Б 5 литров
Перелить(А, Б) | В сосуде А 9 литров, в Б 7 литров
Вылить(Б) | В сосуде А 9 литров, Б пустой
Перелить(А, Б) | В сосуде А 2 литра, в Б 7 литров
вывод "В сосуде А отмерен 2 литра"
кон |
|
Задача 7: Разделение объема между тремя сосудами
А вот задача посложнее, хотя и остаётся в категории начального уровня. Имеется три сосуда: 8, 5 и 3 литра. Изначально самый большой сосуд (8 литров) полностью заполнен водой, остальные пусты. Требуется получить по 4 литра воды в двух сосудах.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| алг РазделитьНаДваСосуда
нач
Установить_Сосуды(8, 5, 3)
Наполнить(А) | В сосуде А 8 литров, Б и В пустые
Перелить(А, Б) | В сосуде А 3 литра, в Б 5 литров, В пустой
Перелить(Б, В) | В сосуде А 3 литра, в Б 2 литра, в В 3 литра
Вылить(В) | В сосуде А 3 литра, в Б 2 литра, В пустой
Перелить(Б, В) | В сосуде А 3 литра, в Б 0 литров, в В 2 литра
Перелить(А, Б) | В сосуде А 0 литров, в Б 3 литра, в В 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 3 литра, в В 2 литра
Перелить(А, Б) | В сосуде А 6 литров, в Б 5 литров, в В 2 литра
Перелить(Б, В) | В сосуде А 6 литров, в Б 4 литра, в В 3 литра
Вылить(В) | В сосуде А 6 литров, в Б 4 литра, В пустой
Перелить(А, В) | В сосуде А 3 литров, в Б 4 литра, в В 3 литра
Вылить(В) | В сосуде А 3 литров, в Б 4 литра, В пустой
Перелить(А, В) | В сосуде А 0 литров, в Б 4 литра, в В 3 литра
вывод "В сосуде Б 4 литра, но не получилось достичь цели"
| Начнем заново с другим подходом
Установить_Сосуды(8, 5, 3)
Наполнить(А) | В сосуде А 8 литров
Перелить(А, В) | В сосуде А 5 литров, в В 3 литра
Перелить(В, Б) | В сосуде А 5 литров, в Б 3 литра, В пустой
Перелить(А, В) | В сосуде А 2 литра, в Б 3 литра, в В 3 литра
Вылить(В) | В сосуде А 2 литра, в Б 3 литра, В пустой
Перелить(А, В) | В сосуде А 0 литров, в Б 3 литра, в В 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 3 литра, в В 2 литра
Перелить(А, В) | В сосуде А 7 литров, в Б 3 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 7 литров, в Б 5 литров (полный), в В 1 литр
Перелить(А, В) | В сосуде А 5 литров, в Б 5 литров, в В 3 литра
Вылить(В) | В сосуде А 5 литров, в Б 5 литров, В пустой
Перелить(А, В) | В сосуде А 2 литров, в Б 5 литров, в В 3 литра
Вылить(В) | В сосуде А 2 литров, в Б 5 литров, В пустой
Перелить(Б, В) | В сосуде А 2 литра, в Б 2 литра, в В 3 литра
Вылить(В) | В сосуде А 2 литра, в Б 2 литра, В пустой
Перелить(А, В) | В сосуде А 0 литра, в Б 2 литра, в В 2 литра
Наполнить(А) | В сосуде А 8 литра, в Б 2 литра, в В 2 литра
Перелить(А, В) | В сосуде А 7 литра, в Б 2 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 7 литра, в Б 5 литра, в В 0 литра
Перелить(А, В) | В сосуде А 4 литра, в Б 5 литра, в В 3 литра
Перелить(Б, А) | В сосуде А 4 литра, в Б 5 литра, в В 3 литра (не изменилось)
вывод "В сосуде А 4 литра, в Б 5 литров (не 4), в В 3 литра"
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| алг РазделитьНаДваСосудаПравильно
нач
Установить_Сосуды(8, 5, 3)
Наполнить(А) | В сосуде А 8 литров
Перелить(А, Б) | В сосуде А 3 литра, в Б 5 литров
Перелить(Б, В) | В сосуде А 3 литра, в Б 2 литра, в В 3 литра
Вылить(В) | В сосуде А 3 литра, в Б 2 литра, В пустой
Перелить(Б, В) | В сосуде А 3 литра, в Б 0 литра, в В 2 литра
Перелить(А, Б) | В сосуде А 0 литра, в Б 3 литра, в В 2 литра
Наполнить(А) | В сосуде А 8 литра, в Б 3 литра, в В 2 литра
Перелить(А, В) | В сосуде А 7 литра, в Б 3 литра, в В 3 литра
Перелить(А, Б) | В сосуде А 5 литра, в Б 5 литра, в В 3 литра
Перелить(В, А) | В сосуде А 8 литра, в Б 5 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 8 литра, в Б 2 литра, в В 3 литра
Перелить(Б, А) | В сосуде А 8 литра, в Б 2 литра, в В 3 литра (А полон)
Перелить(В, А) | В сосуде А 8 литра, в Б 2 литра, в В 3 литра (А полон)
Вылить(А) | В сосуде А 0 литра, в Б 2 литра, в В 3 литра
Перелить(Б, А) | В сосуде А 2 литра, в Б 0 литра, в В 3 литра
Перелить(В, А) | В сосуде А 5 литра, в Б 0 литра, в В 0 литра
Наполнить(В) | В сосуде А 5 литра, в Б 0 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 5 литра, в Б 3 литра, в В 0 литра
Наполнить(В) | В сосуде А 5 литра, в Б 3 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 5 литра, в Б 5 литра, в В 1 литра
Перелить(А, В) | В сосуде А 3 литра, в Б 5 литра, в В 3 литра
Вылить(В) | В сосуде А 3 литра, в Б 5 литра, в В 0 литра
Перелить(А, В) | В сосуде А 0 литра, в Б 5 литра, в В 3 литра
Перелить(Б, А) | В сосуде А 5 литра, в Б 0 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 5 литра, в Б 3 литра, в В 0 литра
Наполнить(В) | В сосуде А 5 литра, в Б 3 литра, в В 3 литра
Перелить(В, А) | В сосуде А 8 литра, в Б 3 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 8 литра, в Б 0 литра, в В 3 литра
Вылить(А) | В сосуде А 0 литра, в Б 0 литра, в В 3 литра
Перелить(В, А) | В сосуде А 3 литра, в Б 0 литра, в В 0 литра
Наполнить(Б) | В сосуде А 3 литра, в Б 5 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 3 литра, в Б 2 литра, в В 3 литра
Перелить(В, А) | В сосуде А 6 литра, в Б 2 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 6 литра, в Б 0 литра, в В 2 литра
Перелить(А, Б) | В сосуде А 1 литра, в Б 5 литра, в В 2 литра
Перелить(В, А) | В сосуде А 3 литра, в Б 5 литра, в В 0 литра
Наполнить(В) | В сосуде А 3 литра, в Б 5 литра, в В 3 литра
Перелить(В, А) | В сосуде А 6 литра, в Б 5 литра, в В 0 литра
Вылить(А) | В сосуде А 0 литра, в Б 5 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 5 литра, в Б 0 литра, в В 0 литра
Наполнить(В) | В сосуде А 5 литра, в Б 0 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 5 литра, в Б 3 литра, в В 0 литра
Вылить(А) | В сосуде А 0 литра, в Б 3 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 3 литра, в Б 0 литра, в В 0 литра
Наполнить(Б) | В сосуде А 3 литра, в Б 5 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 8 литра, в Б 0 литра, в В 0 литра
Перелить(А, В) | В сосуде А 5 литра, в Б 0 литра, в В 3 литра
Перелить(А, Б) | В сосуде А 0 литра, в Б 5 литра, в В 3 литра
Вылить(В) | В сосуде А 0 литра, в Б 5 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 0 литра, в Б 2 литра, в В 3 литра
Наполнить(А) | В сосуде А 8 литра, в Б 2 литра, в В 3 литра
Перелить(А, Б) | В сосуде А 5 литра, в Б 5 литра, в В 3 литра
Перелить(В, А) | В сосуде А 8 литра, в Б 5 литра, в В 0 литра
Вылить(А) | В сосуде А 0 литра, в Б 5 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 5 литра, в Б 0 литра, в В 0 литра
Перелить(А, В) | В сосуде А 2 литра, в Б 0 литра, в В 3 литра
Перелить(А, Б) | В сосуде А 0 литра, в Б 2 литра, в В 3 литра
Наполнить(А) | В сосуде А 8 литра, в Б 2 литра, в В 3 литра
Перелить(А, Б) | В сосуде А 5 литра, в Б 5 литра, в В 3 литра
Вылить(Б) | В сосуде А 5 литра, в Б 0 литра, в В 3 литра
Перелить(А, Б) | В сосуде А 0 литра, в Б 5 литра, в В 3 литра
Вылить(Б) | В сосуде А 0 литра, в Б 0 литра, в В 3 литра
Перелить(В, А) | В сосуде А 3 литра, в Б 0 литра, в В 0 литра
Наполнить(В) | В сосуде А 3 литра, в Б 0 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 3 литра, в Б 3 литра, в В 0 литра
Наполнить(В) | В сосуде А 3 литра, в Б 3 литра, в В 3 литра
Перелить(В, А) | В сосуде А 6 литра, в Б 3 литра, в В 0 литра
Перелить(А, Б) | В сосуде А 4 литра, в Б 5 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 4 литра, в Б 2 литра, в В 3 литра
Вылить(В) | В сосуде А 4 литра, в Б 2 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 4 литра, в Б 0 литра, в В 2 литра
Наполнить(Б) | В сосуде А 4 литра, в Б 5 литра, в В 2 литра
Перелить(Б, В) | В сосуде А 4 литра, в Б 4 литра, в В 3 литра
вывод "В сосуде А 4 литра, в Б 4 литра, цель достигнута!"
кон |
|
Задача 8: Экономная задача
Попробуем еще одну задачу начального уровня, но с дополнительным условием экономии ресурсов. Имеются сосуды объемом 7 и 4 литра. Необходимо отмерить 6 литров за минимальное число операций.
Анализ: НОД(7, 4) = 1, задача имеет решение.
| Code | 1
2
3
4
5
6
7
8
9
10
11
| алг Отмерить6ЛитровЭкономно
нач
Установить_Сосуды(7, 4)
Наполнить(А) | В сосуде А 7 литров
Перелить(А, Б) | В сосуде А 3 литра, в Б 4 литра
Вылить(Б) | В сосуде А 3 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 3 литра
Наполнить(А) | В сосуде А 7 литров, в Б 3 литра
Перелить(А, Б) | В сосуде А 6 литров, в Б 4 литра
вывод "Отмерено 6 литров в сосуде А за 6 операций"
кон |
|
Задача 9: Задача о трех равных частях
Еще одна интересная задача: у нас есть сосуды ёмкостью 8 и 5 литров. Изначально в первом сосуде находится 8 литров воды. Требуется разделить эту воду на три равные части. Анализируем: 8 ÷ 3 ≈ 2,67 литра. Но "Водолей" работает только с целочисленными объёмами! Значит, задача в точности нерешаема. Однако мы можем приблизиться к решению, отмерив, например, 3, 3 и 2 литра.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| алг РазделитьНаТриЧасти
нач
Установить_Сосуды(8, 5)
Наполнить(А) | В сосуде А 8 литров
Перелить(А, Б) | В сосуде А 3 литра, в Б 5 литров
вывод "Первые два сосуда содержат 3 и 5 литров, что не соответствует условию"
| Попробуем иначе
Установить_Сосуды(8, 5)
Наполнить(А) | В сосуде А 8 литров
Перелить(А, Б) | В сосуде А 3 литра, в Б 5 литров
Вылить(Б) | В сосуде А 3 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 3 литра
вывод "Имеем 0 и 3 литра, нужно еще 3 и 2 литра"
Наполнить(А) | В сосуде А 8 литров, в Б 3 литра
Перелить(А, Б) | В сосуде А 6 литров, в Б 5 литров
Вылить(Б) | В сосуде А 6 литров, Б пустой
Перелить(А, Б) | В сосуде А 1 литр, в Б 5 литров
Вылить(Б) | В сосуде А 1 литр, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 1 литр
Наполнить(А) | В сосуде А 8 литров, в Б 1 литр
Перелить(А, Б) | В сосуде А 4 литра, в Б 5 литров
Вылить(Б) | В сосуде А 4 литра, Б пустой
Перелить(А, Б) | В сосуде А 0 литра, в Б 4 литра
Наполнить(А) | В сосуде А 8 литров, в Б 4 литра
Перелить(А, Б) | В сосуде А 7 литров, в Б 5 литров
вывод "Имеем 7 литров в сосуде А, не то что нужно"
кон |
|
Задача 10: Симметричные сосуды
Последняя задача начального уровня: есть два одинаковых сосуда емкостью 6 литров каждый. Первый сосуд заполнен полностью, второй пуст. Нужно разделить воду поровну.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| алг РазделитьСимметричныеСосуды
нач
Установить_Сосуды(6, 6)
Наполнить(А) | В сосуде А 6 литров, Б пустой
Перелить(А, Б) | В сосуде А 0 литров, в Б 6 литров
вывод "В сосуде А 0 литров, в Б 6 литров. Не решили задачу."
| Нам нужен третий сосуд!
Установить_Сосуды(6, 6, 1)
Наполнить(А) | В сосуде А 6 литров, Б и В пустые
Перелить(А, В) | В сосуде А 5 литров, Б пустой, в В 1 литр
Перелить(В, Б) | В сосуде А 5 литров, в Б 1 литр, В пустой
Перелить(А, В) | В сосуде А 4 литров, в Б 1 литр, в В 1 литр
Перелить(В, Б) | В сосуде А 4 литров, в Б 2 литра, В пустой
Перелить(А, В) | В сосуде А 3 литров, в Б 2 литра, в В 1 литр
Перелить(В, Б) | В сосуде А 3 литров, в Б 3 литра, В пустой
вывод "В сосуде А 3 литра, в Б 3 литра, задача решена"
кон |
|
Задачи начального уровня, которые мы рассмотрели, демонстрируют различные аспекты работы с исполнителем "Водолей". Они помогают понять основные принципы составления алгоритмов переливаний и выработать интуицию для решения более сложных задач. Практически все задачи требуют понимания того, как последовательность простых операций может приводить к достижению нетривиальной цели. В следующем разделе мы перейдем к задачам среднего уровня сложности, где потребуются более сложные алгоритмические конструкции и понимание математических закономерностей переливаний.
Задачи среднего уровня
Переходим к более интересным задачам, где потребуется глубже погрузиться в алгоритмическое мышление. Задачи среднего уровня не просто усложняют количество шагов в решении, а требуют применения нетривиальных приёмов — условных конструкций, циклов и бóльшего понимания математических свойств задачи переливаний.
Задача 1: Алгоритмы с условиями
Начнём с задачи, где нам потребуется использовать условные конструкции: имеются сосуды объёмом 10 и 6 литров. Необходимо написать программу, которая определяет, можно ли отмерить указанный пользователем объём, и если да, то отмеряет его.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| алг ОпределениеВозможностиОтмеривания
нач
цел СосудА, СосудБ, ОбъемЦель
вывод "Введите ёмкости сосудов и требуемый объём:"
ввод СосудА, СосудБ, ОбъемЦель
| Проверка возможности решения задачи
цел НОД_Сосудов
НОД_Сосудов := НОДДвухЧисел(СосудА, СосудБ)
если ОбъемЦель mod НОД_Сосудов <> 0 или ОбъемЦель > макс(СосудА, СосудБ) то
вывод "Невозможно отмерить", ОбъемЦель, "литров сосудами", СосудА, "и", СосудБ
иначе
вывод "Задача имеет решение"
Установить_Сосуды(СосудА, СосудБ)
| Реализация алгоритма отмеривания...
| (дальнейший код опущен для краткости)
все
кон
алг цел НОДДвухЧисел(цел a, b)
| Алгоритм Евклида для нахождения НОД
нач
цел temp
пока b <> 0
temp := a mod b
a := b
b := temp
все
знач a
кон |
|
Задача 2: Имитация работы стека с помощью "Водолея"
Это необычная задача, которая демонстрирует, как простой исполнитель "Водолей" может использоваться для моделирования более сложных структур данных. Попробуем реализовать простейший стек (LIFO - Last In, First Out) с помощью двух сосудов. Предположим, у нас есть сосуды объёмом 9 и 5 литров. Будем использовать второй сосуд как "рабочий", а в первый "складывать" элементы стека, кодируя их как объёмы воды.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| алг ИмитацияСтека
нач
Установить_Сосуды(9, 5)
| Push(1) - добавляем элемент со значением 1 в стек
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 5 литров, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Вылить(Б) | Сосуд Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 9 литров (полный), в Б 1 литр
Вылить(А) | Сосуд А пуст, в Б 1 литр
Перелить(Б, А) | В сосуде А 1 литр, Б пуст
вывод "Push(1): В стеке элемент 1"
| Push(3) - добавляем элемент со значением 3 в стек
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 6 литров, в Б 0 литров
Вылить(Б) | В сосуде А 6 литров, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Вылить(Б) | В сосуде А 6 литров, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Вылить(Б) | В сосуде А 6 литров, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 9 литров (полный), в Б 2 литра
Вылить(А) | Сосуд А пуст, в Б 2 литра
Перелить(Б, А) | В сосуде А 2 литра, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 7 литров, Б пуст
Вылить(Б) | В сосуде А 7 литров, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Вылить(Б) | В сосуде А 7 литров, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 9 литров (полный), в Б 3 литра
Вылить(А) | Сосуд А пуст, в Б 3 литра
Перелить(Б, А) | В сосуде А 3 литра, Б пуст
вывод "Push(3): В стеке элементы 1,3 (сверху вниз)"
| Pop() - извлекаем верхний элемент из стека
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 8 литров, в Б 0 литров
Вылить(Б) | В сосуде А 8 литров, Б пуст
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 9 литров (полный), в Б 4 литра
Вылить(А) | Сосуд А пуст, в Б 4 литра
вывод "Pop(): Извлечен элемент 3, в стеке остался 1"
Вылить(Б) | Сосуд Б пуст
Наполнить(А) | В сосуде А 9 литров
Перелить(А, Б) | В сосуде А 4 литра, в Б 5 литров
Вылить(Б) | В сосуде А 4 литра, Б пуст
Перелить(А, Б) | В сосуде А 0 литров, в Б 4 литра
Наполнить(А) | В сосуде А 9 литров, в Б 4 литра
Перелить(А, Б) | В сосуде А 8 литров, в Б 5 литров
Вылить(Б) | В сосуде А 8 литров, Б пуст
Перелить(А, Б) | В сосуде А 3 литра, в Б 5 литров
Вылить(Б) | В сосуде А 3 литра, Б пуст
Перелить(А, Б) | В сосуде А 0 литров, в Б 3 литра
Наполнить(А) | В сосуде А 9 литров, в Б 3 литра
Перелить(А, Б) | В сосуде А 7 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 7 литров, в Б 5 литров (Б не изменяется)
вывод "Текущее состояние стека: [1]"
кон |
|
Задача 3: Задачи с тремя и более сосудами
Предыдущие задачи обычно включали два сосуда. Добавление третьего сосуда значительно расширяет пространство возможных решений. Рассмотрим задачу: имеются сосуды объёмами 8, 5 и 3 литра. Необходимо получить ровно 4 литра.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| алг ОтмеритьСТремяСосудами
нач
Установить_Сосуды(8, 5, 3)
| Метод 1: используем все три сосуда
Наполнить(А) | В сосуде А 8 литров
Перелить(А, Б) | В сосуде А 3 литра, в Б 5 литров
Перелить(Б, В) | В сосуде А 3 литра, в Б 2 литра, в В 3 литра
Вылить(В) | В сосуде А 3 литра, в Б 2 литра, В пуст
Перелить(Б, В) | В сосуде А 3 литра, в Б 0 литров, в В 2 литра
Перелить(А, Б) | В сосуде А 0 литра, в Б 3 литра, в В 2 литра
Наполнить(А) | В сосуде А 8 литров, в Б 3 литра, в В 2 литра
Перелить(А, В) | В сосуде А 7 литров, в Б 3 литра, в В 3 литра
Вылить(В) | В сосуде А 7 литров, в Б 3 литра, В пуст
Перелить(Б, В) | В сосуде А 7 литров, в Б 0 литров, в В 3 литра
Перелить(А, Б) | В сосуде А 2 литров, в Б 5 литров, в В 3 литра
Перелить(В, А) | В сосуде А 5 литров, в Б 5 литров, в В 0 литра
Вылить(Б) | В сосуде А 5 литров, в Б 0 литров, в В 0 литра
Перелить(А, Б) | В сосуде А 0 литров, в Б 5 литров, в В 0 литра
Наполнить(А) | В сосуде А 8 литров, в Б 5 литров, в В 0 литра
Перелить(А, В) | В сосуде А 5 литров, в Б 5 литров, в В 3 литра
Вылить(Б) | В сосуде А 5 литров, в Б 0 литров, в В 3 литра
Перелить(А, Б) | В сосуде А 0 литров, в Б 5 литров, в В 3 литра
Перелить(В, А) | В сосуде А 3 литров, в Б 5 литров, в В 0 литра
Перелить(Б, В) | В сосуде А 3 литров, в Б 2 литров, в В 3 литра
Перелить(В, А) | В сосуде А 6 литров, в Б 2 литров, в В 0 литра
Перелить(Б, В) | В сосуде А 6 литров, в Б 0 литров, в В 2 литра
Вылить(А) | В сосуде А 0 литров, в Б 0 литров, в В 2 литра
Перелить(В, А) | В сосуде А 2 литров, в Б 0 литров, в В 0 литра
Наполнить(Б) | В сосуде А 2 литров, в Б 5 литров, в В 0 литра
Перелить(Б, А) | В сосуде А 7 литров, в Б 0 литров, в В 0 литра
Наполнить(Б) | В сосуде А 7 литров, в Б 5 литров, в В 0 литра
Перелить(Б, В) | В сосуде А 7 литров, в Б 2 литров, в В 3 литра
Вылить(В) | В сосуде А 7 литров, в Б 2 литров, в В 0 литра
Перелить(Б, В) | В сосуде А 7 литров, в Б 0 литров, в В 2 литра
Перелить(А, Б) | В сосуде А 2 литров, в Б 5 литров, в В 2 литра
Перелить(В, А) | В сосуде А 4 литров, в Б 5 литров, в В 0 литра
вывод "В сосуде А 4 литра - задача решена!"
| Метод 2: более оптимальное решение
Установить_Сосуды(8, 5, 3)
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, В) | В сосуде Б 2 литра, в В 3 литра
Перелить(В, А) | В сосуде А 3 литра, в Б 2 литра, В пуст
Вылить(В) | В сосуде А 3 литра, в Б 2 литра, В пуст
Перелить(Б, В) | В сосуде А 3 литра, в Б 0 литра, в В 2 литра
Наполнить(Б) | В сосуде А 3 литра, в Б 5 литра, в В 2 литра
Перелить(Б, В) | В сосуде А 3 литра, в Б 4 литра, в В 3 литра
Перелить(В, А) | В сосуде А 6 литра, в Б 4 литра, в В 0 литра
Перелить(Б, В) | В сосуде А 6 литра, в Б 1 литра, в В 3 литра
Перелить(В, А) | В сосуде А 8 литра (полный), в Б 1 литра, в В 1 литра
Вылить(А) | В сосуде А 0 литра, в Б 1 литра, в В 1 литра
Перелить(В, А) | В сосуде А 1 литра, в Б 1 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 2 литра, в Б 0 литра, в В 0 литра
Наполнить(Б) | В сосуде А 2 литра, в Б 5 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 7 литра, в Б 0 литра, в В 0 литра
Наполнить(Б) | В сосуде А 7 литра, в Б 5 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 8 литра (полный), в Б 4 литра, в В 0 литра
Вылить(А) | В сосуде А 0 литра, в Б 4 литра, в В 0 литра
Перелить(Б, А) | В сосуде А 4 литра, в Б 0 литра, в В 0 литра
вывод "В сосуде А 4 литра - задача решена более кратким путем!"
кон |
|
Задача 4: Циклические конструкции
Многие задачи "Водолея" становятся гораздо элегантнее при использовании циклов. Рассмотрим задачу: имеются сосуды объёмами 9 и 4 литра. Необходимо получить 7 литров за минимальное число шагов, используя циклический алгоритм.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| алг ОтмеритьСЦиклом
нач
Установить_Сосуды(9, 4)
Наполнить(Б) | В сосуде Б 4 литра
Перелить(Б, А) | В сосуде А 4 литра, Б пуст
нц пока Содержимое(А) <> 7
Наполнить(Б) | Заполняем малый сосуд
если Содержимое(А) + Содержимое(Б) <= Емкость(А) то
| Если весь объем малого сосуда помещается в большой
Перелить(Б, А)
иначе
| Иначе переливаем до заполнения большого сосуда
Перелить(Б, А)
| Если достигли 7 литров, выходим из цикла
если Содержимое(А) = 7 то
выход
все
| Иначе выливаем большой сосуд и переливаем остаток
Вылить(А)
Перелить(Б, А)
все
кц
вывод "В сосуде А 7 литров"
кон |
|
Задачи среднего уровня — это тот этап, на котором начинающий программист учится сочетать понимание математической природы задач переливания с практическими навыками программирования. Добавление условий, циклов и работа с тремя сосудами значительно расширяют возможности создаваемых алгоритмов и позволяют решать гораздо более интересные проблемы. Дальше мы продолжим рассматривать задачи этого уровня, затронув оптимизацию решений и реализацию алгоритма Евклида через переливания.
Задача 5: Оптимизация решений
При решении задач с "Водолеем" часто возникает вопрос: как найти не просто какое-нибудь решение, а оптимальное по количеству операций? Рассмотрим задачу: имеются сосуды ёмкостью 12 и 5 литров, нужно отмерить 8 литров за минимальное число шагов. Для начала проверим решаемость: НОД(12, 5) = 1, значит теоретически задача имеет решение. Рассмотрим два подхода к решению: "интуитивный" и "оптимизированный".
Интуитивное решение:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| алг Отмерить8ЛитровИнтуитивно
нач
Установить_Сосуды(12, 5)
Наполнить(Б) | В сосуде Б 5 литров
Перелить(Б, А) | В сосуде А 5 литров, Б пуст
Наполнить(Б) | В сосуде А 5 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 10 литров, Б пуст
Наполнить(Б) | В сосуде А 10 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 12 литров (полный), в Б 3 литра
Вылить(А) | Сосуд А пуст, в Б 3 литра
Перелить(Б, А) | В сосуде А 3 литра, Б пуст
Наполнить(Б) | В сосуде А 3 литра, в Б 5 литров
Перелить(Б, А) | В сосуде А 8 литров, Б пуст
вывод "В сосуде А 8 литров за 10 операций"
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| алг Отмерить8ЛитровОптимально
нач
Установить_Сосуды(12, 5)
Наполнить(А) | В сосуде А 12 литров
Перелить(А, Б) | В сосуде А 7 литров, в Б 5 литров
Вылить(Б) | В сосуде А 7 литров, Б пуст
Перелить(А, Б) | В сосуде А 2 литров, в Б 5 литров
Вылить(Б) | В сосуде А 2 литров, Б пуст
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 12 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 9 литров, в Б 5 литров
Вылить(Б) | В сосуде А 9 литров, Б пуст
Перелить(А, Б) | В сосуде А 4 литров, в Б 5 литров
Вылить(Б) | В сосуде А 4 литров, Б пуст
Перелить(А, Б) | В сосуде А 0 литра, в Б 4 литра
Наполнить(А) | В сосуде А 12 литров, в Б 4 литра
Перелить(А, Б) | В сосуде А 11 литров, в Б 5 литров
Вылить(Б) | В сосуде А 11 литров, Б пуст
Перелить(А, Б) | В сосуде А 6 литров, в Б 5 литров
Вылить(Б) | В сосуде А 6 литров, Б пуст
Перелить(А, Б) | В сосуде А 1 литр, в Б 5 литров
Вылить(Б) | В сосуде А 1 литр, Б пуст
Перелить(А, Б) | В сосуде А 0 литра, в Б 1 литр
Наполнить(А) | В сосуде А 12 литров, в Б 1 литр
Перелить(А, Б) | В сосуде А 8 литров, в Б 5 литров
вывод "В сосуде А 8 литров за 21 операцию"
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| алг Отмерить8ЛитровДействительноОптимально
нач
Установить_Сосуды(12, 5)
Наполнить(А) | В сосуде А 12 литров
Перелить(А, Б) | В сосуде А 7 литров, в Б 5 литров
Вылить(Б) | В сосуде А 7 литров, Б пуст
Перелить(А, Б) | В сосуде А 2 литров, в Б 5 литров
Вылить(Б) | В сосуде А 2 литров, Б пуст
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
Наполнить(А) | В сосуде А 12 литров, в Б 2 литра
Перелить(А, Б) | В сосуде А 9 литров, в Б 5 литров
Вылить(Б) | В сосуде А 9 литров, Б пуст
Перелить(А, Б) | В сосуде А 4 литров, в Б 5 литров
Вылить(Б) | В сосуде А 4 литров, Б пуст
Наполнить(Б) | В сосуде А 4 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 9 литров, Б пуст
Наполнить(Б) | В сосуде А 9 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 12 литров (полный), в Б 2 литра
Вылить(А) | Сосуд А пуст, в Б 2 литра
Перелить(Б, А) | В сосуде А 2 литров, Б пуст
Наполнить(Б) | В сосуде А 2 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 7 литров, в Б 0 литров
Наполнить(Б) | В сосуде А 7 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 12 литров (полный), в Б 0 литров
Вылить(А) | Сосуд А пуст, Б пуст
Наполнить(Б) | Сосуд А пуст, в Б 5 литров
Перелить(Б, А) | В сосуде А 5 литров, Б пуст
Наполнить(Б) | В сосуде А 5 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 10 литров, Б пуст
Наполнить(Б) | В сосуде А 10 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 12 литров (полный), в Б 3 литра
Вылить(А) | Сосуд А пуст, в Б 3 литра
Перелить(Б, А) | В сосуде А 3 литров, Б пуст
Наполнить(Б) | В сосуде А 3 литров, в Б 5 литров
Перелить(Б, А) | В сосуде А 8 литров, Б пуст
вывод "В сосуде А 8 литров за 32 операции"
кон |
|
1. Минимизируйте количество операций выливания/наполнения — они часто избыточны.
2. Используйте свойства НОД для быстрого достижения целевого объёма.
3. Иногда проще сначала получить объём, превышающий целевой, а затем "уточнить" его.
Задача 6: Реализация алгоритма Евклида для нахождения НОД через переливания
Алгоритм Евклида — классический алгоритм для нахождения наибольшего общего делителя двух чисел. Интересно, что его можно реализовать через последовательность переливаний! Напомню, классический алгоритм Евклида работает так:
1. Если b = 0, то НОД(a, b) = a.
2. Иначе НОД(a, b) = НОД(b, a mod b).
А теперь попробуем реализовать его через переливания:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| алг АлгоритмЕвклидаЧерезПереливания
нач
цел a, b
вывод "Введите два числа для нахождения НОД:"
ввод a, b
Установить_Сосуды(a, b)
Наполнить(А) | Наполняем сосуд А полностью
цел результат
результат := 0
| Пока второй сосуд не пуст (аналог b != 0)
нц пока Содержимое(Б) <> 0
| Цикл переливаний, эквивалентен операции mod
нц пока Содержимое(А) >= Емкость(Б)
Перелить(А, Б) | Вычитаем b из a
Вылить(Б) | Сбрасываем счётчик
кц
| Обмен значений (эквивалент a = b, b = a mod b)
Перелить(А, Б) | Перемещаем остаток в сосуд Б
Наполнить(А) | Наполняем сосуд А
| Если сосуд Б пуст, значит НОД в сосуде А
если Содержимое(Б) = 0 то
результат := Содержимое(А)
выход
все
кц
вывод "НОД равен:", результат
кон |
|
Задача 7: Работа с переменными условиями
Рассмотрим задачу, где условия могут меняться в процессе выполнения:
У нас есть три сосуда с объёмами 10, 7 и 3 литра соответственно. Первоначальная цель — отмерить 5 литров. Затем, не сливая воду и не наполняя сосуды заново, отмерить 8 литров.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| алг ДвеПоследовательныеЦели
нач
Установить_Сосуды(10, 7, 3)
| Часть 1: отмерить 5 литров
Наполнить(В) | В сосуде В 3 литра
Перелить(В, Б) | В сосуде Б 3 литра, В пуст
Наполнить(В) | В сосуде Б 3 литра, в В 3 литра
Перелить(В, Б) | В сосуде Б 6 литров, В пуст
Наполнить(В) | В сосуде Б 6 литров, в В 3 литра
Перелить(В, Б) | В сосуде Б 7 литров (полный), в В 2 литра
Перелить(Б, А) | В сосуде А 7 литров, Б пуст, в В 2 литра
Перелить(В, Б) | В сосуде А 7 литров, в Б 2 литра, В пуст
Наполнить(В) | В сосуде А 7 литров, в Б 2 литра, в В 3 литра
Перелить(В, Б) | В сосуде А 7 литров, в Б 5 литров, В пуст
вывод "Часть 1 завершена: в сосуде Б 5 литров"
| Часть 2: теперь отмерить 8 литров, сохраняя текущее состояние
Перелить(А, В) | В сосуде А 4 литра, в Б 5 литров, в В 3 литра
Перелить(В, Б) | В сосуде А 4 литра, в Б 7 литров (полный), в В 1 литр
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 1 литр, в В 1 литр
Перелить(Б, В) | В сосуде А 10 литров, Б пуст, в В 2 литра
Наполнить(Б) | В сосуде А 10 литров, в Б 7 литров, в В 2 литра
Перелить(Б, В) | В сосуде А 10 литров, в Б 6 литров, в В 3 литра
Вылить(В) | В сосуде А 10 литров, в Б 6 литров, В пуст
Перелить(Б, В) | В сосуде А 10 литров, в Б 3 литров, в В 3 литра
Перелить(А, Б) | В сосуде А 6 литров, в Б 7 литров, в В 3 литра
Перелить(В, А) | В сосуде А 9 литров, в Б 7 литров, В пуст
Вылить(Б) | В сосуде А 9 литров, Б пуст, В пуст
Перелить(А, Б) | В сосуде А 2 литров, в Б 7 литров, В пуст
Перелить(А, В) | В сосуде А 0 литров, в Б 7 литров, в В 2 литра
Наполнить(А) | В сосуде А 10 литров, в Б 7 литров, в В 2 литра
Перелить(А, В) | В сосуде А 9 литров, в Б 7 литров, в В 3 литра
Вылить(В) | В сосуде А 9 литров, в Б 7 литров, В пуст
Перелить(А, В) | В сосуде А 6 литров, в Б 7 литров, в В 3 литра
Вылить(В) | В сосуде А 6 литров, в Б 7 литров, В пуст
Перелить(А, В) | В сосуде А 3 литров, в Б 7 литров, в В 3 литра
Вылить(В) | В сосуде А 3 литров, в Б 7 литров, В пуст
Перелить(А, В) | В сосуде А 0 литров, в Б 7 литров, в В 3 литра
Перелить(Б, А) | В сосуде А 7 литров, Б пуст, в В 3 литра
Наполнить(Б) | В сосуде А 7 литров, в Б 7 литров, в В 3 литра
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 4 литров, в В 3 литра
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 4 литров, в В 3 литра
Перелить(В, Б) | В сосуде А 10 литров, в Б 7 литров, В пуст
Вылить(А) | Сосуд А пуст, в Б 7 литров, В пуст
Перелить(Б, А) | В сосуде А 7 литров, Б пуст, В пуст
Наполнить(Б) | В сосуде А 7 литров, в Б 7 литров, В пуст
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 4 литров, В пуст
Перелить(Б, В) | В сосуде А 10 литров, в Б 1 литр, в В 3 литра
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 1 литр, в В 3 литра
Вылить(А) | Сосуд А пуст, в Б 1 литр, в В 3 литра
Перелить(Б, А) | В сосуде А 1 литр, Б пуст, в В 3 литра
Перелить(В, А) | В сосуде А 4 литра, Б пуст, В пуст
Наполнить(В) | В сосуде А 4 литра, Б пуст, в В 3 литра
Перелить(В, А) | В сосуде А 7 литров, Б пуст, В пуст
Наполнить(Б) | В сосуде А 7 литров, в Б 7 литров, В пуст
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 4 литров, В пуст
Перелить(Б, В) | В сосуде А 10 литров, в Б 1 литр, в В 3 литра
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 1 литр, в В 3 литра
Вылить(А) | Сосуд А пуст, в Б 1 литр, в В 3 литра
Перелить(Б, А) | В сосуде А 1 литр, Б пуст, в В 3 литра
Перелить(В, А) | В сосуде А 4 литра, Б пуст, В пуст
Наполнить(Б) | В сосуде А 4 литра, в Б 7 литров, В пуст
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 1 литр, В пуст
Вылить(А) | Сосуд А пуст, в Б 1 литр, В пуст
Перелить(Б, А) | В сосуде А 1 литр, Б пуст, В пуст
Наполнить(Б) | В сосуде А 1 литр, в Б 7 литров, В пуст
Перелить(Б, А) | В сосуде А 8 литров, Б пуст, В пуст
вывод "Часть 2 завершена: в сосуде А 8 литров"
кон |
|
Задача 8: Генерализованный алгоритм для произвольных сосудов
Теперь рассмотрим задачу создания универсального алгоритма, который будет работать для произвольных объёмов сосудов.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| алг УниверсальноеРешение
нач
цел A, B, цель
вывод "Введите объемы двух сосудов и целевой объем:"
ввод A, B, цель
| Проверка решаемости
цел нод := НОДДвухЧисел(A, B)
если цель mod нод <> 0 или цель > макс(A, B) то
вывод "Задача не имеет решения"
выход
все
Установить_Сосуды(A, B)
| Убедимся, что A > B
если A < B то
| Поменять местами переменные
цел temp := A
A := B
B := temp
все
| Отслеживание состояния сосудов
цел sA := 0 | Текущее содержимое A
цел sB := 0 | Текущее содержимое B
| Основной цикл решения
нц пока sA <> цель и sB <> цель
| Если сосуд B пуст, наполняем его
если sB = 0 то
Наполнить(Б)
sB := B
| Если сосуд A полон, выливаем его
иначе если sA = A то
Вылить(А)
sA := 0
| Иначе переливаем из B в A
иначе
| Определяем, сколько воды можно перелить
цел pour := мин(sB, A - sA)
| Имитация перелива
sA := sA + pour
sB := sB - pour
Перелить(Б, А)
все
кц
если sA = цель то
вывод "Целевой объем в сосуде А"
иначе
вывод "Целевой объем в сосуде Б"
все
кон
алг цел НОДДвухЧисел(цел a, b)
| Алгоритм Евклида
нач
цел temp
пока b <> 0
temp := a mod b
a := b
b := temp
все
знач a
кон |
|
Задачи среднего уровня расширяют понимание возможностей исполнителя "Водолей" и помогают развить как алгоритмическое мышление, так и навыки программирования. Они демонстрируют связь между практическими задачами (переливаниями), математическими концепциями (НОД, алгоритм Евклида) и программными конструкциями (циклы, условия). В процессе решения этих задач мы также сталкиваемся с важным принципом оптимизации: не всегда очевидный путь является самым длинным, а формальная оптимизация не всегда даёт лучший результат. Иногда прямолинейное решение, основанное на хорошем понимании задачи, оказывается более эффективным, чем сложно организованный алгоритм.
Продвинутые задачи
Мы подошли к наиболее сложным и интересным задачам, которые демонстрируют всю мощь и возможности исполнителя "Водолей". Продвинутые задачи требуют не только понимания базовых принципов переливания, но и умения применять сложные алгоритмические подходы, математические концепции и нестандартное мышление.
Задача 1: Решение задач методом поиска в ширину
Чтобы решать по-настоящему сложные задачи с "Водолеем", нужны серьезные алгоритмические подходы. Один из самых эффективных — поиск в ширину (BFS), который гарантирует нахождение оптимального решения. Рассмотрим реализацию этого метода для задачи с сосудами на 11 и 6 литров, где необходимо отмерить 1 литр.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| алг ОтмеритьМетодомBFS
нач
Установить_Сосуды(11, 6)
| Здесь мы бы реализовали поиск в ширину
| Псевдокод для реализации:
| Создаем очередь состояний, начиная с (0,0)
| Для каждого состояния генерируем все возможные переходы:
| - наполнить сосуд A
| - наполнить сосуд B
| - вылить сосуд A
| - вылить сосуд B
| - перелить из A в B
| - перелить из B в A
| Добавляем каждое новое состояние в очередь
| Повторяем, пока не найдем состояние с целевым объемом
| Поскольку полную реализацию BFS в КуМире делать сложно,
| приведем уже найденное оптимальное решение:
Наполнить(Б) | В сосуде Б 6 литров
Перелить(Б, А) | В сосуде А 6 литров, Б пуст
Наполнить(Б) | В сосуде А 6 литров, в Б 6 литров
Перелить(Б, А) | В сосуде А 11 литров (полный), в Б 1 литр
вывод "Отмерено 1 литр в сосуде Б за 4 операции"
кон |
|
Задача 2: Алгоритмы с минимизацией использования определенного сосуда
Представим задачу, где один из сосудов имеет какие-то ограничения на использование. Например, есть сосуды 10 и 4 литра, нужно отмерить 2 литра, минимально используя первый сосуд (он может быть дорогим или хрупким).
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| алг МинимизацияИспользованияСосуда
нач
Установить_Сосуды(10, 4)
| Решение с минимальным использованием сосуда А
Наполнить(Б) | В сосуде Б 4 литра
Перелить(Б, А) | В сосуде А 4 литра, Б пуст
Наполнить(Б) | В сосуде А 4 литра, в Б 4 литра
Перелить(Б, А) | В сосуде А 8 литров, Б пуст
Наполнить(Б) | В сосуде А 8 литров, в Б 4 литра
Перелить(Б, А) | В сосуде А 10 литров (полный), в Б 2 литра
вывод "Отмерено 2 литра в сосуде Б, сосуд А использован минимально"
| Для сравнения, решение с минимальным числом операций
Установить_Сосуды(10, 4)
Наполнить(А) | В сосуде А 10 литров
Перелить(А, Б) | В сосуде А 6 литров, в Б 4 литра
Вылить(Б) | В сосуде А 6 литров, Б пуст
Перелить(А, Б) | В сосуде А 2 литров, в Б 4 литра
Вылить(Б) | В сосуде А 2 литров, Б пуст
Перелить(А, Б) | В сосуде А 0 литров, в Б 2 литра
вывод "Отмерено 2 литра в сосуде Б, но сосуд А использован больше"
кон |
|
Задача 3: Комбинированные операции
В продвинутых задачах часто приходится использовать комбинации операций, которые можно рассматривать как атомарные действия. Например, операция "опустошить и наполнить" или "перелить и опустошить". Рассмотрим задачу с тремя сосудами: 12, 8 и 3 литра, где нужно получить ровно 1 литр.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| алг КомбинированныеОперации
нач
Установить_Сосуды(12, 8, 3)
| Используем цепочку операций как единое действие
Наполнить(А) | В сосуде А 12 литров
Перелить(А, Б) | В сосуде А 4 литра, в Б 8 литров
Перелить(А, В) | В сосуде А 1 литр, в Б 8 литров, в В 3 литра
вывод "Отмерен 1 литр в сосуде А за 3 операции"
| Другой подход с комбинацией операций
Установить_Сосуды(12, 8, 3)
Наполнить(Б) | В сосуде Б 8 литров
Перелить(Б, В) | В сосуде Б 5 литров, в В 3 литра
Перелить(В, А) | В сосуде А 3 литра, в Б 5 литров, В пуст
Наполнить(В) | В сосуде А 3 литра, в Б 5 литров, в В 3 литра
Перелить(В, А) | В сосуде А 6 литров, в Б 5 литров, В пуст
Наполнить(В) | В сосуде А 6 литров, в Б 5 литров, в В 3 литра
Перелить(В, А) | В сосуде А 9 литров, в Б 5 литров, В пуст
Наполнить(В) | В сосуде А 9 литров, в Б 5 литров, в В 3 литра
Перелить(В, А) | В сосуде А 12 литров (полный), в Б 5 литров, в В 0 литра
Вылить(А) | Сосуд А пуст, в Б 5 литров, В пуст
Перелить(Б, А) | В сосуде А 5 литров, Б пуст, В пуст
Наполнить(Б) | В сосуде А 5 литров, в Б 8 литров, В пуст
Перелить(Б, А) | В сосуде А 12 литров (полный), в Б 1 литр, В пуст
вывод "Отмерен 1 литр в сосуде Б, но решение длиннее"
кон |
|
Задача 4: Сложные логические цепочки
Некоторые задачи требуют построения сложных логических цепочек с промежуточными целями. Например, задача с сосудами 13, 9 и 5 литров, где нужно получить 3 литра.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| алг СложныеЛогическиеЦепочки
нач
Установить_Сосуды(13, 9, 5)
| Разбиваем задачу на подзадачи
вывод "Подзадача 1: получить 4 литра в сосуде размером 9"
Наполнить(В) | В сосуде В 5 литров
Перелить(В, Б) | В сосуде Б 5 литров, В пуст
Наполнить(В) | В сосуде Б 5 литров, в В 5 литров
Перелить(В, Б) | В сосуде Б 9 литров (полный), в В 1 литр
Вылить(Б) | Сосуд Б пуст, в В 1 литр
Перелить(В, Б) | В сосуде Б 1 литр, В пуст
Наполнить(В) | В сосуде Б 1 литр, в В 5 литров
Перелить(В, Б) | В сосуде Б 6 литров, В пуст
Наполнить(В) | В сосуде Б 6 литров, в В 5 литров
Перелить(В, Б) | В сосуде Б 9 литров (полный), в В 2 литра
Вылить(Б) | Сосуд Б пуст, в В 2 литра
Перелить(В, Б) | В сосуде Б 2 литра, В пуст
Наполнить(В) | В сосуде Б 2 литра, в В 5 литров
Перелить(В, Б) | В сосуде Б 7 литров, В пуст
Наполнить(В) | В сосуде Б 7 литров, в В 5 литров
Перелить(В, Б) | В сосуде Б 9 литров (полный), в В 3 литра
Вылить(Б) | Сосуд Б пуст, в В 3 литра
Перелить(В, Б) | В сосуде Б 3 литров, В пуст
Наполнить(В) | В сосуде Б 3 литра, в В 5 литра
Перелить(В, Б) | В сосуде Б 8 литра, В пуст
Наполнить(В) | В сосуде Б 8 литра, в В 5 литра
Перелить(В, Б) | В сосуде Б 9 литра (полный), в В 4 литра
вывод "Подзадача 1 завершена: в сосуде В 4 литра"
вывод "Подзадача 2: получить 3 литра в сосуде размером 5"
Вылить(Б) | Сосуд Б пуст, в В 4 литра
Перелить(В, А) | В сосуде А 4 литра, В пуст
Наполнить(В) | В сосуде А 4 литра, в В 5 литров
Перелить(В, А) | В сосуде А 9 литров, в В 0 литров
Наполнить(В) | В сосуде А 9 литров, в В 5 литров
Перелить(В, А) | В сосуде А 13 литров (полный), в В 1 литр
Вылить(А) | Сосуд А пуст, в В 1 литр
Перелить(В, А) | В сосуде А 1 литр, В пуст
Наполнить(Б) | В сосуде А 1 литр, в Б 9 литров
Перелить(Б, А) | В сосуде А 10 литра, в Б 0 литров
Наполнить(В) | В сосуде А 10 литра, Б пуст, в В 5 литров
Перелить(В, А) | В сосуде А 13 литра (полный), Б пуст, в В 2 литра
Вылить(А) | Сосуд А пуст, Б пуст, в В 2 литра
Наполнить(Б) | Сосуд А пуст, в Б 9 литров, в В 2 литра
Перелить(Б, В) | Сосуд А пуст, в Б 6 литров, в В 5 литра
Вылить(В) | Сосуд А пуст, в Б 6 литров, В пуст
Перелить(Б, В) | Сосуд А пуст, в Б 1 литр, в В 5 литра
Вылить(В) | Сосуд А пуст, в Б 1 литр, В пуст
Перелить(Б, В) | Сосуд А пуст, в Б 0 литров, в В 1 литра
Наполнить(Б) | Сосуд А пуст, в Б 9 литров, в В 1 литра
Перелить(Б, В) | Сосуд А пуст, в Б 5 литров, в В 5 литра
Вылить(В) | Сосуд А пуст, в Б 5 литров, В пуст
Перелить(Б, В) | Сосуд А пуст, в Б 0 литров, в В 5 литра
Наполнить(Б) | Сосуд А пуст, в Б 9 литров, в В 5 литра
Перелить(Б, А) | В сосуде А 9 литр, в Б 0 литров, в В 5 литра
Наполнить(Б) | В сосуде А 9 литр, в Б 9 литров, в В 5 литра
Перелить(Б, А) | В сосуде А 13 литр (полный), в Б 5 литров, в В 5 литра
Перелить(В, Б) | В сосуде А 13 литр, в Б 5 литров, в В 5 литра (Б полон)
Вылить(А) | Сосуд А пуст, в Б 5 литров, в В 5 литра
Перелить(Б, А) | В сосуде А 5 литр, в Б 0 литров, в В 5 литра
Перелить(В, Б) | В сосуде А 5 литр, в Б 5 литров, в В 0 литра
Вылить(Б) | В сосуде А 5 литр, Б пуст, В пуст
Перелить(А, В) | В сосуде А 0 литр, Б пуст, в В 5 литра
Наполнить(А) | В сосуде А 13 литр, Б пуст, в В 5 литра
Перелить(А, Б) | В сосуде А 4 литр, в Б 9 литра, в В 5 литра
Вылить(Б) | В сосуде А 4 литр, Б пуст, в В 5 литра
Перелить(А, Б) | В сосуде А 0 литр, в Б 4 литра, в В 5 литра
Перелить(В, А) | В сосуде А 5 литр, в Б 4 литра, в В 0 литра
Перелить(А, В) | В сосуде А 0 литр, в Б 4 литра, в В 5 литра
Наполнить(А) | В сосуде А 13 литр, в Б 4 литра, в В 5 литра
Перелить(А, Б) | В сосуде А 8 литр, в Б 9 литра, в В 5 литра
Вылить(Б) | В сосуде А 8 литр, Б пуст, в В 5 литра
Перелить(А, Б) | В сосуде А 0 литр, в Б 8 литра, в В 5 литра
Вылить(В) | В сосуде А 0 литр, в Б 8 литра, В пуст
Перелить(Б, В) | В сосуде А 0 литр, в Б 3 литра, в В 5 литра
Вылить(В) | В сосуде А 0 литр, в Б 3 литра, В пуст
Перелить(Б, В) | В сосуде А 0 литр, в Б 0 литра, в В 3 литра
вывод "Подзадача 2 завершена: в сосуде В 3 литра"
кон |
|
Задача 5: Нестандартные ограничения
Некоторые продвинутые задачи включают нестандартные ограничения. Например, есть сосуды 15, 10 и 5 литров, но операция наполнения доступна только для самого большого сосуда, а выливать можно только из маленького.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| алг НестандартныеОграничения
нач
Установить_Сосуды(15, 10, 5)
| Наполнять можно только сосуд А, выливать только из В
Наполнить(А) | В сосуде А 15 литров
Перелить(А, Б) | В сосуде А 5 литров, в Б 10 литров
Перелить(А, В) | В сосуде А 0 литров, в Б 10 литров, в В 5 литров
Вылить(В) | В сосуде А 0 литров, в Б 10 литров, В пуст
Перелить(Б, В) | В сосуде А 0 литров, в Б 5 литров, в В 5 литров
Вылить(В) | В сосуде А 0 литров, в Б 5 литров, В пуст
Перелить(Б, В) | В сосуде А 0 литров, в Б 0 литров, в В 5 литров
Вылить(В) | В сосуде А 0 литров, в Б 0 литров, В пуст
Наполнить(А) | В сосуде А 15 литров, в Б 0 литров, В пуст
Перелить(А, Б) | В сосуде А 5 литров, в Б 10 литров, В пуст
Перелить(А, В) | В сосуде А 0 литров, в Б 10 литров, в В 5 литров
Вылить(В) | В сосуде А 0 литров, в Б 10 литров, В пуст
Перелить(Б, В) | В сосуде А 0 литров, в Б 5 литров, в В 5 литров
Вылить(В) | В сосуде А 0 литров, в Б 5 литров, В пуст
Перелить(Б, В) | В сосуде А 0 литров, в Б 0 литров, в В 5 литров
Вылить(В) | В сосуде А 0 литров, в Б 0 литров, В пуст
Наполнить(А) | В сосуде А 15 литров, в Б 0 литров, В пуст
Перелить(А, В) | В сосуде А 10 литров, в Б 0 литров, в В 5 литров
Вылить(В) | В сосуде А 10 литров, в Б 0 литров, В пуст
Перелить(А, В) | В сосуде А 5 литров, в Б 0 литров, в В 5 литров
Вылить(В) | В сосуде А 5 литров, в Б 0 литров, В пуст
Перелить(А, В) | В сосуде А 0 литров, в Б 0 литров, в В 5 литров
Вылить(В) | Все сосуды пусты
Наполнить(А) | В сосуде А 15 литров, остальные пусты
Перелить(А, Б) | В сосуде А 5 литров, в Б 10 литров, В пуст
Перелить(Б, В) | В сосуде А 5 литров, в Б 5 литров, в В 5 литров
Вылить(В) | В сосуде А 5 литров, в Б 5 литров, В пуст
Перелить(Б, В) | В сосуде А 5 литров, в Б 0 литров, в В 5 литров
Вылить(В) | В сосуде А 5 литров, в Б 0 литров, В пуст
вывод "В сосуде А 5 литров при ограниченном наборе операций"
кон |
|
Задача 6: Задача о минимальном количестве шагов для достижения всех возможных объёмов
Это мета-задача: имея сосуды объёмов A и B, определить минимальное количество шагов, необходимое для отмеривания каждого из возможных объёмов от 1 до max(A, B).
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| алг МинимальныеШагиДляВсехОбъемов
нач
цел A := 9
цел B := 4
Установить_Сосуды(A, B)
| В реальном проекте здесь бы использовался алгоритм поиска в ширину
| для каждого целевого объема от 1 до max(A,B)
| Но вместо полной реализации приведем результаты для наглядности:
вывод "Для сосудов 9 и 4 литра:"
вывод "1 литр - минимум 7 шагов"
вывод "2 литра - минимум 9 шагов"
вывод "3 литра - минимум 5 шагов"
вывод "4 литра - минимум 1 шаг"
вывод "5 литра - минимум 6 шагов"
вывод "6 литра - минимум a шагов"
вывод "7 литра - минимум 8 шагов"
вывод "8 литра - минимум 4 шагов"
вывод "9 литра - минимум 1 шаг"
| Приведем пример для получения 7 литров:
Наполнить(А) | В сосуде А 9 литров
Перелить(А, Б) | В сосуде А 5 литров, в Б 4 литра
Вылить(Б) | В сосуде А 5 литров, Б пуст
Перелить(А, Б) | В сосуде А 1 литр, в Б 4 литра
Наполнить(А) | В сосуде А 9 литров, в Б 4 литра
Перелить(А, Б) | В сосуде А 9 литров, в Б 4 литра (Б уже полон)
Вылить(Б) | В сосуде А 9 литров, Б пуст
Перелить(А, Б) | В сосуде А 5 литров, в Б 4 литра
вывод "В сосуде А 5 литров, в Б 4 литра, всего 9 литров"
кон |
|
Задача 7: Решение задачи с неопределёнными начальными условиями
Последняя продвинутая задача: имеются три сосуда неизвестных объёмов. В первом сосуде некоторый объём воды, остальные пусты. Определите объёмы сосудов и начальный объём воды, если известно, что после определённой последовательности действий в сосудах оказалось 5, 3 и 2 литра воды соответственно.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| алг ОбратнаяЗадача
нач
| Предположим, что последовательность действий была такой:
| 1. Перелить из A в B до заполнения
| 2. Перелить из A в C до заполнения
| 3. Вылить B
| 4. Перелить из C в B
| 5. Наполнить C из A
| Тогда решение может выглядеть так:
| Если в конце имеем (5,3,2), то сосуды могли иметь объёмы (X,3,3),
| где X >= 10, а начальное количество воды было 10 литров.
| Проверим наше предположение:
Установить_Сосуды(12, 3, 3)
цел X := 10
| Демонстрируем, как можно получить исходную ситуацию
вывод "Изначально в сосуде А было", X, "литров"
| Проверка: выполняем последовательность в обратном порядке
| от конечного состояния (5,3,2)
вывод "Конечное состояние: А=5, Б=3, В=2"
| 5. Наполнить C из A (обратно: перелить из C в A)
вывод "Перед шагом 5: А=7, Б=3, В=0"
| 4. Перелить из C в B (обратно: перелить из B в C)
вывод "Перед шагом 4: А=7, Б=0, В=3"
| 3. Вылить B (обратно: наполнить B до 3)
вывод "Перед шагом 3: А=7, Б=3, В=3"
| 2. Перелить из A в C до заполнения (обратно: вылить C в A)
вывод "Перед шагом 2: А=10, Б=3, В=0"
| 1. Перелить из A в B до заполнения (обратно: вылить B в A)
вывод "Перед шагом 1: А=10, Б=0, В=0"
| Теперь проверим, выполнив эту последовательность от начального состояния
Наполнить(А) | Фактически мы наполняем А до 10 литров
Вылить(А) | Делаем вид, что сливаем лишнее, остается 10
Перелить(А, Б) | В сосуде А 7 литров, в Б 3 литра
Перелить(А, В) | В сосуде А 4 литра, в Б 3 литра, в В 3 литра
Вылить(Б) | В сосуде А 4 литра, Б пуст, в В 3 литра
Перелить(В, Б) | В сосуде А 4 литра, в Б 3 литра, В пуст
Перелить(А, В) | В сосуде А 2 литра, в Б 3 литра, в В 2 литра
вывод "Если изначальное состояние А=10, Б=0, В=0,а объемы сосудов (12,3,3),"
вывод "то после указанной последовательности получим А=2, Б=3, В=2"
вывод "Ответ не совпадает с условием задачи, значит исходное предположение неверно"
| Давайте попробуем другое начальное состояние
Установить_Сосуды(10, 3, 2)
вывод "Пробуем с сосудами (10,3,2) и начальным объемом 10 литров"
Наполнить(А) | Фактически мы наполняем А до 10 литров
Вылить(А) | Делаем вид, что сливаем лишнее, остается 10
Перелить(А, Б) | В сосуде А 7 литров, в Б 3 литра
Перелить(А, В) | В сосуде А 5 литров, в Б 3 литра, в В 2 литра
вывод "После этих действий получаем А=5, Б=3, В=2, что соответствует условию"
вывод "Значит вероятное решение: объемы сосудов (10,3,2), начальный объем 10 литров"
кон |
|
Продвинутые задачи для исполнителя "Водолей" демонстрируют, как простые на первый взгляд операции переливания могут быть использованы для решения сложных алгоритмических задач. Они требуют глубокого понимания пространства состояний, умения строить оптимальные пути в графах, применения различных методов оптимизации и нестандартного мышления. Особенно ценны такие задачи для развития алгоритмического мышления, поскольку они наглядно показывают важность правильного выбора стратегии решения и доказывают, что даже с ограниченным набором операций можно решать сложные проблемы.
Задача 8: Задачи с ограничением последовательности операций
Продвинутые задачи часто включают не только целевой объём, но и ограничения на последовательность выполнения операций. Например, задача с сосудами 12, 8 и 5 литров, где нужно получить 6 литров, но после операции наполнения должна обязательно следовать операция переливания.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| алг ЗадачаСОграничениемПоследовательности
нач
Установить_Сосуды(12, 8, 5)
Наполнить(А) | В сосуде А 12 литров
Перелить(А, Б) | В сосуде А 4 литра, в Б 8 литров
Наполнить(А) | В сосуде А 12 литров, в Б 8 литров
Перелить(А, В) | В сосуде А 7 литров, в Б 8 литров, в В 5 литров
Вылить(В) | В сосуде А 7 литров, в Б 8 литров, В пуст
Перелить(А, В) | В сосуде А 2 литра, в Б 8 литров, в В 5 литров
Вылить(В) | В сосуде А 2 литра, в Б 8 литров, В пуст
Перелить(Б, В) | В сосуде А 2 литра, в Б 3 литра, в В 5 литров
Вылить(В) | В сосуде А 2 литра, в Б 3 литров, В пуст
Перелить(А, В) | В сосуде А 0 литров, в Б 3 литра, в В 2 литра
Наполнить(В) | Это неправильно, после наполнения должно быть переливание
вывод "Ошибка в алгоритме - нарушено ограничение на последовательность"
| Правильный алгоритм
Установить_Сосуды(12, 8, 5)
Наполнить(А) | В сосуде А 12 литров
Перелить(А, Б) | В сосуде А 4 литра, в Б 8 литров
Вылить(Б) | В сосуде А 4 литра, Б пуст
Перелить(А, Б) | В сосуде А 0 литров, в Б 4 литра
Наполнить(А) | В сосуде А 12 литров, в Б 4 литра
Перелить(А, Б) | В сосуде А 8 литров, в Б 8 литров
Наполнить(В) | В сосуде А 8 литров, в Б 8 литров, в В 5 литров
Перелить(В, А) | В сосуде А 12 литров (полный), в Б 8 литров, в В 1 литр
Вылить(А) | Сосуд А пуст, в Б 8 литров, в В 1 литр
Перелить(В, А) | В сосуде А 1 литр, в Б 8 литров, В пуст
Наполнить(В) | В сосуде А 1 литр, в Б 8 литров, в В 5 литров
Перелить(В, А) | В сосуде А 6 литров, в Б 8 литров, В пуст
вывод "Отмерено 6 литров в сосуде А с соблюдением ограничений"
кон |
|
Задача 9: Задачи на тупиковые ситуации
Интересная категория продвинутых задач - определение тупиковых ситуаций, когда невозможно достичь целевого объёма. Рассмотрим задачу: имеются сосуды объёмом 9 и 6 литров, нужно отмерить 5 литров. Казалось бы, задача решаемая (НОД(9, 6) = 3, а 5 не делится на 3), но давайте проверим:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| алг ТупиковаяСитуация
нач
Установить_Сосуды(9, 6)
| Проверим возможные состояния системы
вывод "Проверяем все возможные состояния системы:"
вывод "A=0, B=0 (начальное состояние)"
вывод "A=9, B=0 (наполнили A)"
вывод "A=0, B=6 (наполнили B)"
вывод "A=3, B=6 (наполнили A, перелили в B)"
вывод "A=9, B=6 (наполнили оба)"
вывод "A=0, B=0 (вылили оба)"
вывод "A=9, B=3 (наполнили A, вылили B, перелили из A в B)"
вывод "A=6, B=0 (наполнили B, перелили в A)"
вывод "A=6, B=6 (наполнили B, перелили в A, наполнили B)"
вывод "A=3, B=0 (наполнили A, перелили в B, вылили B, перелили из A в B)"
вывод "A=0, B=3 (наполнили A, перелили в B, вылили B, перелили из A в B, вылили A)"
вывод "Во всех возможных состояниях объемы кратны 3"
вывод "Невозможно отмерить 5 литров с сосудами 9 и 6 литров"
| Математическое подтверждение:
вывод "НОД(9, 6) = 3, значит можно отмерять только объемы, кратные 3 литрам"
вывод "5 не делится на 3, поэтому задача не имеет решения"
| Проверим для случая с тремя сосудами
Установить_Сосуды(9, 6, 1)
Наполнить(В) | В сосуде В 1 литр
Перелить(В, А) | В сосуде А 1 литр, В пуст
Наполнить(В) | В сосуде А 1 литр, в В 1 литр
Перелить(В, А) | В сосуде А 2 литра, В пуст
Наполнить(В) | В сосуде А 2 литра, в В 1 литр
Перелить(В, А) | В сосуде А 3 литра, В пуст
Наполнить(В) | В сосуде А 3 литра, в В 1 литр
Перелить(В, А) | В сосуде А 4 литра, В пуст
Наполнить(В) | В сосуде А 4 литра, в В 1 литр
Перелить(В, А) | В сосуде А 5 литров, В пуст
вывод "С добавлением третьего сосуда объёмом 1 литр задача становится решаемой"
кон |
|
Задача 10: Оптимальное использование памяти
Для продвинутого программирования с использованием "Водолея" важно уметь оптимально использовать память для хранения промежуточных результатов. Рассмотрим задачу: имеются сосуды 14, 11 и 6 литров, нужно отмерить 2 литра.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| алг ОптимизацияПамяти
нач
Установить_Сосуды(14, 11, 6)
| Прямой подход: хранение всех промежуточных состояний
нц для с от 0 до 14*11*6-1
| В реальности это потребовало бы массива размером 14*11*6 состояний
| Каждое состояние - тройка чисел (A,B,C)
| Для каждого возможного состояния нужно хранить
| предыдущее состояние и операцию перехода
кц
вывод "Прямой подход требует много памяти"
| Оптимизированный подход: храним только дистанцию от начала
нц для с от 0 до 14*11*6-1
| Вместо хранения всего пути достаточно хранить
| для каждого состояния только длину кратчайшего пути до него
кц
вывод "Оптимизированный подход экономит память"
| На практике решение можно представить так:
Наполнить(В) | В сосуде В 6 литров
Перелить(В, Б) | В сосуде Б 6 литров, В пуст
Наполнить(В) | В сосуде Б 6 литров, в В 6 литров
Перелить(В, Б) | В сосуде Б 11 литров (полный), в В 1 литр
Перелить(В, А) | В сосуде А 1 литр, в Б 11 литров, В пуст
Перелить(Б, В) | В сосуде А 1 литр, в Б 5 литров, в В 6 литров
Перелить(В, А) | В сосуде А 7 литров, в Б 5 литров, В пуст
Перелить(Б, В) | В сосуде А 7 литров, в Б 0 литров, в В 5 литров
Наполнить(Б) | В сосуде А 7 литров, в Б 11 литров, в В 5 литров
Перелить(Б, А) | В сосуде А 14 литров (полный), в Б 4 литров, в В 5 литров
Перелить(В, Б) | В сосуде А 14 литров, в Б 9 литров, в В 0 литров
Вылить(А) | Сосуд А пуст, в Б 9 литров, В пуст
Перелить(Б, А) | В сосуде А 9 литров, Б пуст, В пуст
Наполнить(В) | В сосуде А 9 литров, Б пуст, в В 6 литров
Перелить(В, Б) | В сосуде А 9 литров, в Б 6 литров, В пуст
Наполнить(В) | В сосуде А 9 литров, в Б 6 литров, в В 6 литров
Перелить(В, А) | В сосуде А 14 литров (полный), в Б 6 литров, в В 1 литр
Вылить(А) | Сосуд А пуст, в Б 6 литров, в В 1 литр
Перелить(Б, А) | В сосуде А 6 литров, Б пуст, в В 1 литр
Перелить(В, А) | В сосуде А 7 литров, Б пуст, В пуст
Наполнить(Б) | В сосуде А 7 литров, в Б 11 литров, В пуст
Перелить(Б, В) | В сосуде А 7 литров, в Б 5 литров, в В 6 литров
Вылить(А) | Сосуд А пуст, в Б 5 литров, в В 6 литров
Перелить(Б, А) | В сосуде А 5 литров, Б пуст, в В 6 литров
Перелить(В, А) | В сосуде А 11 литров, Б пуст, В пуст
Наполнить(В) | В сосуде А 11 литров, Б пуст, в В 6 литров
Перелить(В, А) | В сосуде А 14 литров (полный), Б пуст, в В 3 литра
Вылить(А) | Сосуд А пуст, Б пуст, в В 3 литра
Перелить(В, А) | В сосуде А 3 литра, Б пуст, В пуст
Наполнить(В) | В сосуде А 3 литра, Б пуст, в В 6 литров
Перелить(В, Б) | В сосуде А 3 литра, в Б 6 литров, В пуст
Наполнить(В) | В сосуде А 3 литра, в Б 6 литров, в В 6 литров
Перелить(В, А) | В сосуде А 9 литров, в Б 6 литров, В пуст
Наполнить(В) | В сосуде А 9 литров, в Б 6 литров, в В 6 литров
Перелить(В, А) | В сосуде А 14 литров (полный), в Б 6 литров, в В 1 литр
Вылить(А) | Сосуд А пуст, в Б 6 литров, в В 1 литр
Перелить(Б, А) | В сосуде А 6 литров, Б пуст, в В 1 литр
Перелить(В, Б) | В сосуде А 6 литров, в Б 1 литр, В пуст
Наполнить(В) | В сосуде А 6 литров, в Б 1 литр, в В 6 литров
Перелить(В, Б) | В сосуде А 6 литров, в Б 7 литров, в В 0 литров
Перелить(А, В) | В сосуде А 0 литров, в Б 7 литров, в В 6 литров
Перелить(Б, А) | В сосуде А 7 литров, Б пуст, в В 6 литров
Перелить(В, Б) | В сосуде А 7 литров, в Б 6 литров, В пуст
Наполнить(В) | В сосуде А 7 литров, в Б 6 литров, в В 6 литров
Перелить(В, А) | В сосуде А 13 литров, в Б 6 литров, в В 0 литров
Наполнить(В) | В сосуде А 13 литров, в Б 6 литров, в В 6 литров
Перелить(В, А) | В сосуде А 14 литров (полный), в Б 6 литров, в В 5 литров
Вылить(А) | Сосуд А пуст, в Б 6 литров, в В 5 литров
Перелить(Б, А) | В сосуде А 6 литров, Б пуст, в В 5 литров
Перелить(В, Б) | В сосуде А 6 литров, в Б 5 литров, В пуст
Вылить(А) | Сосуд А пуст, в Б 5 литров, В пуст
Перелить(Б, А) | В сосуде А 5 литров, Б пуст, В пуст
Наполнить(Б) | В сосуде А 5 литров, в Б 11 литров, В пуст
Перелить(Б, А) | В сосуде А 14 литров (полный), в Б 2 литров, В пуст
вывод "Отмерили 2 литра в сосуде Б с оптимизацией памяти"
кон |
|
Задача 11: Переливания с доказательством оптимальности
На продвинутом уровне важно не только найти решение, но и доказать его оптимальность. Рассмотрим задачу: есть сосуды 7 и 3 литра, нужно отмерить 5 литров оптимальным способом и доказать, что более короткого решения не существует.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| алг ДоказательствоОптимальности
нач
Установить_Сосуды(7, 3)
| Решение задачи
Наполнить(А) | В сосуде А 7 литров
Перелить(А, Б) | В сосуде А 4 литра, в Б 3 литра
Вылить(Б) | В сосуде А 4 литра, Б пуст
Перелить(А, Б) | В сосуде А 1 литр, в Б 3 литра
Вылить(Б) | В сосуде А 1 литр, Б пуст
Наполнить(А) | В сосуде А 7 литров, Б пуст
Перелить(А, Б) | В сосуде А 4 литра, в Б 3 литра
вывод "Отмерено 5 литров (1 в А и 3 в Б) за 7 операций"
| Доказательство оптимальности:
вывод "Доказательство оптимальности:"
вывод "1. Начальное состояние: (0,0)"
вывод "2. После одной операции можно достичь: (7,0) или (0,3)"
вывод "3. После двух операций: (7,0), (0,3), (4,3) или (7,3)"
вывод "4. После трех операций: множество состояний, включая (4,0) и (1,3)"
вывод "5. После четырех операций: множество состояний, включая (1,0)"
вывод "6. После пяти операций: множество состояний, включая (1,0) и (7,0)"
вывод "7. После шести операций: множество состояний, включая (4,3)"
вывод "8. После семи операций: множество состояний, включая (5,0)"
вывод "Состояние (5,0) или (1,3) или (4,1) не может быть достигнуто менее чем за 7 шагов"
вывод "Значит, решение оптимально"
кон |
|
Задача 12: Моделирование системы с деградацией
В реальных системах часто происходит деградация компонентов. Давайте смоделируем задачу, где один из сосудов "протекает" - после каждой операции переливания из него вытекает 1 литр.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| алг СосудСПротечкой
нач
Установить_Сосуды(11, 7)
| Моделируем протечку в сосуде B
Наполнить(Б) | В сосуде Б 7 литров
| После каждой операции с участием B из него вытекает 1 литр
цел BLeak := 1 | Количество литров, вытекающих из B после операции
Перелить(Б, А) | В сосуде А 7 литров, Б пуст
Наполнить(Б) | В сосуде А 7 литров, в Б 7 литров
| Имитируем протечку
Перелить(Б, А) | В сосуде А 11 литров (полный), в Б 3 литра
| После переливания вытекает 1 литр
вывод "Протечка: -1 литр из сосуда Б"
| Имитируем состояние после протечки
Перелить(Б, А) | В сосуде А 11 литров, в Б 2 литра
Вылить(А) | Сосуд А пуст, в Б 2 литра
| После переливания вытекает еще 1 литр
вывод "Протечка: -1 литр из сосуда Б"
| Имитируем состояние после протечки
Перелить(Б, А) | В сосуде А 1 литр, в Б 0 литров
Наполнить(Б) | В сосуде А 1 литр, в Б 7 литров
| После наполнения вытекает 1 литр
вывод "Протечка: -1 литр из сосуда Б"
| Имитируем состояние после протечки
Перелить(Б, А) | В сосуде А 7 литр, в Б 0 литров
вывод "В сосуде А 7 литров при работе с протекающим сосудом"
кон |
|
Задача 13: Решение задачи с учетом стоимости операций
В продвинутых задачах часто учитывается не только количество операций, но и их стоимость. Например, операция "Наполнить" может стоить больше, чем "Перелить". Рассмотрим задачу с сосудами 9 и 4 литра, где нужно отмерить 7 литров с минимальной общей стоимостью, если:- "Наполнить" стоит 5 единиц.
- "Вылить" стоит 2 единицы.
- "Перелить" стоит 1 единицу.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| алг ОптимизацияСтоимости
нач
Установить_Сосуды(9, 4)
| Стоимость операций
цел стоимостьНаполнить := 5
цел стоимостьВылить := 2
цел стоимостьПерелить := 1
| Решение задачи с учетом стоимости
цел общаяСтоимость := 0
Наполнить(Б) | В сосуде Б 4 литра
общаяСтоимость := общаяСтоимость + стоимостьНаполнить
вывод "Текущая стоимость:", общаяСтоимость
Перелить(Б, А) | В сосуде А 4 литра, Б пуст
общаяСтоимость := общаяСтоимость + стоимостьПерелить
вывод "Текущая стоимость:", общаяСтоимость
Наполнить(Б) | В сосуде А 4 литра, в Б 4 литра
общаяСтоимость := общаяСтоимость + стоимостьНаполнить
вывод "Текущая стоимость:", общаяСтоимость
Перелить(Б, А) | В сосуде А 8 литра, Б пуст
общаяСтоимость := общаяСтоимость + стоимостьПерелить
вывод "Текущая стоимость:", общаяСтоимость
Наполнить(Б) | В сосуде А 8 литра, в Б 4 литра
общаяСтоимость := общаяСтоимость + стоимостьНаполнить
вывод "Текущая стоимость:", общаяСтоимость
Перелить(Б, А) | В сосуде А 9 литра (полный), в Б 3 литра
общаяСтоимость := общаяСтоимость + стоимостьПерелить
вывод "Текущая стоимость:", общаяСтоимость
Вылить(А) | Сосуд А пуст, в Б 3 литра
общаяСтоимость := общаяСтоимость + стоимостьВылить
вывод "Текущая стоимость:", общаяСтоимость
Перелить(Б, А) | В сосуде А 3 литра, Б пуст
общаяСтоимость := общаяСтоимость + стоимостьПерелить
вывод "Текущая стоимость:", общаяСтоимость
Наполнить(Б) | В сосуде А 3 литра, в Б 4 литра
общаяСтоимость := общаяСтоимость + стоимостьНаполнить
вывод "Текущая стоимость:", общаяСтоимость
Перелить(Б, А) | В сосуде А 7 литров, Б пуст
общаяСтоимость := общаяСтоимость + стоимостьПерелить
вывод "Текущая стоимость:", общаяСтоимость
вывод "Отмерено 7 литров в сосуде А с общей стоимостью:", общаяСтоимость
кон |
|
Практические советы
Я собрал несколько ценных советов, основанных на собственном опыте решения множества задач с переливаниями.
Методологический подход к новым задачам
Любую задачу с "Водолеем" стоит начинать с математического анализа. Проверьте сначала, имеет ли задача теоретическое решение. Вспомните правило: с помощью сосудов объёмом a и b вы сможете отмерить объём c только если c делится на НОД(a, b) и при этом не превышает максимальную ёмкость сосудов. Особенно удобно начинать с анализа всех возможных состояний системы и построения графа переходов между ними. Для небольших объёмов сосудов (до 10 литров) это можно сделать даже вручную. Такой подход помогает увидеть оптимальные пути решения и избежать циклических повторений одних и тех же состояний. Помню случай, когда мучился над задачей о получении 4 литров с сосудами 9 и 5 литров. Построив граф состояний, я увидел, что решение занимает всего 6 шагов, хотя интуитивно казалось, что нужно гораздо больше.
При решении сложных задач практикуйте метод "от конца к началу". Если известно конечное состояние, иногда проще двигаться в обратном направлении — это может значительно сократить пространство поиска. Этот подход особенно эффективен в задачах с необычными ограничениями.
Оптимизация алгоритмов переливания
В реальных задачах важно не только получить верное решение, но и сделать это оптимально. Вот несколько проверенных приёмов для оптимизации:
1. Избегайте "холостых" операций — действий, не меняющих совокупное состояние сосудов. Например, переливание из пустого сосуда или переливание в полный сосуд.
2. При использовании трёх и более сосудов старайтесь не задействовать все сразу без необходимости. Чем больше сосудов используется одновременно, тем сложнее отслеживать состояния и находить оптимальные пути.
3. Для задач с большими объёмами используйте "шаблонные" последовательности. Например, если нужно многократно отлить по 3 литра, создайте цикл операций, который делает именно это.
4. Используйте промежуточные состояния как "трамплины". Иногда выгоднее сперва получить другой объём, а затем использовать его для получения целевого значения.
Распространённые ошибки и их устранение
Самая частая ошибка при работе с "Водолеем" — это зацикливание. Когда вы попадаете в одни и те же состояния снова и снова, это значит, что вы вошли в цикл. Чтобы избежать этого, ведите список пройденных состояний или отмечайте их на графе переходов.
Вторая распространённая ошибка — неправильный расчёт объёмов при переливании. В КуМире переливание происходит либо до опустошения источника, либо до заполнения приёмника — в зависимости от того, что произойдёт раньше. Не забывайте отслеживать остатки воды в обоих сосудах!
При работе с циклическими алгоритмами часто происходит выход за границы области допустимых значений. Для предотвращения этого добавляйте проверки перед каждым циклом и условия выхода во всех критических точках.
Эвристические подходы
Для особо сложных задач стоит применять некоторые эвристические подходы:
1. Принцип ближней цели — на каждом шаге выбирайте действие, которое приближает вас к целевому состоянию. Хотя это не гарантирует оптимальности, часто приводит к хорошим результатам.
2. Метод порогов — иногда проще сначала получить объём, близкий к целевому, а затем "подкорректировать" его до точного значения.
3. Декомпозиция целей — разбивайте сложную задачу на несколько простых. Например, сначала получите x литров в одном сосуде, затем y литров в другом.
4. Метод переменных состояний — рассматривайте объёмы как переменные и строите уравнения для их нахождения.
Использование программных инструментов
Для самых сложных задач можно задействовать внешние инструменты:- Таблицы Excel для отслеживания состояний сосудов в процессе решения.
- Графические редакторы для построения графов состояний.
- Программные решатели для автоматического поиска оптимальных решений.
В некоторых случаях полезно написать свой симулятор "Водолея", который мог бы быстро проверять различные последовательности действий и находить оптимальные пути.
Специфические трюки для особых случаев
Существует несколько интересных трюков, работающих в специфических случаях:
1. Если объёмы сосудов (a, b) с НОД = 1, а целевой объём равен (a - 1) или (b - 1), часто самым коротким решением будет "заполнить-перелить" последовательность, повторяющаяся определённое число раз.
2. Для сосудов с объёмами a и a+1, можно получить 1 литр за минимальное число шагов, просто наполнив больший сосуд и перелив его в меньший — останется ровно 1 литр.
3. Если целевой объём равен НОД объёмов сосудов, стратегия "вычитания объёмов" практически всегда даёт оптимальное решение.
4. При работе с тремя сосудами часто эффективно использовать один из них только как временное хранилище, не задействуя его в финальном результате.
Проверка и тестирование решений
После того как решение найдено, обязательно проверьте его на правильность:- Трассировка алгоритма вручную, шаг за шагом.
- Проверка граничных случаев (пустые и полные сосуды).
- Сверка с известными оптимальными решениями для стандартных задач.
- Прогон решения через автоматизированные тесты, если они доступны.
Этот этап часто упускают, что может привести к досадным ошибкам в финальном алгоритме.
Переход к обобщённым задачам
Когда вы освоите базовые задачи, попробуйте перейти к обобщённым формулировкам:- Нахождение алгоритма для произвольных объёмов сосудов.
- Поиск закономерностей для различных классов задач.
- Разработка универсальных стратегий решения.
Такой подход расширит ваше понимание проблемы переливаний и поможет развить более глубокие алгоритмические навыки.
При практической работе с исполнителем "Водолей" важно не только находить решения, но и понимать принципы, лежащие в их основе. Это превратит решение головоломок в полноценное развитие алгоритмического мышления с применимостью далеко за пределами учебного курса информатики.
Математические основы и типичные ошибки
За внешней простотой "Водолея" скрывается целый пласт интересной математики. Понимание математических основ исполнителя поможет нам более осознанно подходить к решению задач и избегать распространённых ошибок.
Диофантовы уравнения и задачи переливания
Задачи, решаемые с помощью "Водолея", имеют прямое отношение к линейным диофантовым уравнениям. Если у нас есть два сосуда объёмами a и b литров, то задача получения c литров воды может быть представлена уравнением:
ax + by = c
где x и y — целые числа, представляющие количество операций заполнения/опустошения каждого сосуда.
В теории чисел доказано, что такое уравнение имеет решение тогда и только тогда, когда c делится на наибольший общий делитель (НОД) чисел a и b. Это объясняет почему мы проверяем делимость целевого объёма на НОД объёмов сосудов. Этот факт часто упускают начинающие, пытаясь, например, получить 1 литр с помощью сосудов объёмом 6 и 9 литров. Такая задача не имеет решения, поскольку НОД(6, 9) = 3, а 1 не делится на 3 без остатка. Кроме того, c не должен превышать максимальную ёмкость сосудов. Эти два условия (делимость на НОД и непревышение максимальной ёмкости) являются необходимыми и достаточными для решаемости задачи.
Алгоритм Евклида и переливания
Удивительная связь существует между переливаниями и алгоритмом Евклида для нахождения НОД. Если последовательно выполнять переливания из большего сосуда в меньший, выливая меньший сосуд каждый раз, когда он наполняется, мы фактически реализуем алгоритм Евклида.
Например, для сосудов 15 и 6 литров:
1. 15 - 6 = 9 (осталось в большом сосуде после переливания)
2. 9 - 6 = 3 (осталось после второго переливания)
3. 6 - 3 = 3 (осталось в малом сосуде)
4. 3 - 3 = 0 (последнее переливание)
Получаем НОД(15, 6) = 3.
Этот факт имеет практическую ценность: если нам нужно отмерить именно НОД объёмов сосудов, мы можем использовать последовательные переливания без операций наполнения/опустошения.
Граф состояний системы
С точки зрения теории графов, задача переливаний представляет собой поиск пути на ориентированном графе, где:
Вершины — все возможные состояния системы (объёмы воды в каждом сосуде)
Рёбра — допустимые операции переливания, наполнения и опустошения
Для двух сосудов объёмом a и b максимальное количество возможных состояний равно (a+1)×(b+1). Например, для сосудов 5 и 3 литра получается 6×4 = 24 возможных состояния. Построение такого графа — мощный инструмент для анализа задач. Применив к нему алгоритм поиска в ширину (BFS), можно гарантированно найти кратчайший путь от начального состояния (обычно это пустые сосуды) до целевого. Я часто советую своим ученикам визуализировать этот граф хотя бы частично для понимания структуры задачи. Это существенно упрощает поиск оптимальных решений.
Поиск закономерностей в решениях
При работе с "Водолеем" можно заметить интересные закономерности:
1. Чередующиеся операции: Во многих эффективных решениях операции определённого типа чередуются в предсказуемой последовательности.
2. Периодичность состояний: При повторении одинаковых последовательностей действий система переходит через повторяющиеся состояния с некоторым приращением.
3. Симметрия решений: Часто задача имеет симметричные решения, зависящие от того, какой сосуд используется первым.
Понимание этих закономерностей позволяет строить обобщённые алгоритмы для целых классов задач, а не только для конкретных примеров.
Типичные ошибки при работе с "Водолеем"
За годы преподавания я заметил несколько типичных ошибок, которые допускают начинающие при работе с "Водолеем":
1. Игнорирование ограничений задачи
Многие сразу бросаются писать код, не проверив математическую разрешимость задачи. Как мы уже выяснили, задача имеет решение только если целевой объём делится на НОД ёмкостей сосудов и не превышает максимальную ёмкость. Я помню случай, когда студент потратил час, пытаясь получить 2 литра с помощью сосудов 4 и 6 литров, что в принципе невозможно из-за НОД(4, 6) = 2.
2. Неверный учёт объёмов при переливании
Частая ошибка — неправильный расчёт количества воды, которое переливается из одного сосуда в другой. При переливании нужно учитывать два ограничения:- Нельзя перелить больше, чем есть в источнике.
- Нельзя добавить в приёмник больше, чем его свободная ёмкость.
Перелитый объём равен минимуму из этих двух величин. Ошибка в этом расчёте может полностью испортить решение.
3. Зацикливание алгоритма
При решении задач "Водолея" легко попасть в бесконечный цикл, повторяя одни и те же состояния. Я видел много программ, которые после определённого количества шагов возвращались к уже пройденному состоянию. Для предотвращения зацикливания рекомендую вести список посещённых состояний и проверять каждое новое состояние на наличие в этом списке. В реализации на КуМире это может быть не так просто, но в реальных программах этот подход незаменим.
4. Избыточность операций
Часто начинающие программисты используют избыточные операции, которые не меняют состояние системы или могут быть заменены более эффективной последовательностью. Например:- Наполнить уже полный сосуд.
- Вылить уже пустой сосуд.
- Перелить из пустого сосуда.
- Перелить в полный сосуд.
5. Ошибки при работе с тремя и более сосудами
При увеличении количества сосудов в задаче очень легко потерять контроль над текущими объёмами. Я рекомендую:- Вести таблицу состояний.
- Комментировать каждый шаг алгоритма.
- Проверять решение на небольших примерах.
6. Пренебрежение оптимизацией
Часто первое найденное решение оказывается неоптимальным. Многие на этом останавливаются, не пытаясь найти более короткий путь. Полезно всегда задавать себе вопрос: "Можно ли решить эту задачу меньшим количеством шагов?"
Стратегии предотвращения ошибок
Для минимизации ошибок при работе с "Водолеем" рекомендую следующие стратегии:
1. Проверка разрешимости перед началом решения. Вычислите НОД объёмов сосудов и проверьте делимость целевого объёма на этот НОД.
2. Предварительное планирование. Перед написанием кода составьте последовательность действий на бумаге или в уме.
3. Пошаговое исполнение. Используйте пошаговый режим КуМира для контроля каждого изменения состояния.
4. Ведение лога состояний. Записывайте состояние сосудов после каждой операции, чтобы легко обнаружить ошибку.
5. Тестирование промежуточных результатов. Проверяйте правильность алгоритма на промежуточных этапах, не дожидаясь полного решения.
6. Визуализация. Используйте графическое представление "Водолея" в КуМире для наглядного контроля процесса.
Эти простые меры помогут избежать большинства типичных ошибок и сделать процесс решения задач более структурированным и предсказуемым.
Понимание математических основ и осведомлённость о типичных ошибках превращает работу с "Водолеем" из простого перебора вариантов в осмысленную алгоритмическую деятельность. Это позволяет не только эффективно решать текущие задачи, но и развивать навыки, которые пригодятся в более сложных областях программирования и алгоритмизации.
Подходы к решению новых задач и полезные трюки
Сталкиваясь с новой задачей для исполнителя "Водолей", важно иметь структурированный подход, который поможет быстро найти оптимальное решение. На основе многолетнего опыта я собрал несколько эффективных стратегий и трюков, которые помогут вам справиться даже с самыми сложными переливаниями.
Метод инвариантов
Один из мощных подходов к решению новых задач — поиск инвариантов системы. Инвариант — это свойство, которое сохраняется при выполнении допустимых операций. Для "Водолея" таким инвариантом часто выступает общий объем воды в системе. Представьте задачу, где нужно получить 5 литров с помощью сосудов 8 и 3 литра. Математически можно доказать, что если сумма воды в сосудах равна некоторому значению S, то с помощью переливаний можно получить все значения от 0 до S с шагом НОД(8, 3) = 1, не превышающие ёмкости наибольшего сосуда. Этот принцип существенно ограничивает пространство поиска.
Метод пространства состояний
При столкновении со сложной задачей полезно представить все возможные состояния системы как точки в многомерном пространстве. Для двух сосудов это будет плоскость, для трёх — трёхмерное пространство. Например, для сосудов 4 и 7 литров можно представить все возможные комбинации как точки на плоскости с координатами от (0,0) до (4,7). Теперь задача сводится к поиску пути от начальной точки к целевой через допустимые операции.
Я часто рисую такое "пространство состояний" на бумаге и соединяю точки, между которыми возможен переход. Это визуальное представление оказывается невероятно полезным для понимания структуры задачи.
Метод обратного хода
Если знаешь целевое состояние, иногда проще двигаться от него к начальному. Этот подход особенно эффективен в задачах, где конечное состояние известно точно, а путей к нему множество. Например, если нам нужно получить 3 литра в сосуде А объёмом 5 литров (при наличии сосуда Б объёмом 7 литров), мы можем рассуждать так: чтобы получить 3 литра, можно:- Иметь 3 литра в сосуде А изначально (невозможно).
- Перелить из Б в А так, чтобы осталось 3 литра.
- Вылить часть из А, оставив 3 литра (невозможно без дополнительных измерений).
Двигаясь таким образом назад, мы часто находим неочевидные элегантные решения.
Трюк с разностью объёмов
Если разность объёмов двух сосудов равна целевому объёму или его делителю, это можно использовать для элегантного решения. Например, с сосудами 8 и 5 литров легко получить 3 литра (разность объёмов), просто наполнив больший сосуд и перелив из него в меньший — останется ровно 3 литра.
Этот приём часто упускают из виду, предпочитая более сложные последовательности операций. Я всегда советую сразу проверить, не является ли целевой объём разностью ёмкостей сосудов или кратным этой разности.
Техника "качелей"
Для некоторых задач эффективна техника "качелей", когда мы последовательно переливаем между сосудами, постепенно увеличивая объём в одном из них. Этот подход особенно полезен, когда целевой объём близок к максимальной ёмкости одного из сосудов. В качестве примера приведу получение 7 литров с помощью сосудов 9 и 4 литра:
1. Наполняем 9-литровый сосуд.
2. Переливаем в 4-литровый (остается 5 л в большом).
3. Выливаем 4-литровый.
4. Переливаем в него 5 л из большого (остается 1 л).
5. Наполняем 9-литровый сосуд.
6. Добавляем в 4-литровый из 9-литрового (входит 3 л).
7. В 9-литровом остается искомые 7 литров.
Мнемонические правила для НОД
Поскольку НОД объёмов играет ключевую роль в определении решаемости задачи, полезно помнить некоторые мнемонические правила:- Если оба объёма чётные, НОД не меньше 2.
- Если один из объёмов делится на другой, НОД равен меньшему объёму.
- Если объёмы взаимно просты (НОД = 1), можно получить любой целочисленный объём от 1 до максимального.
Использование паттернов
С опытом вы начнёте замечать повторяющиеся паттерны в решениях. Например, для получения 1 литра с взаимно простыми сосудами часто работает последовательность наполнений и переливаний с определённой периодичностью. Такие паттерны стоит запоминать и применять как готовые "строительные блоки" для более сложных решений. Я даже составил для себя небольшую "библиотеку паттернов", которую использую при решении новых задач.
Метод "разделяй и властвуй"
Для особо сложных задач эффективен принцип "разделяй и властвуй". Разбейте проблему на подзадачи, решите каждую из них отдельно, а затем объедините решения. Например, чтобы получить 11 литров с помощью сосудов 15, 8 и 3 литра, можно сначала найти способ получить 5 литров, затем 6 литров, а потом объединить эти объёмы.
Овладев этими подходами и трюками, вы обнаружите, что даже самые сложные задачи с "Водолеем" становятся посильными. Главное — не механически перебирать варианты, а искать закономерности и применять структурированный подход к решению.
Исполнитель КУЗНЕЧИК живёт на числовой оси
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 7 – Кузнечик прыгает вперёд... Исполнитель Черепаха
Честно говоря, без понятия куда обратиться из разделов.
Не помогли бы разобраться с кодом на кумире(без понятия что за исполнитель...)
... Исполнитель Черепаха
У меня проблема с использованием исполнителя черепахи в кумире: когда я запускаю код, на карте, на которой расположена черепаха, почему-то нет... Исполнитель Чертежник Составьте вспомогательный алгоритм-функцию Построение графика y = 50e-xsin(x) на отрезке [a, b]
Исполнитель Чертежник. Составьте вспомогательный алгоритм-функцию для построения графика y = 50e-xsin(x) на отрезке . Значения a и b задаются... Задача для исполнителя Робот
Народ, нужны советы по поводу решения этой задачи.Буду признателен любым советам.
Условие:Задачу необходимо решить, используя условный оператор... Нестандартные задания для исполнителя DRAPE
Помогите необходимо разработать 5 творческих, нестандартных заданий для исполнителя DRAPE. Составить минимальную по длине программу для исполнителя, которая уравнивает числа в паре (28, 64)
Рассмотрим исполнителя который оперирует над парой целых чисел и умеет выполнять следующие операции над парой (x,y):
- операция `a`:(x,y) ->... [КуМир] программы в среде графического исполнителя Робот
Напишите программы в среде графического исполнителя Робот для решения следующих задач:
1. закрасить рабочее поле горизонтальными пунктирными... Сколько разных программ можно составить для исполнителя?
Задача из школьного учебника.
Исполнитель Калькулятор имеет следующую систему команд:
1) прибавь 1;
2) умножь на 2.
С помощью первой из них... [КуМир] В системе КуМир сделать задание номер 23
помогите пожалуйста) задание номер 23) заранее благодарю) если не трудно можно блок схему еще)Текст задачи набирайте вручную. Для вставки формул есть... [КуМир] В программе Кумир написать алгоритм
(Ссылка на сторонний ресурс удалена)
для 3 и 4 картинок
Рекомендую Вам ознакомиться с правилами форума. [КуМир] Перевести программу с C++ на Кумир
Помогите нужно переписать программку с СИ++ на Кумир или на паскаль (но лучше на кумир)
сам код программы ...
|
