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

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

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

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

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

- В остальных случаях функция вызывает сама себя трижды: f(start+1, finish) (команда "прибавь 1"), f(start+5, finish) (команда "прибавь 5") и f(start*start, finish) (команда "возвести в квадрат"). Сумма этих трёх вызовов даёт общее количество программ для данного промежутка.

Поскольку траектория должна содержать число 5, решаем задачу по частям: сначала считаем количество программ от 2 до 5, затем от 5 до 26, и перемножаем результаты, так как каждый путь первой части может сочетаться с любым путём второй части.

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

# Считаем количество программ от 2 до 5 и от 5 до 26
# Перемножаем результаты для учета условия о траектории
print(f(2, 5) * f(5, 26))

—

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

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

1. Создаем массив a большого размера (например, 10000 элементов) и инициализируем его нулями.

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

3. Перебираем все числа от 2 до 26 (целевое число включительно). На каждом шаге делаем следующее:

- Если текущее число равно 5 (обязательное число в траектории), обнуляем все будущие значения массива от 6 до 26, чтобы учесть требование, что 5 должна обязательно встретиться.

- Для каждого числа добавляем количество способов для текущего числа в ячейки i+1, i+5 и i*i, соответствующие действиям команд "прибавь 1 "прибавь 5"и "возвести в квадрат". Это позволяет аккумулировать все возможные траектории до каждого числа.

4. После завершения цикла в ячейке с индексом 26 хранится общее количество программ, которые начинаются с 2, проходят через 5 и заканчиваются на 26.

# Создаем массив для подсчета количества программ
a = [0] * 10000
# Исходное число 2 — один способ быть в этом состоянии
a[2] = 1

# Проходим по всем числам от 2 до 26
for i in range(2, 26):
    # Если текущее число равно обязательному числу 5
    if i == 5:
        # Обнуляем все будущие числа до 26,
        # чтобы учесть условие прохождения через 5
        for j in range(6, 27):
            a[j] = 0
    # Добавляем текущие способы в следующие числа согласно командам
    a[i + 1] += a[i]   # команда "прибавь 1"
    a[i + 5] += a[i]   # команда "прибавь 5"
    a[i * i] += a[i]   # команда "возвести в квадрат"

# Количество программ, удовлетворяющих условиям, хранится в a[26]
print(a[26])