Исполнитель Щелчок преобразует число на экране. У исполнителя есть n команд:
1. Умножить на 2
2. Умножить на 3
3. Умножить на n
где n — число, на котором находится исполнитель. Если исполнитель применяет команды к числу 2, то он может умножить на 2, если число 3, то от 2 до 3 и т.д.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 2 результатом является число 60?
Решение 1 (Рекурсия)
def f(st, fn):
if st == fn:
return 1
if st > fn:
return 0
a = [0] * (st * st)
for i in range(2, st + 1):
a[i] = f(st * i, fn)
return sum(a)
print(f(2, 60))
Решение 2 (Динамика)
a = [0] * 60 * 60
a[2] = 1
for i in range(2, 60):
for j in range(2, i + 1):
a[i * j] += a[i]
print(a[60])