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

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

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

- Если текущее число совпадает с целевым , возвращаем 1, так как найден корректный путь.

- Если больше , возвращаем 0, так как дальнейшие операции не могут привести к уменьшению числа.

- В остальных случаях функция рекурсивно вызывает сама себя для трёх вариантов команд: , и , суммируя результаты этих вызовов, чтобы получить общее количество программ.

Так как траектория должна содержать число 22, решение разбивается на два этапа: из 3 в 22 и из 22 в 35. Итоговое количество программ равно произведению результатов двух этапов, так как для каждого пути первой части можно использовать любой путь второй части.

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

# Вычисляем общее количество программ через число 22
print(f(3, 22) * f(22, 35))

—

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

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

1. Инициализируем массив нулями и задаём a[3] = 1, так как начинаем с числа 3.

2. Перебираем все числа от 3 до 22 включительно. Для каждого числа прибавляем количество программ к числам , и , чтобы учесть все возможные команды. Таким образом, в массиве к моменту достижения числа 22 будут корректно подсчитаны все пути из 3 в 22.

- После этого необходимо обнулить все значения в массиве, кроме a[22]. Это делается потому, что траектория должна содержать число 22: все пути, которые не достигли числа 22, не удовлетворяют условию, и их нельзя учитывать на следующем этапе.

3. Далее перебираем числа от 22 до 35 включительно, применяя те же команды. На этом этапе a[i] учитывает только пути, которые начинаются из числа 22, гарантируя, что траектория обязательно проходит через него.

4. В конце a[35] содержит количество программ, которые из 3 ведут в 35 и при этом проходят через 22.

# Создаем массив из 1000 элементов, все значения изначально 0
a = [0] * 1000
# Начальное число 3, существует ровно один способ быть в этом положении
a[3] = 1

# Первый этап: от 3 до 22
for i in range(3, 22 + 1):
    # Для каждого числа добавляем количество программ к числам,
    # которые получаются применением каждой команды
    a[i + 3] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]

# Обнуляем все числа, кроме 22, чтобы следующие этапы учитывали только траектории,
# проходящие через 22
for i in range(1000):
    if i != 22:
        a[i] = 0

# Второй этап: от 22 до 35
for i in range(22, 35 + 1):
    # Применяем все три команды и суммируем количество программ
    a[i + 3] += a[i]
    a[i + 4] += a[i]
    a[i * 2] += a[i]

# Выводим итоговое количество программ
print(a[35])