3

Как решать задачи с переливаниями?

Например:

Мачеха велела Золушке принести с реки ровно 3 л воды, а в доме всего два ведра: одно емкостью 5 л, а другое вмещает 9 л. Помогите Золушке принести воду

2 ответа 2

12

Такие задачи решаются через сетки возможных состояний.
Этот метод также называется "Метод бильярдного шара"
Обычно имеют пару решений.

  1. (0,9)-(5,4)-(0,4)-(4,0)-(4,9)-(5,8)-(0,8)-(5,3)
  2. (5,0)-(0,5)-(5,5)-(1,9)-(1,0)-(0,1)-(5,1)-(0,6)-(5,6)-(2,9)-(2,0)-(0,2)-(5,2)-(0,7)-(5,7)-(3,9)

Через (5,3)-(0,3)-(3,0)-(3,9) решения замыкаются в цикл.

Сама сетка выглядит как-то так:

введите сюда описание изображения

Это две оси(два ведра: пустое-полное) и переходы(переливания) между состояниями. Синяя линяя соединяет состояния, когда в каком-то ведре нужное количество воды(3л). Это исходная точка для поиска решения.

Горизонталь - ось 9л ведра, наклон вправо - ось 5л ведра. Переходы могут быть вдоль осей(набираем, выливаем) либо поперёк(переливаем из одного в другое).
Переходы "квантовые" - посередине остановиться не можем.

Ну и решать нужно, соответственно, с конца, начиная от требуемого количества. Стартуем с 3л и идём по одному из двух возможных "нетривиальных" путей.
Если построенный цикл замкнулся не включая точки (0,0) - решения нет.

5
  • а как эта сетка строится? :-)
    – Grundy
    28 мая 2018 в 8:16
  • Берёшь, и строишь... Получается сетка... В посте она кривая, на глаз рисовал и нет неиспользованных переходов между состояниями. Горизонталь - ось 9л ведра, наклон вправо - ось 5л ведра. Переходы могут быть вдоль осей(набираем, выливаем) либо поперёк(переливаем из одного в другое). Переходы "квантовые" - посередине остановиться не можем
    – vp_arth
    28 мая 2018 в 8:20
  • цветная сетка хорошо, если gif сделаешь - вообще отлично будет :)
    – Grundy
    28 мая 2018 в 10:03
  • 1
    Объяснение невнятное. 29 мая 2018 в 0:35
  • А если вёдер не 2, а больше? Чисто механически задача уже не решается? 29 мая 2018 в 11:36
1

Решение существует, если требуемый объём кратен наибольшему общему делителю объемов вёдер и не превосходит суммарный объём обоих вёдер.

Для каждой пары (x0, y0) составляем список пар (x, y), которые мы можем получить за одно переливание. Это граф. Начальное состояние (0, 0) - из него любым подходящим алгоритмом поиска пути ищем путь в вершину, один из объёмов которой равен желаемому. Разумеется, граф можно не хранить, однако стоит позаботиться об обработке циклов.

5
  • Кратен? Например, 30 л тоже можно отмерить? 28 мая 2018 в 16:08
  • @АндрейNOP, уточнил.
    – Qwertiy
    28 мая 2018 в 16:16
  • Хм, стало хуже. Надо было просто добавить, что "но не больше суммы объёмов всех вёдер" 28 мая 2018 в 16:19
  • @АндрейNOP, суммы или максимума? Вообще, графовый алгоритм сам разберётся, если пути нет.
    – Qwertiy
    28 мая 2018 в 20:28
  • @АндрейNOP, хотя да, согласен. Набираем разность с максимальным ведром, переливаем в меньшее и наполняем большее полностью - получается как раз то, что надо. Впрочем, если вёдер больше двух, то уже не уверен.
    – Qwertiy
    28 мая 2018 в 20:36

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.