Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера
Прибавить
Умножить на
Умножить на
Сколько существует программ, для которых при исходном числе 1 результатом является число 38 и при этом траектория вычислений содержит число 12 и не содержит число 18?

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи, можно воспользоваться методом динамического программирования.

Пусть dp[i] - количество способов получить число i. Тогда dp[1] = 1, так как изначальное число 1. Далее мы поочередно применяем каждую из трех команд, пока не достигнем числа 38.

Таким образом, для чисел от 1 до 38, кроме 18, мы будем использовать следующее соотношение:

dp[i] = dp[i-1] + dp[i/2] + dp[i/3] (если i делится на 2 или 3 без остатка)

При этом, для числа 18, необходимо исключить его из общего количества способов:

dp[18] = 0

Таким образом, мы можем заполнить массив dp[i] для всех i от 1 до 38, и получить количество способов преобразовать число 1 в число 38 при условии, что траектория вычислений содержит число 12 и не содержит число 18.

Искомый ответ будет равен:

dp[38] - dp[18]

Таким образом, мы можем использовать метод динамического программирования для эффективного нахождения количества программ, удовлетворяющих условиям задачи.