Навчання / Бібліотека / Головоломки
Розділити сироп
Бочка з літрами сиропу стоїть поруч із порожнім слоїком на літрів і порожнім слоїком на літри. На жодній посудині немає позначок. Хід — це одне переливання з однієї посудини в іншу, що триває, доки джерело не стане порожнім чи цільова посудина не наповниться; нічого не розливається, нічого не додається й не забирається. Яка мінімальна кількість ходів потрібна, щоб у бочці було рівно літрів, а в слоїку на літрів — теж рівно ?
Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.
Підказка
Записуйте вміст як трійку (бочка, великий слоїк, малий слоїк) із сумою у кожний момент.
Розв’язок
- Запишемо стан як (бочка, слоїк на , слоїк на ): починаємо з (, , ) і прагнемо до (, , ).
- Одна найкоротша послідовність станів така: (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ), (, , ).
- Перебір усіх позицій на меншій глибині ніколи не досягає (, , ).
- Ця послідовність має ходів.
Відповідь: