23.01 Количество программ из A в B

Решение руками

Обозначим число программ, преобразующих число 2 в число n как Тогда число может быть получено либо прибавлением к либо к либо из некоторого числа увеличением на так что откуда так могут быть получены только нечетные числа.
Тогда для четных чисел а для нечетных — ). Заполним таблицу по данным формулам:

Отсюда получаем искомое количество программ — 122.

Идея решения программой (рекурсией)

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

Функция начинается с базовых случаев: 1. Если текущее число a стало больше b, возвращаем 0, так как такой путь уже не может привести к цели. 2. Если a == b, возвращаем 1, так как найден ровно один способ достичь нужного числа.

Если базовые случаи не выполнены, мы рассматриваем возможные шаги: - всегда можем прибавить , это вызов f(a+1, b); - можем прибавить , это вызов f(a+2, b); - можем прибавить «предыдущее» число, то есть a-1. Тогда текущее число увеличивается на a-1, получаем выражение f(a + a - 1, b). Но этот шаг недопустим для числа , так как «предыдущее» будет равно . Поэтому добавляем этот вызов только если a != 1.

Каждый рекурсивный вызов возвращает количество способов для своей ветви, и мы суммируем их, так как все пути независимы. В конце программа печатает f(1, 10), что соответствует количеству способов пройти из в .

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

# Выводим количество программ, преобразующих 1 в 10
print(f(1,10))