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

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

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

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10?

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

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

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

2. Последовательно вычисляем количество программ до числа 10: f(1)=1, f(2)=2, f(3)=2, f(4)=4, f(5)=4, f(6)=6, f(7)=6, f(8)=10, f(9)=10, f(10)=14.
f(10)=f(9)+f(5)=10+4=14

3. Из числа 10 в число 20 можно попасть двумя способами: девять раз прибавить 1 или сразу умножить 10 на 2.
g(10)=2

4. Каждая программа от 1 до 10 можно соединить с каждой программой от 10 до 20.
14⋅2=28