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

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

Мы используем рекурсивный подход, чтобы построить функцию f(s, fi, flag), которая считает количество программ, приводящих число s к числу fi с учётом условий: траектория должна содержать число 50 и не содержать число 99.

1. Сначала мы проверяем базовые случаи:

- Если текущее число s превысило целевое fi, путь невозможен, возвращаем 0.

- Если текущее число равно 99, путь запрещён, возвращаем 0.

- Если текущее число равно 50, отмечаем флаг flag = True, чтобы зафиксировать, что условие "траектория содержит 50"выполнено.

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

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

- прибавляем 2 (s + 2)

- умножаем на 3 (s * 3)

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

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

# Запускаем функцию с начальным числом 10, целевым 100 и флагом False
print(f(10, 100, False))

—

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

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

1. Создаём массив длиной 101 (от 0 до 100) и заполняем его нулями.

2. Начальное число 10 имеет один способ быть достигнутым, поэтому a[10] = 1.

3. Проходим по всем числам от 11 до 100 включительно:

- Считаем количество программ, которые ведут в число i из числа i-2 командой "прибавить 2".

- Если i делится на 3, добавляем a[i//3], так как можно прийти командой "умножить на 3".

- Если число равно 99, обнуляем a[i], так как траектория через 99 запрещена.

- Если число равно 50, обнуляем все предыдущие значения a[j] для j < 50, чтобы обеспечить прохождение через 50.

4. В конце a[100] содержит количество программ, соответствующих условиям.

# Создаем массив для подсчета количества программ для чисел от 0 до 100
a = [0] * 101
# Начальное число 10 имеет один способ быть достигнутым
a[10] = 1
# Перебираем все числа от 11 до 100
for i in range(11, 101):
    # Количество программ для числа i складывается из:
    # 1) прибавить 2
    # 2) умножить на 3, если i делится на 3
    a[i] = a[i - 2] + a[i // 3] * (i % 3 == 0)
    # Если число равно запрещенному 99, путь невозможен
    if i == 99:
        a[i] = 0
    # Если число равно 50, обнуляем все предыдущие значения,
    # чтобы гарантировать, что траектория проходит через 50
    if i == 50:
        for j in range(i):
            a[j] = 0

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