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

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

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

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

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

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

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

1. Обозначим через f(n) число программ, переводящих число 1 в число n. В число n можно попасть командами «прибавить 1» и «прибавить 2», а также командой умножения на 3, если n делится на 3.
f(n)=f(n−1)+f(n−2)+{f(n/3),&n⋮3; 0,&n не делится на 3

2. Последовательно вычисляя значения, получаем: f(1)=1, f(2)=1, f(3)=3, f(4)=4, f(5)=7, f(6)=12, f(7)=19, f(8)=31, f(9)=53.

3. Количество программ, переводящих 9 в 13, считаем аналогично, не используя значения меньше 9: g(9)=1, g(10)=1, g(11)=2, g(12)=3, g(13)=5.

4. Любая программа, проходящая через 9, однозначно распадается на путь от 1 до 9 и путь от 9 до 13. Поэтому количества путей перемножаются.
53⋅5=265