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

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

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

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

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

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

Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

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

2. Последнее слагаемое учитывается только для чётных n. Получаем значения до числа 11:
f(4)=1, f(5)=1, f(6)=2, f(7)=3, f(8)=6, f(9)=9, f(10)=16, f(11)=25

3. Значит, существует 25 программ, переводящих 4 в 11.

4. Теперь считаем количество программ от 11 до 15. Аналогично:
g(11)=1, g(12)=1, g(13)=2, g(14)=3, g(15)=5

5. Любая программа, проходящая через 11, состоит из программы из 4 в 11 и программы из 11 в 15. Поэтому количества перемножаются.
25⋅5=125