Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Увеличь на 1
2. Умножь на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 5 результатом является число 299, если известно, что никакую команду нельзя выполнять более трёх раз подряд?
Программное решение:
Способ №1
# c1 - количество совершенных команд 1
# с2 - количество совершенных команд 2
def f(a, b, c1 = 0, c2 = 0):
if a > b:
return 0
if a == b:
return 1
else:
s = 0
if c1 < 3:
s += f(a + 1, b, c1 + 1, 0)
if c2 < 3:
s += f(a * 2, b, 0, c2 + 1)
return s
print(f(5, 299))
Способ №2
# cтрока moves хранит ходы, где
# 1 - увеличить на 1
# 2 - умножить на 2
def func(a, b, moves):
# перешагнули за финиш, либо какая-то команда повторяется подряд 4 раза
if a > b or ’1111’ in moves or ’2222’ in moves:
return 0
if a == b:
return 1
return func(a + 1, b, moves + ’1’) + func(a * 2, b, moves + ’2’)
print(func(5, 299, ’’))