З Задачи о переливаниях

Определения и обозначения

Задача о переливаниях — задача, в которой нужно получить нужное количество жидкости, переливая её между сосудами. Например, требуется отмерить несколько литров, хотя на сосудах нет делений. Это определение подсказывает, что решением будет последовательность действий, а не одно вычисление.

Сосуд — ёмкость, в которой находится жидкость; в задаче учитывают её текущий объём и вместимость. Сосуды могут быть полными, пустыми или заполненными частично. Учитывать оба свойства нужно, чтобы понимать, сколько воды можно из сосуда вылить и сколько в него ещё поместится.

Вместимость сосуда — наибольший объём жидкости, который в него помещается. Если вместимость равна 5 л, воды в сосуде не может быть больше 5 л. Это ограничение помогает проверять, допустимо ли каждое полученное состояние.

Состояние сосудов — количества жидкости в каждом сосуде в данный момент. Для трёх сосудов его можно записать так: (3, 5, 0), то есть в первом 3 л, во втором 5 л, в третьем 0 л. Такая запись нужна, чтобы видеть всю задачу сразу и не забывать о воде в остальных сосудах.

Как это устроено

Условия задачи задают вместимость каждого сосуда и начальный объём воды. Например, запись «сосуды 8 л, 5 л и 3 л; первый полный, остальные пустые» означает вместимости 8, 5 и 3 л и начальное состояние (8, 0, 0). Вместимость ограничивает верхнее количество воды, а начальное состояние определяет, с чего начинается поиск. Если потерять хотя бы одно из этих условий, можно записать невозможное действие.

При обычном переливании воду льют, пока исходный сосуд не опустеет или принимающий не наполнится. Это правило делает действия однозначными: не приходится выбирать произвольную порцию. Вода только перемещается, поэтому её общий объём остаётся прежним. Например, если всего было 8 л, после любого переливания во всех сосудах вместе тоже должно быть 8 л.

Чтобы записать состояние, перечисляют объёмы воды во всех сосудах в одном и том же порядке. В состоянии (3, 5, 0) сумма чисел равна 8, а каждое число не превышает вместимость соответствующего сосуда. Такая запись сохраняет сразу две проверки: общий объём и ограничения сосудов. Если поменять порядок чисел, запись уже будет означать другое состояние.

Для переливания сначала выбирают исходный и принимающий сосуды. Затем сравнивают воду в исходном сосуде со свободным местом в принимающем: перелить можно ровно меньшее из этих двух количеств. Например, если в исходном сосуде 6 л, а в принимающем свободно только 2 л, переместятся 2 л. Запишите, сколько вычли и сколько прибавили, а затем проверьте, что ни один сосуд не переполнен.

Поиск решения ведут цепочкой состояний: из начального получают возможные следующие, затем рассматривают действия из них. Уже встреченное состояние отмечают, потому что оно возвращает к тем же возможностям и не требует повторного перебора. Цель проверяют после каждого перехода: нужный объём может оказаться в любом сосуде, если условие не говорит иначе. Если требуется минимум действий, удобно сравнивать цепочки по числу переливаний и начинать с цепочек в один шаг, затем в два и так далее.

Состояния сосудов и возможные переливания

Читайте строку как переход от текущих объёмов к следующим: сначала выберите допустимое переливание, затем запишите, что изменилось. После этого проверьте вместимость каждого сосуда и сохранение общего количества воды. Если цель достигнута, цепочку можно завершить.

Разбор задач

Как получить 4 л с сосудами 8 л, 5 л и 3 л

В начале полный сосуд содержит 8 л, а два других пусты: состояние (8, 0, 0). Объёмы в записи всегда идут в порядке вместимостей 8, 5, 3 л. Нужно получить 4 л в одном из сосудов, поэтому будем записывать результат после каждого действия.

1. Перелейте из сосуда 8 л в сосуд 5 л до заполнения второго. Получится (3, 5, 0): в первом осталось 3 л.
2. Перелейте из сосуда 5 л в сосуд 3 л до заполнения третьего. Получится (3, 2, 3).
3. Перелейте из сосуда 3 л в сосуд 8 л до опустошения третьего. Получится (6, 2, 0).
4. Перелейте из сосуда 5 л в сосуд 3 л. В третьем поместятся все 2 л, поэтому получится (6, 0, 2).
5. Из сосуда 8 л перелейте воду в сосуд 5 л до его заполнения. Получится (1, 5, 2).
6. Из сосуда 5 л перелейте воду в сосуд 3 л до заполнения третьего. В нём уже 2 л, свободно 1 л, поэтому в сосуде 5 л останется 4 л: (1, 4, 3).

