Задание 13 ЕГЭ по информатике · 121720

Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Умножить на 3
2. Прибавить 2
3. Прибавить 3

Первая из них умножает число на экране на 3, вторая увеличивает его на 2, третья увеличивает его на 3.

Программа для Вычислителя — это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 15?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 21, 23, 26.

1. Обозначим через f(n) количество программ, преобразующих число 2 в число n. Для получения n последняя команда могла быть прибавлением 2, прибавлением 3 или умножением на 3.
f(n)=f(n−2)+f(n−3)+f(n/3),еслиnделитсяна3

2. Последовательно вычисляя значения, получаем количество программ из 2 в 15:
f(15)=f(13)+f(12)+f(5)=12+10+1=23

3. Теперь считаем количество программ из 15 в 21. Число 21 можно получить из 19 прибавлением 2 или из 18 прибавлением 3. Поэтому таких программ две.
g(21)=g(19)+g(18)=1+1=2

4. Любая программа, проходящая через 15, однозначно состоит из программы из 2 в 15 и программы из 15 в 21.
23⋅2=46