Лекция: ЗАДАЧА О ТРЕХ СОСУДАХ

Рассмотрим задачу о трех сосудах. Имеется три сосуда емкостью 8, 5 и 3 литра. В первом сосуде содержится 8 литров вина. Требуется разделить вино поровну, пользуясь только этими тремя сосудами, т.е. алгоритм переливания.

Информацию об объемах сосудов представим фактом:

объемы(8,5,3).

Правило переливания из одного сосуда в другой:

Чтобы перелить из одного сосуда в другой, надо, чтобы в сосуде «откуда» было какое-то количество вина, а в сосуде «куда»- свободное место. Если в сосуде «откуда» вина больше чем

свободного места в сосуде «куда», то переливается количество, равное свободному объему сосуда «куда», в противном случае из сосуда «откуда» выливается все вино, т.е. переливаемое количество равно минимуму из количества вина в сосуде «откуда» и свободного места в сосуде «куда». После переливания вина в сосуде «откуда» станет меньше на перелитое количество, а в сосуде «куда» увеличится на столько же. Количество вина в оставшемся третьем сосуде не

изменится. Затем надо повторить переливание из нового состояния так, чтобы после ряда переливаний получить в двух первых сосудах по 4 литра.

В этой задаче ситуацию можно описать следующим образом

состояние(Количество_вина_в_первом_сосуде, Количество_вина_во_втором_сосуде,

Количество_вина_в_третьем_сосуде).

дуги пространства состояний определяются разрешенным переходам из одной ситуации в другую, т.е. правилами переливаниями. Задача отыскания решения эквивалентна задаче построения пути между начальной ситуацией (8,0,0) и конечной ситуацией (4,0,0).

 

 

Чтобы не «зацикливаться» будем хранить все пройденные состояния в списке в виде структур сост(В_первом, Во_втором, В_третьем) и проверять каждое новое состояние на принадлежность этому списку.

Для трех сосудов возможно шесть вариантов переливаний и соответственно 6 правил (1→2, 1→3, 2→1, 2→3, 3→1, 3→2) + правило остановки.

еще рефераты
Еще работы по информатике