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

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

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

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

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

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

- f(x+2, y) — шаг, соответствующий команде «прибавь 2»;

- f(x*10, y) — шаг, соответствующий команде «умножь на 10».

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

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

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

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

Второй способ решения — динамическое программирование.

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

1. В начальной точке a[2] = 1, так как существует ровно один способ «быть» в числе 2.

2. Для каждого числа i от до :

- если мы пришли в число i командой «прибавь 2», то добавляем a[i-2];

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

После выполнения цикла в a[40] будет итоговое количество программ.

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

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

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

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