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

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

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

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

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

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

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

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

2. Последовательно получаем: 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. Из 11 в 13 можно попасть двумя способами: сразу выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».

4. Общее число программ равно произведению количества путей на двух участках.
25⋅2=50