Есть кувшины 5 и 3 литра, можно наполнять, опустошать и переливать до заполнения или опустошения. Получите 4 литра.…
Quant ResearchУровень: ПрактикаJug construction and invariant
Есть кувшины 5 и 3 литра, можно наполнять, опустошать и переливать до заполнения или опустошения. Получите 4 литра. Почему кувшины 9 и 3 не подходят?
Подсказки
- Используйте малый кувшин для вычитания 3 из 5.
- В невозможном случае найдите общий делитель.
Ответ
Состояния (большой,малый): (0,0)→(5,0)→(2,3)→(2,0)→(0,2)→(5,2)→(4,3). Для 9 и 3 все разрешённые операции сохраняют кратность объёмов трём; 4 получить нельзя.
Источник и лицензия: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · ответ: редакция Quantoros · перевод: Quantoros