Есть два сосуда объемом 7 и 11 литров. За одно действие любой сосуд можно наполнить или опустошить. Кроме этого, за одно действие можно переливать воду из одного в другой до тех пор, пока первый сосуд не окажется пустым или второй - полным. Изначально оба сосуда пусты. За какое наименьшее количество действий можно получить в каком-нибудь сосуде 9 литров?

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться алгоритмом Евклида для нахождения наибольшего общего делителя двух чисел.

Найдем НОД(7, 11):
11 = 71 + 4
7 = 41 + 3
4 = 31 + 1
3 = 13

Отсюда получаем, что НОД(7, 11) = 1.

Это означает, что мы можем получить в любом из сосудов количество воды, кратное НОД(7, 11) = 1. То есть мы можем получить в сосуде 9 литров воды за наименьшее количество действий - 9.

Для этого выполним следующую последовательность действий:

Наполним 11-литровый сосуд.Перелить из 11-литрового сосуда в 7-литровый сосуд (останется 4 литра в 11-литровом сосуде).Опустошим 7-литровый сосуд.Перелить 4 литра из 11-литрового сосуда в 7-литровый сосуд.Наполним 11-литровый сосуд.Перелить из 11-литрового сосуда 2 литра в 7-литровый сосуд (останется 9 литров в 11-литровом сосуде).

Таким образом, за 6 действий мы получаем 9 литров воды в одном из сосудов.