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

Аналитическое решение

Количество программ, которые преобразуют число 1 в число обозначим Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда Число “3” можем получить из чисел 1 и 2 — Число “4” получаем из 2 и 3 — Можем заметить, что количество программ для получения числа n находится по формуле — Составим таблицу по данной формуле:

Отсюда видим, что имеем 34 возможных программ для получения числа 9.

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

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

Функция работает по принципу разветвления:

1. Если текущее число a стало больше b, возвращаем 0, так как из этого состояния уже невозможно достичь цели.

2. Если a == b, возвращаем 1, так как найден ровно один путь достижения результата.

3. В остальных случаях мы рассматриваем два возможных шага:

- переход от a к a+1, вызов f(a+1, b);

- переход от a к a+2, вызов f(a+2, b).

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

Чтобы решить задачу, вызываем функцию f(1, 9), то есть считаем количество всех возможных программ, преобразующих число в число .

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

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