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

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

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

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

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

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

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

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

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

3. Аналогично считаем количество программ из 9 в 14: 1,1,2,3,5,8. Значит, таких программ 8.

4. Любая траектория возрастает, поэтому число 9 встречается ровно один раз. Общее количество программ равно произведению количества способов попасть в 9 и затем из 9 в 14.
25⋅8=200