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

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

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

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

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

- Если ни одно из условий не выполнено, функция рекурсивно вызывает сама себя для каждого возможного действия:

1. x - 2 — уменьшение на 2, прибавляем результат к общему числу программ.

2. x - 3 — уменьшение на 3, прибавляем результат к общему числу программ.

3. pow(x, 0.5) — извлечение квадратного корня возведением в степень 0.5, но только если число неотрицательное; добавляем результат к общему числу программ.

Таким образом, функция постепенно перебирает все возможные последовательности команд от числа 25 до числа 3. Каждый рекурсивный вызов делит задачу на подзадачи, соответствующие одному шагу программы, и суммирует результаты. Вызов F(25, 3) вернёт итоговое количество всех программ.

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

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