Шаблон рекурсивной функции
# Рекурсивная функция
def rec(now, last, step):
if now == last: # Проверка, что получили нужное число
return 1
if now > last: # Проверка, что превысили нужное число
return 0
# Вызов рекурсивной функции с учетом заданных команд изменения числа и условия неповторения одинаковых команд
return rec(now + ???, last, step) + ???
# Основная программа
print(rec(???)) # Вызов рекурсивной функции с начальными значениями
Задача
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает число на 2, третья увеличивает число в 2 раза.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 5 результатом является число 20, и при этом в программах нет двух одинаковых команд, идущих подряд?