На каждом шаге вода только перемещалась, а объёмы не превышали вместимости 8, 5 и 3 л. Значит, цепочка допустима и приводит к цели. Ответ: 4 л получены в сосуде вместимостью 5 л.

Можно ли получить 7 л с сосудами 9 л, 6 л и 4 л

Начальное состояние — (9, 0, 0), а всего воды 9 л. Проверим цель последовательностью допустимых переливаний, записывая все три сосуда. Полученная цепочка одновременно показывает, что 7 л действительно достижимы.

1. Перелейте из сосуда 9 л в сосуд 6 л до заполнения: (3, 6, 0).
2. Из сосуда 6 л перелейте воду в сосуд 4 л до заполнения: (3, 2, 4).
3. Из сосуда 4 л перелейте воду в сосуд 9 л до опустошения: (7, 2, 0).

В последнем состоянии в первом сосуде 7 л, во втором 2 л, а третий пуст. Сумма по-прежнему равна 9 л, и ни одна вместимость не превышена. Ответ: да, можно; в сосуде вместимостью 9 л будет 7 л.

Как получить 5 л за минимальное число переливаний

Пусть сосуды имеют вместимости 10, 7 и 3 л, а начальное состояние — (10, 0, 0). Чтобы обосновать минимум, удобно рассматривать возможные состояния по числу действий: сначала все достижимые за один шаг, потом за два и так далее. Не возвращайтесь к состояниям, которые уже встречались: из них новых возможностей не появится.

1. Из (10, 0, 0) перелейте 7 л в средний сосуд: получится (3, 7, 0).
2. Из среднего сосуда перелейте воду в сосуд 3 л до заполнения: получится (3, 4, 3).
3. Перелейте из сосуда 3 л в сосуд 10 л: получится (6, 4, 0).
4. Из сосуда 7 л перелейте 3 л в сосуд 3 л: получится (6, 1, 3).
5. Перелейте 3 л из сосуда 3 л в сосуд 10 л: получится (9, 1, 0).
6. Из сосуда 10 л налейте в сосуд 7 л до заполнения: получится (2, 7, 1).
7. Из сосуда 7 л перелейте воду в сосуд 3 л до заполнения. В третьем сосуде уже 1 л, поэтому переместятся 2 л и получится (2, 5, 3).

Теперь в среднем сосуде ровно 5 л. Поиск по уровням — сначала один переход, затем два и далее — позволяет проверить, что на более ранних уровнях цели нет; значит, найденная цепочка кратчайшая. Ответ: 5 л получаются за 7 переливаний.

Типичные ошибки

Записывать только количество воды в одном сосуде — значит потерять сведения об остальных. Так поступают, когда следят лишь за целью, но это может сделать непонятным следующий шаг. Проверяйте себя: в каждой строке должны быть объёмы всех сосудов в неизменном порядке.

Переливать произвольное количество нельзя, если условие разрешает только переливать до опустошения или заполнения. Ошибка возникает из-за желания сразу получить нужный объём, но выбранное действие может быть недопустимым. Перед записью результата сравните количество воды с количеством свободного места.

Иногда кажется, что при переливании вода исчезла или появилась, потому что записали новое состояние с ошибкой. На самом деле жидкость только переходит из сосуда в сосуд. Сложите объёмы до и после действия: обе суммы должны быть одинаковыми.

Повторное прохождение уже встреченного состояния тратит время и может запутать цепочку. Оно возникает, когда состояния не отмечают или записывают в разном порядке. Сравните каждую новую запись с предыдущими: если набор объёмов совпал, эти возможности уже рассматривались.

Связь с другими темами

Для решения нужны сравнение чисел, сложение и вычитание объёмов, а также понимание слов «полный» и «пустой сосуд». Эти умения помогают определить свободное место и правильно вычислить, сколько воды перемещается. Перебор состояний и поиск цепочки действий связаны с логическими задачами и алгоритмами. Такой способ поиска пригодится и в задачах, где нужно найти путь от начального положения к цели.

Что запомнить

• Вместимость сосуда ограничивает количество воды в нём.
• Состояние задачи задаётся объёмом воды в каждом сосуде.
• При переливании общий объём воды не меняется.
• Переливание заканчивается, когда исходный сосуд опустел или принимающий наполнился.
• Каждый переход должен соответствовать вместимости сосудов.
• Повтор состояния означает, что те же возможности уже рассматривались.