Задача к ЕГЭ по информатике на тему «одна функция» №9

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

# Аргумент n - целое неотрицательное число по условию
def f(n):
    if int(n) != n or n < 0:  # Проверка на недопустимое значение n
        # Возвращаем отрицательное и огромное по модулю число,
        # которое не повлияет на вычисление 10**5
        return -9999999999
    if n < 3:
        return 2 * n * n + 2
    elif n > 2 and n % 5 == 0:
        return 2 * f(n - 2) + f(n / 2) + n
    elif n > 2 and n % 5 != 0:
        return n * n + f(n - 2) + 1 + f(n / 3)


ans = 0  # Переменная-счётчик для ответа
for i in range(1, 301):  # Перебор значений n из отрезка [1; 300]
    if f(i) > 10 ** 5:  # Проверка значения функции
        ans += 1
print(ans)

Динамическое решение

# Создаём список значений функции f(n), аргумент n - индекс ячейки
# Заполняем список неопределёнными значениями 0
f = [0] * (300 + 1)
for n in range(1, 300 + 1):  # Перебираем n для заполнения функции
    if n < 3:
        f[n] = 2 * n * n + 2
    if n > 2 and n % 5 == 0:
        # По условию деление n/2 обычное,
        # а функция принимает только целые неотрицательные значения
        # Поэтому проверяем, что n можно поделить нацело без остатка,
        # а также функция определена для аргументов (n-2) и (n/2),
        # то есть имеет ненулевое значение. Тогда можно считать f[n]
        if (n % 2 == 0) and (f[n - 2] != 0) and (f[n // 2] != 0):
            f[n] = 2 * f[n - 2] + f[n // 2] + n
    if n > 2 and n % 5 != 0:
        # Аналогичная ситуация, как с n/2
        if (n % 3 == 0) and (f[n - 2] != 0) and (f[n // 3] != 0):
            f[n] = n * n + f[n - 2] + 1 + f[n // 3]

ans = 0  # Счётчик для ответа
for n in range(1, 300 + 1):  # перебираем n для проверки итоговых значений функции
    if f[n] > 10 ** 5:
        ans += 1

print(ans)