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

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

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

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

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

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

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

1. Так как все команды увеличивают число, числа 10 и 12 в траектории встречаются именно в указанном порядке. Поэтому искомое количество программ является произведением числа способов пройти три участка.
N(4,14;10,12)=N(4,10)⋅N(10,12)⋅N(12,14)

2. Посчитаем количество способов попасть из 4 в 10. Для каждого числа учитываются переходы из чисел на 1 и 2 меньше, а также из числа вдвое меньшего, если оно целое.
N(4,10)=16

3. Из 10 в 12 можно попасть двумя способами: дважды прибавить 1 или один раз прибавить 2.
N(10,12)=2

4. Из 12 в 14 также существует два способа: дважды прибавить 1 или один раз прибавить 2.
N(12,14)=2

5. Перемножаем количества способов для трёх независимых участков.
16⋅2⋅2=64