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*4, y) — соответствует команде «умножить на 4».

Сумма этих вызовов даёт общее количество программ от x до y.

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

# Выводим количество программ для преобразования 2 в 17
print(f(2, 17))

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

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

1. Изначально a[2] = 1, так как число — стартовое, и есть ровно один способ «быть в точке старта».

2. Далее для каждого числа i от до вычисляем количество способов:

- складываем количество способов попасть в i-1 и i-2, так как из этих чисел можно перейти в i командами «+1» и «+2»;

- если число i делится на , то к результату добавляем a[i//4], так как в этом случае существует путь, ведущий через умножение на 4.

После окончания цикла в a[17] будет находиться итоговый ответ.

# Создаём массив для хранения количества способов
a = [0] * 100
# В начальной точке (число 2) есть один способ
a[2] = 1
# Перебираем все числа от 3 до 17
for i in range(3, 18):
    # Добавляем количество способов из предыдущих двух чисел
    a[i] = a[i - 1] + a[i - 2]
    # Если число делится на 4, добавляем путь через деление на 4
    if i % 4 == 0:
        a[i] += a[i // 4]
# Выводим количество программ для получения числа 17
print(a[17])

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

Количество программ, которые преобразуют число 2 в число n, обозначим R(n). Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 4, то оно может быть получено командами 1 и 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: .

Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда . Заполним таблицу по данной формуле:

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