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

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

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

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

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

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

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

1. Рассмотрим все допустимые переходы из исходного состояния 100. Команда A увеличивает текущее число на 1, а команда B выполняет перестановку двух последних цифр только при условии, что цифра десятков меньше цифры единиц.

2. Последовательно перебираем достижимые числа и для каждого числа сохраняем количество программ, которыми оно получено. При переходе по команде A значение увеличивается на 1; при допустимом переходе по команде B добавляется способ перейти к числу с переставленными последними цифрами.

3. После исключения недопустимых применений команды B и подсчёта всех путей от 100 до 141 количество программ равно 16.
N(141)=16