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

Решение динамикой

Мы создаём список a, где индекс i соответствует числу, которое может появиться на экране, а значение a[i] обозначает количество способов попасть в это число, начиная с исходного числа .

1. Так как стартовое число равно , то a[1] = 1. Это означает, что в числе мы можем находиться единственным способом — начав в нём.

2. Далее последовательно для всех чисел от до вычисляем количество способов:

- попасть в число можно из числа , если применить команду «+1»;

- также в число можно попасть из числа , если применить команду «+2».

3. Поэтому a[i] = a[i-1] + a[i-2].

После завершения цикла значение a[10] покажет количество программ, преобразующих число в число .

# Создаем массив для хранения количества способов
a = [0] * (10 + 1)  # Размер массива от 0 до 10 включительно
# В начальной точке (число 1) существует один способ
a[1] = 1
# Заполняем массив для всех чисел от 2 до 10
for i in range(2, 10 + 1):
    # В число i можно попасть из (i-1) и (i-2)
    a[i] = a[i - 1] + a[i - 2]
# Выводим количество программ для числа 10
print(a[10])

Решение рекурсией

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

1. Если текущее число стало больше , возвращаем 0, так как такие траектории не подходят.

2. Если текущее число совпало с , возвращаем 1, так как найден один корректный путь.

3. В остальных случаях количество способов считается как сумма значений:

- f(a+1) — соответствует применению команды «+1»;

- f(a+2) — соответствует применению команды «+2».

Таким образом, функция перебирает все возможные траектории и суммирует количество успешных.

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

# Запускаем функцию от исходного числа 1
print(f(1))