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Наглядно это тот же подсчёт путей в графе: из каждого числа ведут стрелки-команды, а под каждой точкой можно надписать, сколько программ в неё приводит.
📌 Как перевести команды в код Каждая команда исполнителя — это одно слагаемое в |