Исполнитель ДЖАСТДЕНСЕР преобразует число на экране, а должен танцевать… У исполнителя есть есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2.
3. Умножить на 3.
Первая команда увеличивает число на экране 2, вторая увеличивает его в два раза, а третья увеличивает его в три раза. Программа для исполнителя ДЖАСТДЕНСЕР — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 35, при этом траектория содержит число 28 и не содержит 19?
Рекурсия:
# Определяем функцию f с двумя аргументами: n и m
def f(n, m):
# Если n и m равны, функция возвращает 1
# Это условие может служить в качестве базового случая для рекурсии
if n == m:
return 1
# Если n больше m или n равно 19, функция возвращает 0
# Это ещё один базовый случай для рекурсии
if n > m or n == 19:
return 0
# Если n меньше m, функция вызывает себя три раза с различными аргументами:
# - один раз с n увеличенным на 2
# - один раз с n удвоенным
# - один раз с n утроенным
# и возвращает сумму результатов этих вызовов
if n < m:
return f(n+2, m) + f(n*2, m) + f(n*3, m)
# Наконец, мы вызываем функцию f с различными аргументами и печатаем результат их произведения
print(f(3, 28) * f(28, 35))
Динамика:
a = [0] * 36
a[3] = 1
for i in range(4, 36):
a[i] = a[i - 2] + a[i // 2] * (i % 2 == 0) + a[i // 3] * (i % 3 == 0)
if i == 28:
for j in range(i):
a[j] = 0
if i == 19:
a[i] = 0
print(a[35])