23.02 Количество программ из A в B (на убывание)

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

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

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

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

- Если ни одно из этих условий не выполнено, функция рекурсивно вызывает сама себя три раза: первый раз с аргументом (команда "вычесть 2"), второй раз с аргументом (команда "вычесть 3"), третий раз с аргументом (команда "извлечь квадратный корень"). Сумма этих трёх значений даст количество всех программ, которые переводят в .

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

# Запускаем функцию от 25 до 3 и выводим результат
print(f(25, 3))

—

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

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

- Инициализируем массив длиной, достаточной для всех промежуточных чисел (например, 1000 элементов), и присваиваем a[25] = 1, так как изначально мы находимся в числе 25, и существует ровно один способ быть в этом положении.

- Проходим по массиву в обратном порядке от 24 до 3 (включительно), для каждого числа i вычисляем количество способов дойти до него:

1. Добавляем a[i + 2], так как из числа i+2 можно получить i командой "вычесть 2".

2. Добавляем a[i + 3], так как из числа i+3 можно получить i командой "вычесть 3".

3. Добавляем a[i ** 2], так как из числа î2 можно получить i командой "извлечь квадратный корень".

- После завершения цикла значение a[3] даст общее количество программ, которые переводят 25 в 3.

# Создаем массив для хранения количества способов для чисел до 1000
a = [0] * 1000
# Исходное число 25 имеет один способ быть достигнутым
a[25] = 1
# Проходим по всем числам от 24 до 3 включительно
for i in range(24, 2, -1):
    # Количество способов добраться до i равно сумме:
    # из i+2 командой "вычесть 2",
    # из i+3 командой "вычесть 3",
    # из i**2 командой "извлечь корень"
    a[i] = a[i + 2] + a[i + 3] + a[i ** 2]
# Выводим количество программ, приводящих от 25 к 3
print(a[3])