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

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

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

1. Если текущее число x стало больше числа y, то возвращаем 0, так как такой путь невозможен.

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

3. В остальных случаях мы складываем результаты трёх вызовов:

- f(x+1, y) — переход командой «прибавь 1»;

- f(x+2, y) — переход командой «прибавь 2»;

- f(x+3, y) — переход командой «прибавь 3».

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

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

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

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

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

Изначально установим a[1] = 1, так как существует ровно один способ оказаться в числе — это стартовое состояние.

Далее последовательно заполним массив:

- чтобы попасть в число , можно прийти из числа (командой +1),

- или из числа (командой +2),

- или из числа (командой +3).

Поэтому общее число способов a[i] равно сумме a[i-1] + a[i-2] + a[i-3]. Вычисления нужно вести для всех чисел от до . Ответом задачи будет значение a[14].

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

Решение аналитикой:

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

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

Получается ответ: