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

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которые обозначены латинскими буквами:

A. Прибавь 1
B. Поменяй местами

Первая из этих команд увеличивает число на экране на 1.

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

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

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

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

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

Ответ:

Демонстрационный вариант ЕГЭ 2027 по информатике – задание №13

Решение:

Решение —

Используем рекурсивную функцию f(x, y), которая определяет количество программ, переводящих число x в число y.

def f(x, y):
    if x > y:
        return 0

    if x == y:
        return 1

    if str(x)[1] < str(x)[2]:
        return f(x + 1, y) + f(int(str(x)[0] + str(x)[2] + str(x)[1]), y)
    else:
        return f(x + 1, y)

print(f(100, 141))

def f(x, y):

if x > y:

return 0

if x == y:

return 1

if str(x)[1] < str(x)[2]:

return f(x + 1, y) + f(int(str(x)[0] + str(x)[2] + str(x)[1]), y)

else:

return f(x + 1, y)

print(f(100, 141))

Рассмотрим условия функции.

Если текущее число уже больше конечного, получить число y невозможно:

if x > y:
    return 0

1 2	if x > y: return 0

Если текущее число равно конечному, найден один подходящий способ:

if x == y:
    return 1

1 2	if x == y: return 1

Команда A всегда доступна и увеличивает число на 1:

f(x + 1, y)

1	f(x + 1, y)

Команда B может выполняться только тогда, когда цифра десятков меньше цифры единиц:

if str(x)[1] < str(x)[2]:

1	if str(x)[1] < str(x)[2]:

При выполнении команды B две последние цифры меняются местами. Например, для числа 123 получаем 132:

int(str(x)[0] + str(x)[2] + str(x)[1])

1	int(str(x)[0] + str(x)[2] + str(x)[1])

Если доступны обе команды, складываем количество способов для двух возможных продолжений:

return f(x + 1, y) + f(int(str(x)[0] + str(x)[2] + str(x)[1]), y)

1	return f(x + 1, y) + f(int(str(x)[0] + str(x)[2] + str(x)[1]), y)

Запускаем функцию для исходного числа 100 и конечного числа 141:

print(f(100, 141))

1	print(f(100, 141))

Программа выводит:

16

Ответ: 16