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

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

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

1. Если текущее число совпало с целевым числом , то мы нашли одну корректную программу, и функция возвращает 1.

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

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

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

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

- вызываем f(x*3, y), что соответствует команде "умножить на 3".

Чтобы учесть условие, что траектория должна содержать число 18, мы разбиваем задачу на два этапа: сначала считаем количество программ от 4 до 18, затем от 18 до 31. Итоговое количество программ равно произведению этих двух результатов, так как для каждой программы из первой части можно использовать любую программу из второй части.

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

# Вычисляем количество программ для двух этапов и перемножаем
# Первый этап: от 4 до 18
# Второй этап: от 18 до 31
print(f(4, 18) * f(18, 31))

—

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

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

1. Инициализируем массив нулями, длина массива равна 32, так как максимальное число, до которого нужно дойти, — 31.

2. В ячейку с индексом 4 записываем 1, так как начальное число — 4, и существует ровно один способ быть в этом состоянии.

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

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

- Добавляем количество программ из (команда "+2").

- Если делится на 3, добавляем количество программ из (команда "*3").

4. Чтобы учесть, что траектория должна содержать число 18, после заполнения ячейки с индексом 18 мы обнуляем все предыдущие значения массива (индексы меньше 18). Это гарантирует, что все найденные программы обязательно проходят через число 18.

5. После завершения цикла ячейка с индексом 31 хранит количество программ, которые преобразуют 4 в 31 с обязательным прохождением числа 18.

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