3 Как считать программы: рекурсия

Как считать программы: рекурсия

Обозначим за f(x, y) число программ, которые превращают число x в число y. Рассуждаем от конца:

  • если x == y — мы уже на месте, это одна готовая программа (пустая): return 1;

  • если x > y (число проскочило мимо цели и командами только растёт) — дальше цель недостижима: return 0;

  • иначе программа делает любую из доступных команд, а дальше считаем рекурсивно. Число программ — это сумма по всем командам.

Для команд «+1» и «×2» это выглядит так:

def f(x, y):
    if x > y: return 0        # проскочили цель — тупик
    if x == y: return 1        # дошли — одна программа
    return f(x + 1, y) + f(x * 2, y)   # сумма по командам: +1 и ×2

print(f(2, 22))               # 37

Наглядно это тот же подсчёт путей в графе: из каждого числа ведут стрелки-команды, а под каждой точкой можно надписать, сколько программ в неё приводит.

Иллюстрация к заданию 13, рисунок 1

📌 Как перевести команды в код

Каждая команда исполнителя — это одно слагаемое в return. «Прибавить 3» → f(x + 3, y); «умножить на 2» → f(x * 2, y); «умножить на само себя» → f(x * x, y). Сколько команд — столько слагаемых.

Как считать программы: рекурсия — Задание 13 ЕГЭ 2027 | Методички — Профиматика