Одна функция: Алгоритм вычисления значения функции F(n), где n –; 3, 2, 2018 · ЕГЭ №16

Условие, ответ и разбор задачи

Рекурсивные алгоритмы

ФИПИ КЭС 3.7ФИПИ

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

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

F(n) = n + F(n − 2), если n ≥ 3.

Чему равно значение выражения F(2022) – F(2018)?

Ответ:

Решение

# Способ 1
from functools import lru_cache
@lru_cache(None)
def F(n):
    if n < 3: return 3
    return n + F(n-2)
for i in range(0, 2023): F(i)
print(F(2022) - F(2018))

# Способ 2
f = [0]*2023
for n in range(0, 2023):
    if n < 3: f[n] = 3
    else: f[n] = n + f[n-2]
print(f[2022] - f[2018])

# Способ 3 (аналитически)
# F(n) = n + F(n-2), значит разность идёт с шагом 2.
# F(2022) - F(2018) = 2022 + 2020 = 4042.

Одна функция: Алгоритм вычисления значения функции F(n), где n –; 3, 2, 2018 · ЕГЭ №16

Похожие задачи