Источник: https://kpolyakov.spb.ru/
Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 3
3. Умножь на 2
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 30 и при этом не содержат двух команд «Прибавить 1» подряд?
def f(a, b, c = 0):
if a == b: # Если достигли b
return 1 # Возвращаем 1
if a > b: # Если перешли за b
return 0 # Возвращаем 0
if c == 1: # Если предыдущий ход - прибавить 1,
return f(a + 3, b, 2) + f(a * 2, b, 3) # его не выполняем
# Рекурсивный вызов функции
return f(a + 1, b, 1) + f(a + 3, b, 2) + f(a * 2, b, 3)
print(f(3, 30))
Ответ: 407