Решение: Для начала определим, к какому наименьшему числу от 1 до 15 можно применять только одну команду.
У нас есть две команды — +1 и *3. Наименьшим числом, к которому можно применять только одну из этих команд — 6. Число 6 мы не можем умножить на 3, так как в этом случае получим число 18, а нам нужно 15. К числу 5 же можно и умножить на 3, и увеличить на 1.
Построим граф, отображающий получение числа 15 из числа 6:
На графе из числа 6 получается число 7, расписывать дальше (до 15) смысла нет, так как очевидно, что здесь может быть только одна программа, содержащая команды +1. Общее количество программ для получения 15-ти обведено окружностью, чтобы не запутаться в числах.
Теперь рассмотрим число 5. К нему можно применить уже две программы — прибавь 1 и умножь на 3:
Из числа 6, как мы знаем, существует только одна программа, число 15 — конечное, то есть здесь мы тоже можем указать одну программу.
Рассмотрим число 4:
Из 4 мы можем получить 5 и 12. Из числа 5, как мы знаем, существует две программы для получения 15, к числу 12 мы можем только прибавлять 1, то есть из 12 существует только одна программа.
Рассмотрим число 3:
Из числа 3 мы можем получить числа 4 и 9. Из числа 4 существует три программы для получения 15, к числу 9 мы можем только прибавлять 1, то есть из 9 существует только одна программа для получения 15. Общее количество программ — 4.
Рассмотрим число 2:
Из числа 2 мы можем получить 3 и 6. Из числа 3, как мы знаем, существует 4 программы, из числа 6 — одна программа. Общее количество программ — 5.
Рассмотрим число 1, то, которое нам и требуется:
Из числа 1 мы можем получить числа 2 и 3. Из числа 3 существует 4 программы, из числа 2 — 5 программ. Общее количество программ для получения числа 15 из числа 1 — 9.
Ответ: 9
