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

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

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

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

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

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

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

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

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

3. От 9 до 11 возможны две программы: дважды прибавить 1 или сначала прибавить 2, затем прибавить 1.
g(11)=2

4. Из 11 в 12 можно перейти единственным способом — прибавить 1.
h(12)=1

5. Так как траектория должна пройти через 9 и затем через 11, количества способов на трёх участках перемножаются.
17⋅2⋅1=34