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

Решение

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

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

1. Инициализируем массив достаточного размера, чтобы покрыть все промежуточные значения, и задаём a[2] = 1, так как исходное число 2 имеет один способ быть достигнутым.

2. Проходим по всем числам от 2 до 11 включительно и для каждого числа выполняем три действия:

- a[i + 2] += a[i] — прибавляем все пути, которые достигают , к числу через команду «прибавь 2»;

- a[i + 3] += a[i] — прибавляем пути через команду «прибавь 3»;

- a[i + i - 1] += a[i] — прибавляем пути через команду «прибавь предыдущее», так как третья команда прибавляет число .

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

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

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

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

• 0, если a > b, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (сложение 2, сложение 3, сложение предыдущего числа), если a > b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

Общее количество программ равно f(2, 11).

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