ЕГЭ. Информатика. Задача с роботом Исполнитель Робот преобразует число, записанное на экране. У
исполнителя есть две команды, которым присвоены номера:
1.Прибавить 1
2. Умножить на 4
Первая из них увеличивает число на экране на 1, вторая умножает на 4.
Программа для исполнителя Робот – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное
число 2 в число 48 и при этом траектория вычислений программы
содержит число 4 и не содержит числа 12?

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

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

Обозначим dp[i] - количество программ, которые преобразуют число 2 в число i и при этом на траектории вычислений программы есть число 4 и не содержится число 12.

Сначала рассмотрим базовые случаи:
dp[2] = 1

Далее, для каждого i от 3 до 48 (так как нужно преобразовать из 2 в 48), можно использовать рекуррентное соотношение:
dp[i] = dp[i-1] + dp[i/4] (если i делится на 4)

Таким образом, можно найти количество программ, удовлетворяющих условиям задачи, пройдя от dp[2] до dp[48] с использованием указанного рекуррентного соотношения.

После проведения всех необходимых вычислений, получим ответ.