Условие: КЕГЭ № 10718 (Уровень: Средний)
• Статья подготовлена командой itpy
• Полный разбор задачи в Notion
Алгоритм вычисления значения функции 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)?
Решение через Python и комментарии к нему:
Комментарии к коду решения:
- from functools import * - Подключение модуля functools для использования декоратора lru_cache.
- @lru_cache(None) - Применение декоратора lru_cache для кэширования результатов функции f и установки размера кэша как неограниченный.
- def f(n): - Объявление функции f с аргументом n.
- if n < 3: - Если значение n меньше 3, выполнить следующий блок кода.
- return 2 - Вернуть значение 2.
- if n > 2 and n % 2 == 0: - Если значение n больше 2 и остаток от деления на 2 равен 0, выполнить следующий блок кода.
- return 2 * f(n-2) - f(n-1) + 2 - Вернуть результат выражения 2 * f(n-2) - f(n-1) + 2.
- if n > 2 and n % 2 != 0: - Если значение n больше 2 и остаток от деления на 2 не равен 0, выполнить следующий блок кода.
- return 2 * f(n-1) + f(n-2) - 2 - Вернуть результат выражения 2 * f(n-1) + f(n-2) - 2.
- print(f(170)) - Вывести результат вызова функции f с аргументом 170 на экран.
В данном коде @lru_cache(None) используется для кэширования результатов функции f(n) с помощью декоратора lru_cache из модуля functools.
Аргумент None указывает, что размер кэша неограничен.
Кэширование функции позволяет избежать повторных вычислений для одних и тех же входных данных.
При первом вызове функции f(n) результат сохраняется в кэше. При последующих вызовах функции с тем же аргументом, результат будет возвращен из кэша, вместо повторного выполнения вычислений.
Таким образом, в данном коде использование @lru_cache(None) позволяет сэкономить время на вычислениях, так как функция f(n) будет выполняться только один раз для каждого уникального аргумента.