№13. +1 и «поменяй местами», задача 13-05

№13

+1 и «поменяй местами»

Исполнитель преобразует число на экране. У исполнителя две команды: A. Прибавь 1 B. Поменяй местами A увеличивает число на 1. B применяется только к числу, у которого цифра десятков меньше цифры единиц, и меняет эти две цифры местами. Сколько существует программ, для которых при исходном числе 100 результатом является число 150? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 13 траектория состоит из чисел 14, 41, 42.

Источник: ФИПИ (Основная 18.06.2026), № 31128

Ответвпиши то, что вывела программа

Показать разбор

Напиши функцию f(x, end): сколько программ ведёт из x в end.
Если x == end, верни 1. Если x > end, верни 0: команды только увеличивают число.
Собери список moves: команда A есть всегда.
Команду B добавляй, только если цифра десятков меньше цифры единиц. Новое число собери из сотен, единиц и десятков.
Верни сумму moves и выведи f(100, 150).

def f(x, end):
    if x == end: return 1
    if x > end: return 0
    moves = [f(x + 1, end)]
    if (x // 10) % 10 < x % 10:
        moves.append(f(x // 100 * 100 + x % 10 * 10 + (x // 10) % 10, end))
    return sum(moves)

print(f(100, 150))