Исполнитель Бот решил сыграть в игру. Он преобразовывает числа на доске с помощью трёх команд:
1. Вычесть 2
2. Вычесть 3
3. Извлечь корень
Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 25 в число 3?
Рекурсия:
def f(x, y):
if x < y:
return 0
elif x == y:
return 1
else:
return f(x - 2, y) + f(x - 3, y) + f(x ** 0.5, y)
print(f(25, 3) )
Динамика:
a = [0] * 1000
a[25] = 1
for i in range(24, 2, -1):
a[i] = a[i + 2] + a[i + 3] + a[i ** 2]
print(a[3])