К содержанию
Quantoros

Есть кувшины 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

Похожие вопросы