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

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

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

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

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

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

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

1. Так как все команды увеличивают число, траектория может содержать число 9 только один раз. Поэтому программу можно разделить на путь от 3 до 9 и путь от 9 до 14.

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

3. Получаем значения: f(3)=1, f(4)=1, f(5)=2, f(6)=3, f(7)=5, f(8)=8, f(9)=14.

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

5. Общее количество программ равно произведению числа способов пройти обе части пути.
14⋅8=112