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

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

Рекурсивное решение основывается на разбиении задачи на два этапа: подсчет всех программ, которые преобразуют число 2 в 10, и всех программ, которые преобразуют число 10 в 30. Общее количество программ равно произведению этих двух чисел, так как каждая траектория до 10 может соединяться с любой траекторией от 10 до 30.

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

- Условия проверки внутри функции:

1. Если равно , возвращаем 1, так как путь успешно завершен.

2. Если больше , возвращаем 0, так как дальнейшее выполнение команд не приведет к цели.

3. Иначе выполняем три рекурсивных вызова: (команда 3), (команда 1), (команда 2) и возвращаем их сумму.

Таким образом, f(2,10) подсчитает все пути от 2 до 10, а f(10,30) — от 10 до 30. Их произведение даст итоговое количество программ.

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

# Общее количество программ равно произведению способов до 10 и от 10 до 30
print(f(2, 10) * f(10, 30))

—

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

Динамический способ решения позволяет последовательно подсчитывать количество программ для каждого числа, используя массив для хранения промежуточных результатов.

- Создаем массив a длиной 93 (выбран с запасом, 31*3) для всех чисел до 30.

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

- Проходим по массиву чисел от 2 до 29:

1. Если текущее число равно 10, сохраняем значение a[i] во вспомогательную переменную b, затем обнуляем весь массив и восстанавливаем только a[i]=b, чтобы исключить траектории, не проходящие через 10.

2. Для каждого числа добавляем количество программ в следующие позиции: a[i+1] += a[i], a[i+3] += a[i], a[i*2] += a[i], чтобы учесть все три команды. - После завершения итерации массив a[30] содержит количество программ, преобразующих число 2 в 30 и проходящих через число 10.

# Создаем массив для хранения количества программ до чисел до 30
a = [0] * 31 * 3
# Начальное положение: один способ быть в числе 2
a[2] = 1
# Перебираем числа от 2 до 29
for i in range(2, 30):
    # Если достигнуто число 10, сохраняем текущее значение и обнуляем массив
    if i == 10:
        b = a[i]      # Сохраняем количество программ, достигших 10
        a = [0] * 31 * 3  # Обнуляем все элементы массива
        a[i] = b      # Восстанавливаем значение для числа 10
    # Обновляем количество программ для следующего числа командой +3
    a[i + 3] += a[i]
    # Обновляем количество программ для числа при умножении на 2
    a[i * 2] += a[i]
    # Обновляем количество программ для следующего числа командой +1
    a[i + 1] += a[i]

# Количество программ, приводящих к числу 30 и проходящих через 10
print(a[30])