Навчання / Бібліотека / Головоломки

Лише швидкі виміри

ГоловоломкиСкладне

У хіміка є порожня колба на $7$ літрів і порожня колба на $11$ літрів, кран і раковина. Одна операція — це: наповнити колбу до країв, повністю вилити колбу або перелити з однієї колби в іншу, доки джерело не стане порожнім чи цільова колба не наповниться. Кількість $g$ виміряно, коли в якійсь колбі рівно $g$ літрів. Для скількох цілих значень $g$ від $1$ до $11$ можна виміряти $g$ , виконавши щонайбільше $6$ операцій?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Знайдіть найменшу кількість операцій для кожного значення окремо й порахуйте ті, що потребують $6$ або менше.

Розв’язок

Пошук у ширину від порожньої пари дає найменшу кількість операцій для кожного значення від $1$ до $11$ .
Значення $7$ і $11$ потребують по $1$ операції, $4$ потребує $2$ , $3$ потребує $4$ , а $8$ потребує $6$ .
Значення $1$ , $2$ , $5$ , $6$ , $9$ і $10$ потребують $8$ , $14$ , $12$ , $10$ , $16$ і $8$ операцій, а це більше за $6$ .
Отже, підходять рівно значення $3$ , $4$ , $7$ , $8$ і $11$ , і їх кількість дорівнює $5$ .

Відповідь: $5$

Наступна задача Назад до бібліотеки