23.04 Количество программ из A в B где траектория вычислений НЕ содержит число(-а)

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

Мы используем рекурсивный способ для подсчета количества программ, которые переводят число в число , не проходя через запрещённое число 14. Для этого определяем функцию f(n, m). Внутри функции мы делаем следующие проверки:

1. Если текущее число равно целевому ,

- значит мы достигли результата корректным путем,

- возвращаем 1.

2. Если текущее число превысило или равно запрещённому числу 14,

- дальнейшее движение невозможно,

- возвращаем 0.

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

- прибавляем 1 к текущему числу, вызывая f(n+1, m),

- умножаем текущее число на 2, вызывая f(n*2, m).

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

Таким образом, рекурсия последовательно перебирает все допустимые последовательности команд, исключая запрещённое число 14, и считает количество корректных программ.

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

# Вызываем функцию для исходного числа 5 и целевого числа 31
# и выводим общее количество корректных программ
print(f(5, 31))

—

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

Мы можем использовать динамическое программирование для подсчета количества программ, создавая массив, где каждый индекс соответствует числу, а значение в ячейке — количеству программ, приводящих к этому числу из исходного числа 5, без прохождения через запрещённое число 14.

1. Создаём массив a длиной 32 (для чисел от 0 до 31), изначально заполняем его нулями.

2. Устанавливаем a[5] = 1, так как исходное число 5 даёт ровно один путь к самому себе.

3. Проходим циклом по числам от 6 до 31:

- Для каждого числа добавляем количество способов добраться из (команда «прибавить 1»).

- Если число чётное, добавляем количество способов добраться из (команда «умножить на 2»).

4. После заполнения массива исключаем запрещённое число: a[14] = 0.

5. В конце a[31] содержит количество программ, которые переводят 5 в 31 без прохождения через 14.

# Создаем массив для чисел от 0 до 31, изначально все значения 0
a = [0] * 32
# Начальное число 5, один способ быть в нем
a[5] = 1
# Перебираем числа от 6 до 31 включительно
for i in range(6, 32):
    # Количество способов добраться до i через прибавление 1
    # и через умножение на 2, если i четное
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0)
    # Запрещаем проход через число 14
    a[14] = 0
# Выводим количество программ, которые ведут от 5 к 31
print(a[31])