Пример 1
Исполнитель преобразует число на экране. У исполнителя есть три команды:
1. Прибавить 1
2. Прибавить 3
3. Умножить на 2
Программа для исполнителя — это последовательность команд. Траектория вычислений — последовательность результатов выполнения всех команд программы.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, и при этом траектория вычислений содержит число 10 и не содержит числа 15?
Показать решение и ответ
1. Траектория обязательно проходит через 10 — считаем отдельно пути 2 → 10 и 10 → 20 и перемножаем.
2. Число 15 запрещено — путь, попавший в 15, не считаем.
3. Число путей из a в b: если a > b или a = 15 — 0 путей, если a = b — 1 путь, иначе сумма путей после каждой из трёх команд.
def f(a, b): # сколько программ переводят a в b
if a > b or a == 15: # перелетели цель или попали в запретное 15 — путь не годится
return 0 # таких программ нет
if a == b: # дошли до цели
return 1 # ровно одна программа — пустая
return f(a + 1, b) + f(a + 3, b) + f(a * 2, b) # пробуем все три команды и складываем
print(f(2, 10) * f(10, 20)) # через 10: пути до 10 × пути от 10 до 20 = 351Ответ: 351