Задача 4: Переливания Есть 2 кувшина: на 3 литра (А) и на 5 литров (В). Изначально оба пусты. Можно: 1) Набрать полный кувшин, 2) Вылить из кувшина, 3) Перелить из одного в другой. Постройте граф состояний, чтобы получить ровно 4 литра в кувшине В.

Решение:

Задача состоит в том, чтобы с помощью двух кувшинов (на 3 и 5 литров) получить ровно 4 литра воды в 5-литровом кувшине. Изначально оба кувшина пусты.

Допустимые действия:

• 1. Набрать полный кувшин (из источника воды).
• 2. Вылить воду из кувшина (в источник воды).
• 3. Перелить воду из одного кувшина в другой до тех пор, пока либо переливающий кувшин не опустеет, либо принимающий кувшин не наполнится.

Граф состояний:

Состояние будем описывать парой чисел (x, y), где x — количество воды в 3-литровом кувшине, а y — количество воды в 5-литровом кувшине.

Начальное состояние: (0, 0).

Целевое состояние: (x, 4), где x может быть любым (0 ≤ x ≤ 3).

Путь к решению:

1. (0, 0) → (3, 0) — Наполняем 3-литровый кувшин.
2. (3, 0) → (0, 3) — Переливаем из 3-литрового в 5-литровый.
3. (0, 3) → (3, 3) — Наполняем 3-литровый кувшин.
4. (3, 3) → (1, 5) — Переливаем из 3-литрового в 5-литровый до заполнения 5-литрового. В 3-литровом остаётся 1 литр.
5. (1, 5) → (1, 0) — Выливаем воду из 5-литрового кувшина.
6. (1, 0) → (0, 1) — Переливаем 1 литр из 3-литрового в 5-литровый.
7. (0, 1) → (3, 1) — Наполняем 3-литровый кувшин.
8. (3, 1) → (4, 0) — Переливаем из 3-литрового в 5-литровый. Теперь в 5-литровом 1+3=4 литра.

Граф состояний (краткое представление):

(0,0) → (3,0) → (0,3) → (3,3) → (1,5) → (1,0) → (0,1) → (3,1) → (4,0)

Примечание: Достигнуто целевое состояние (x, 4).

Ответ: Граф состояний и последовательность действий, приводящих к получению 4 литров в 5-литровом кувшине, представлены выше.