23.03 Количество программ из A в B где траектория вычислений содержит число(-а)

Решение программой:

Чтобы найти количество программ, мы воспользуемся функцией, которая вызывает сама себя (рекурсией). Определим функцию f(a, b), где параметр a обозначает текущее число на экране, а параметр b – целевое число, к которому мы хотим прийти.

Функция f(a, b) работает по правилам:

1. Если a > b, возвращаем 0, так как выйти за предел целевого числа нельзя, программа в этом случае не подходит.

2. Если a == b, возвращаем 1. Это значит, что найден один способ дойти от числа a до числа b.

3. В противном случае мы продолжаем движение по траектории, пробуя обе возможные команды:

- команда «прибавить 1» (a + 1),

- команда «умножить на 2» (a * 2).

Сумма результатов этих двух вызовов и будет числом всех возможных программ, начинающихся с текущего состояния.

Так как по условию траектория обязательно должна содержать число 10, мы делим задачу на два этапа:

* сначала считаем количество способов добраться от 1 до 10,

* затем – количество способов добраться от 10 до 20.

Окончательный результат равен произведению этих двух значений, так как каждая траектория до числа 10 может быть продолжена любой траекторией от 10 до 20.

# Определяем функцию f, которая считает количество программ от числа a до числа b
def f(a, b):
    # Если текущее число стало больше целевого, возвращаем 0
    if a > b:
        return 0
    # Если текущее число совпало с целевым, возвращаем 1
    if a == b:
        return 1
    # Иначе пробуем оба варианта перехода:
    # 1) добавляем 1
    # 2) умножаем на 2
    # и суммируем количество найденных путей
    return f(a + 1, b) + f(a * 2, b)

# Считаем количество программ как произведение двух этапов:
# из 1 в 10 и из 10 в 20
print(f(1, 10) * f(10, 20))