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

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

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

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

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

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

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

1. Для подсчёта числа программ, ведущих из 3 в заданное число, используем динамику: последний шаг может быть прибавлением 1, умножением на 2 или прибавлением 3.
f(n)=f(n−1)+f(n/2)+f(n−3)

2. Вычисляя значения от 3 до 10, получаем: f(3)=1, f(4)=1, f(5)=1, f(6)=3, f(7)=4, f(8)=6, f(9)=9, f(10)=14.

3. Значит, существует 14 способов попасть из 3 в 10.

4. Аналогично считаем количество способов из 10 в 15: g(10)=1, g(11)=1, g(12)=1, g(13)=2, g(14)=3, g(15)=4.

5. Любую программу, проходящую через 10, можно однозначно представить как программу из 3 в 10 и программу из 10 в 15.
14⋅4=56