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

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

В задаче дан рекурсивный алгоритм: функция F(n) вызывает саму себя с другими аргументами (n - 2, n / 2 или n / 3). Реализуем этот алгоритм на Python, для этого создадим функцию def f(n). Внутри функции создадим ветвление: n < 3, n > 2 и n кратно 5, n > 2, n некратно 5. Для каждого случая будем возвращать описанное в условии выражение, таким образом и будет запущенна рекурсия. Однако важно учетсть, что при делении (n / 2 или n / 3) могут получаться дробные числа, а по условию n должно быть целым. Поэтому добавим проверку: если n не целое, вернём очень маленькое число (например, -999999999), чтобы оно не влияло на результат.

Затем, останется только запустить функцию f для n из отрезка [1; 300] и сосчитать количество таких n, при которых результат функции превышает , для этого воспользуемся циклом for.

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

    # Базовый случай: n < 3
    if n < 3:
        return 2 * n * n + 2

    # Рекурсивный случай 1: n > 2 и кратно 5
    elif n > 2 and n % 5 == 0:
        return 2 * f(n - 2) + f(n / 2) + n

    # Рекурсивный случай 2: n > 2 и не кратно 5
    elif n > 2 and n % 5 != 0:
        return n * n + f(n - 2) + 1 + f(n / 3)

# Переменная-счётчик для ответа
ans = 0

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

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

Для использования метода динамического программирования создадим массив f, где f[n] хранит значение F(n). Реализуем программу, которая будет заполнять массив последовательно от n = 1 до n = 300, для этого организуем перебор от 1 дл 300 с помощью цикла for. Внутри цикла для каждого n проверяем условия и вычисляем f[n] на основе уже вычисленных значений.

При ветвлении по условиям из задачи важно также учесть два момента:

1. n делится на 2 (или 3 в завсимости от ветки) без остатка, так как n / 2 (или n / 3) должно быть целым.

2. f[n-2], f[n//2] и f[n//3] уже вычислены (не равны 0), некоторые значения могут оказаться невычисленными, если для их расчёта не выполнились условия в предыдущих шагах (например, n не делилось на нужное число или требуемые рекурсивные вызовы тоже остались невычисленными).

В конце остается просто подсчитать, сколько значений в массиве превышают 100000.

# Создаем список значений функции F(n), где индекс соответствует n.
# Изначально заполняем нулями (неопределенные значения).
f = [0] * (300 + 1) # Индексы от 0 до 300

# Заполняем массив f для n от 1 до 300.
for n in range(1, 300 + 1):
    # Базовый случай: n < 3
    if n < 3:
        f[n] = 2 * n * n + 2

    # Случай 1: n > 2 и кратно 5
    if n > 2 and n % 5 == 0:
        # Проверяем, что n делится на 2 без остатка (так как n/2 должно быть целым),
        # и что f[n-2] и f[n//2] уже вычислены (не равны 0).
        if (n % 2 == 0) and (f[n - 2] != 0) and (f[n // 2] != 0):
            f[n] = 2 * f[n - 2] + f[n // 2] + n

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

print(ans)