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

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

Первая из этих команд увеличивает число на экране на 1. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.

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

Сколько существует программ, для которых при исходном числе 101 результатом является число 152?

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

Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.

1. Введём f(n) — количество программ, переводящих исходное число 101 в число n. Для исходного числа f(101)=1.

2. Переход по команде A возможен из числа n−1, поэтому он добавляет f(n−1) способов.

3. Переход по команде B учитывается для тех чисел, у которых цифра десятков меньше цифры единиц: после перестановки двух последних цифр получается новое достижимое число. Для каждого такого перехода добавляется количество способов достижения исходного числа.

4. Последовательно перебирая все достижимые числа от 101 до 152 и суммируя количества способов для переходов A и B, получаем f(152)=42.