Признак достижимости объёма в задаче Водолей
В задаче «Водолей» нужный объём воды можно получить переливаниями тогда и только тогда, когда он кратен наибольшему общему делителю вместимостей сосудов и не превышает вместимость большего сосуда. Этот признак быстро проверяет возможность решения до построения последовательности действий.
Формула признака
Сначала находят \(d=\operatorname{НОД}(a,b)\), например алгоритмом Евклида. Затем проверяют остаток от деления \(x\) на \(d\). Если остаток равен нулю и объём не больше большей вместимости, препятствий по этому признаку нет. Сам признак отвечает на вопрос «существует ли решение», но не показывает последовательность переливаний. Для построения действий используют метод переливаний или рассматривают граф состояний Водолея.
Вместимости сосудов равны \(6\) и \(10\) литров. Их НОД равен \(2\). Поэтому достижимы объёмы \(0\), \(2\), \(4\), \(6\), \(8\) и \(10\) литров, а объём \(5\) литров недостижим: \(5\) не делится на \(2\).
Условие проверяет объём в одном сосуде, а не произвольное количество воды сразу в двух сосудах. Кроме того, одной кратности НОД недостаточно: объём должен быть не больше большей вместимости. Например, при вместимостях \(6\) и \(10\) число \(12\) кратно НОД, но получить \(12\) литров в одном сосуде невозможно.
Можно ли получить 7 литров в одном из сосудов вместимостями 9 и 12 литров?
Главное
- Для вместимостей \(a\) и \(b\) найдите \(d=\operatorname{НОД}(a,b)\).
- Объём \(x\) достижим в одном сосуде, если \(x\leq\max(a,b)\) и \(x\) кратен \(d\).
- Признак проверяет существование решения; последовательность переливаний строят отдельно.