Решение задач методом переливаний
Задачи на переливания решаются построением точной последовательности команд исполнителя Водолей. Нужно учитывать вместимость сосудов, их текущее состояние и правила переливания, а затем проверить, что в некотором сосуде получен требуемый объём воды.
Модель задачи и команды
В условии обычно даны два или три сосуда известной вместимости. В начале один сосуд может быть наполнен, остальные пусты, либо начальное состояние указано явно. Исполнитель умеет выполнять ограниченный набор действий. Перед решением полезно повторить команды исполнителя Водолея и записать их кратко: наполнить сосуд, вылить сосуд, перелить из одного сосуда в другой.
Состояние — это набор текущих объёмов воды во всех сосудах. Для сосудов вместимостью \(A\) и \(B\) его удобно записывать парой \((x,y)\), где \(0\le x\le A\) и \(0\le y\le B\). Подробное описание есть на странице «Состояние сосудов».
При переливании из сосуда \(X\) в сосуд \(Y\) вода льётся до тех пор, пока либо сосуд \(X\) не опустеет, либо сосуд \(Y\) не наполнится. Поэтому после каждой команды хотя бы один из двух сосудов оказывается пустым или полным. Это свойство помогает быстро проверять правильность промежуточных состояний.
| Команда | Что происходит | Условие остановки |
|---|---|---|
| Наполнить \(X\) | \(x\) становится равным вместимости \(X\) | сосуд \(X\) полон |
| Вылить \(X\) | \(x\) становится равным \(0\) | сосуд \(X\) пуст |
| Перелить \(X\) в \(Y\) | часть воды переходит из \(X\) в \(Y\) | \(X\) пуст или \(Y\) полон |
Алгоритм решения вручную
Главная идея — не угадывать команды бессистемно, а строить цепочку состояний. Начинайте с начального состояния и после каждой команды записывайте результат. Если требуется получить объём \(T\), цель считается достигнутой, когда \(x=T\) или \(y=T\).
- Запишите вместимости сосудов, начальное состояние и требуемый объём.
- Выберите направление переливаний. Например, можно пытаться получать остаток в сосуде \(B\), переливая из \(A\) в \(B\).
- После каждой команды записывайте новое состояние \((x,y)\).
- Остановитесь, как только один из объёмов станет равен \(T\).
- Проверьте каждую команду: объёмы не должны выходить за пределы вместимостей, а вода не должна исчезать без команды выливания.
Формула (1) описывает переливание из сосуда \(A\) в сосуд \(B\): \(x\) и \(y\) — объёмы до переливания, \(B-y\) — свободное место во втором сосуде. Величина \(\min(x,B-y)\) — объём перелитой воды.
Для сосудов вместимостей \(A\) и \(B\) можно получить объём \(T\) (при стандартных командах), если \(T\le\max(A,B)\) и \(T\) кратен \(\gcd(A,B)\): \(T\equiv0\pmod{\gcd(A,B)}\). Этот признак не заменяет построение команд: он только сообщает, существует ли решение.
С признаком подробнее помогает страница «Признак достижимости объёма в задаче Водолей». Если объём достижим, последовательность можно искать перебором состояний или двумя типовыми стратегиями: переливать из большего сосуда в меньший либо наоборот.
В сосудах вместимостью 5 л и 3 л состояние равно \((5,2)\). Что произойдёт при переливании из первого сосуда во второй?
Разобранный пример
Задача. Есть сосуды вместимостью 5 л и 3 л. В начале пятилитровый сосуд полон, трёхлитровый пуст. Получить ровно 4 л воды в пятилитровом сосуде.
Будем обозначать состояние как \((x,y)\), где \(x\) — объём в сосуде 5 л, а \(y\) — объём в сосуде 3 л. Выполним переливания из пятилитрового сосуда в трёхлитровый, а затем будем повторять цикл.
Последовательность команд: наполнить 5-литровый сосуд; перелить из 5-литрового в 3-литровый; вылить 3-литровый; перелить из 5-литрового в 3-литровый; вылить 3-литровый; наполнить 5-литровый; перелить в 3-литровый; вылить 3-литровый; перелить в 3-литровый; наполнить 5-литровый; перелить в 3-литровый. Получаем состояние \((4,3)\), то есть в пятилитровом сосуде ровно 4 л.
Поиск решения через состояния
Если цепочка не находится сразу, перечисляйте все достижимые состояния. Каждое состояние — вершина, а команда, переводящая его в другое состояние, — переход. Так строится граф состояний Водолея. Нельзя добавлять в список состояние, которое уже встречалось: иначе алгоритм будет ходить по циклу.
Для двух сосудов число состояний ограничено: у первого \(A+1\) вариантов объёма, у второго \(B+1\), всего не более \((A+1)(B+1)\) пар. Удобно вести таблицу: номер шага, команда, состояние. Если задача требует кратчайший путь, используют перебор по уровням: сначала проверяют состояния после одной команды, затем после двух и так далее.
Сравните два варианта: получать остаток в сосуде \(A\), переливая из \(B\) в \(A\), или получать остаток в сосуде \(B\), переливая из \(A\) в \(B\). Обычно короче тот вариант, в котором целевой объём появляется как остаток после заполнения меньшего сосуда.
Типичные ошибки
1. Записывают только команды и не проверяют состояния. 2. Переливают воду «частично» без причины: по правилам переливание заканчивается при пустом исходном или полном принимающем сосуде. 3. Путают вместимость и текущий объём. 4. Забывают, что для получения нового полного сосуда его нужно сначала наполнить или перелить в него воду. 5. Продолжают команды после появления требуемого объёма, хотя в ответе нужна последовательность до первого достижения цели. 6. Повторяют уже встречавшееся состояние и попадают в цикл.
В задачах с дополнительными ограничениями учитывайте препятствие исполнителя и правила траектории исполнителя, если они указаны в условии. Общий принцип тот же: состояние меняется только разрешённой командой, а каждый переход нужно проверить.
Как оформить ответ на экзамене
- Указать начальное состояние сосудов.
- Записать команды в правильном порядке, без пропусков.
- После ключевых шагов проверить объёмы.
- Убедиться, что итоговое состояние содержит требуемый объём.
- Если спрашивается минимальное число действий, сравнить найденный путь с другими или выполнить поиск по уровням.
Быстрая проверка
Главное
- Состояние двух сосудов записывают как \((x,y)\), где значения не превышают вместимости сосудов.
- При переливании вода идёт до опустошения исходного или заполнения принимающего сосуда.
- Решение строят как цепочку состояний: команда — новое состояние — проверка.
- Достижимость объёма связана с НОД вместимостей: целевой объём должен быть кратен \(\gcd(A,B)\) и не превышать большую вместимость.
- Если решение не находится сразу, используют граф состояний и не повторяют уже рассмотренные пары.