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

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

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

def f(n):
    # База для n < 3:
    if n < 3:
        return 2 * n + 10
    # Ветка n кратно 5 и n > 2:
    elif n > 2 and n % 5 == 0:
        return 2 * f(n - 2) + f(n // 5) + n
    # Иначе: n > 2 и n не кратно 5
    else:
        return n + f(n - 2) + 1 + f(n // 3)

# Счётчик подходящих n
ans = 0
# Перебираем n в [1; 300]
for i in range(1, 300 + 1):
    # Проверяем условие F(n) > 10 ** 7
    if f(i) > 10 ** 7:
        ans += 1
print(ans)