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

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

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

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

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

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

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

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

2. Последовательно получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=f(5)+f(4)+f(2)=3+2+1=6.

3. После достижения числа 6 умножение на 3 использовать нельзя, поскольку получится 18, поэтому нужно набрать прибавлениями 7. Число способов представить 7 как сумму единиц и двоек равно 21.

4. Любая программа, проходящая через 6, однозначно состоит из программы от 2 до 6 и программы от 6 до 13. Поэтому количества перемножаются.
6⋅21=126