Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
А. Вычти 3
Б. Вычти 5
В. Найди целую часть от деления на 3
Первая из них уменьшает число на экране на 3, вторая уменьшает число на экране на 5, третья заменяет число на экране на целую часть от деления числа на 3. Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 68 результатом является число 4, и при этом траектория вычислений содержит числа 14 и 35?
Рекурсия:
def f(x, y):
if x < y:
return 0
elif x == y:
return 1
else:
return f(x - 3, y) + f(x - 5, y) + f(x // 3, y)
print(f(68, 35) * f(35, 14) * f(14, 4))
Динамика:
a = [0] * 1000
a[68] = 1
for i in range(68, 3, -1):
if i == 14 or i == 35:
for j in range(i):
a[j] = 0
a[i - 3] += a[i]
a[i - 5] += a[i]
a[i // 3] += a[i]
print(a[4])