Каждый с пелёнок помнит эту задачу. И в "Крепком орешке - 3" её решали, и в незавбенных "Космических рейнджерах" и не упомню где ещё. Есть два сосуда, на 3 и 5 литров, и нужно организовать в одном из них ровно 4 литра. И алгоритм решения тоже тайны не составляет.
Алгоритм - это вещь, конечно, хорошая, но не отвечающая на некоторые вопросы. В частности, всегда ли задача имеет решение? Скажем, если взять ёмкости 6 и 4 литра, можно ли этим способом получить 3 литра?
Чтобы разобраться в вопросе, немного изменим алгоритм. Будем не выливать воду, чтобы освободить сосуд, а добавлять новый пустой того же объёма. Тогда процедуру решения задачи можно проиллюстрировать следующим образом:
Как видим, ничего принципиально не поменялось. Но зато появилась возможность построить математическую модель задачи:
У нас получилось, что три наполнения меньшего сосуда и одно наполнение большего удовлетворяют уравнению очень знакомого вида:
Ax - By = C
Это, как не трудно убедиться, самое обычное линейное диофантово уравнение (с точностью до замены y' = -y). А существование решения этого уравнения в целых числах зависит от того, является ли наибольший общий делитель коэффициентов A и B заодно и делителем числа С из правой части уравнения.
Таким образом, с ёмкостями 6 и 4 литра получить 3 литра не удастся (НОД(4, 6) = 2 - не является делителем тройки). А вот, например, при помощи 7 и 3 литра получить 4 литра - вполне, пусть и не самым коротким путём:
Вышеприведенная иллюстрация показывает, что алгоритм, в котором наполняется сначала меньший сосуд, не всегда оказывается оптимальным. Можно рассмотреть ситуацию, когда всегда наполняется только больший сосуд, а потом переливается в меньший. Этот случай тоже приводит к линейному диофантову уравнению с точностью до перемены знаков:
Очевидно, количество усилий, необходимых для получения результата с помощью того или иного алгоритма, пропорционально суммарному количеству наполнений/выливаний сосудов, так что если требуется найти оптимальный порядок действий, придется рассмотреть решения обоих уравнений:
Ax - By = C и By - Ax = C
и выбрать вариант с минимальной суммой x + y.