КЕГЭ № 10718 (Уровень: Средний)

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 2 при n < 3;

F(n)= 2 × F(n−2) − F(n−1) + 2, если n > 2 и при этом n чётно;

F(n) = 2 × F(n−1) + F(n−2) − 2, если n > 2 и при этом n нечётно.

Чему равно значение функции F(170)?

Комментарии к коду решения:

1. from functools import * - Подключение модуля functools для использования декоратора lru_cache.
2. @lru_cache(None) - Применение декоратора lru_cache для кэширования результатов функции f и установки размера кэша как неограниченный.
3. def f(n): - Объявление функции f с аргументом n.
4. if n < 3: - Если значение n меньше 3, выполнить следующий блок кода.
5. return 2 - Вернуть значение 2.
6. if n > 2 and n % 2 == 0: - Если значение n больше 2 и остаток от деления на 2 равен 0, выполнить следующий блок кода.
7. return 2 * f(n-2) - f(n-1) + 2 - Вернуть результат выражения 2 * f(n-2) - f(n-1) + 2.
8. if n > 2 and n % 2 != 0: - Если значение n больше 2 и остаток от деления на 2 не равен 0, выполнить следующий блок кода.
9. return 2 * f(n-1) + f(n-2) - 2 - Вернуть результат выражения 2 * f(n-1) + f(n-2) - 2.
10. print(f(170)) - Вывести результат вызова функции f с аргументом 170 на экран.

from functools import *

@lru_cache(None)
def f(n):
    if n < 3:
        return 2
    if n > 2 and n % 2 == 0:
        return 2 * f(n-2) - f(n-1) + 2
    if n > 2 and n % 2 != 0:
        return 2 * f(n-1) + f(n-2) - 2

print(f(170))

В данном коде @lru_cache(None) используется для кэширования результатов функции f(n) с помощью декоратора lru_cache из модуля functools.

Аргумент None указывает, что размер кэша неограничен.

Кэширование функции позволяет избежать повторных вычислений для одних и тех же входных данных.

При первом вызове функции f(n) результат сохраняется в кэше. При последующих вызовах функции с тем же аргументом, результат будет возвращен из кэша, вместо повторного выполнения вычислений.

Таким образом, в данном коде использование @lru_cache(None) позволяет сэкономить время на вычислениях, так как функция f(n) будет выполняться только один раз для каждого уникального аргумента.