16.01 Одна функция

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: при — ; при и чётном — ; при и нечётном — . Перебираем от до , считаем по определению и ищем первое , для которого сумма цифр равна .

def f(n):
    # База: n < 6
    if n < 6:
        return n
    # Чётный n > 5
    if n % 2 == 0:
        return n + f(n // 2) * 2
    # Нечётный n > 5
    return f(n - 2) + f(n - 1)

# Поиск минимального n с суммой цифр F(n) равной 22
for i in range(1, 1001):
    if sum(map(int, str(f(i)))) == 22:
        print(i)
        break