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

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

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

1. Сначала проверяем условие x == y. Если текущее число равно целевому, значит найден один корректный путь, поэтому возвращаем 1.

2. Если текущее число превысило целевое (x > y), дальнейшие операции только увеличат число, а значит нельзя достичь . В этом случае возвращаем 0.

3. Если ни одно из условий не выполнено, выполняем три рекурсивных вызова:

- f(x+1, y) — учитывает вариант применения команды "прибавить 1";

- f(x+4, y) — учитывает вариант применения команды "прибавить 4";

- f(x*4, y) — учитывает вариант применения команды "умножить на 4";

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

Так как траектория должна содержать число 11, общее количество программ вычисляется как произведение количества программ из 3 в 11 и количества программ из 11 в 27: f(3, 11) * f(11, 27).

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

# Вычисляем общее количество программ, проходящих через число 11
# Сначала количество программ от 3 до 11
# Потом количество программ от 11 до 27
# Произведение этих двух чисел даст итоговое количество
print(f(3, 11) * f(11, 27))

—

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

Динамический способ строится на последовательном подсчёте количества программ для каждого числа с использованием массива. Алгоритм реализуется следующим образом:

1. Создаём массив a достаточного размера, заполненный нулями. Каждая ячейка с индексом будет хранить количество программ, которые приводят к числу .

2. В ячейку с индексом 3 записываем 1, так как начинаем с числа 3.

3. Заполняем массив для чисел от 3 до 11 включительно:

- Для каждого числа i добавляем a[i] к a[i+1], учитывая команду "прибавить 1";

- Добавляем a[i] к a[i+4], учитывая команду "прибавить 4";

- Добавляем a[i] к a[i*4], учитывая команду "умножить на 4".

4. После первого этапа обнуляем все элементы массива, кроме элемента с индексом 11, так как траектория должна обязательно содержать число 11.

5. Второй этап: для чисел от 11 до 27 выполняем аналогичные шаги, суммируя количество программ по каждой команде.

6. В итоге элемент a[27] содержит количество программ от 3 до 27 через число 11.

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

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

# Обнуляем все значения кроме ячейки 11, так как траектория должна пройти через 11
for i in range(1000):
    if i != 11:
        a[i] = 0

# Второй этап: считаем количество программ от 11 до 27
for i in range(11, 27 + 1):
    # Переход командой +1
    a[i + 1] += a[i]
    # Переход командой +4
    a[i + 4] += a[i]
    # Переход командой *4
    a[i * 4] += a[i]

# Результат: количество программ, приводящих от 3 к 27 через 11
print(a[27])