Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Увеличь на 1
2. Умножь на 2
3. Умножь на 3
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 8 результатом является число 123, если известно, что после второй команды обязательно должна идти третья?
Программное решение:
# c — номер команды на предыдущем шаге
def f(a, b, c = 0):
if a > b:
return 0
if a == b:
return 1
if c == 2:
return f(a * 3, b, 3)
return f(a + 1, b, 1) + f(a * 2, b, 2) + f(a * 3, b, 3)
print(f(8, 123))
Ответ: 111