0У
Все задачи №13
№13

две команды: +1 и «поменяй местами»

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

Источник: ФИПИ (Демо), № 31510

Ответвпиши то, что вывела программа
Показать разбор
  1. Напиши функцию f(x, end): сколько программ ведёт из x в end.
  2. Если x == end, верни 1. Если x > end, верни 0: команды только увеличивают число.
  3. Собери список moves: команда A есть всегда.
  4. Команду B добавляй, только если цифра десятков меньше цифры единиц. Новое число собери из сотен, единиц и десятков.
  5. Верни сумму moves и выведи f(100, 141).
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, 141))