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

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

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

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

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

F(n) = 1 при n = 1;

F(n) = 2 n F(n − 1), если n > 1.

Чему равно значение выражения (F(2024) + 2 F(2023)) / F(2022)?

Ответ:

Решение

# Способ 1
from functools import lru_cache
@lru_cache(None)
def F(n):
    if n == 1: return 1
    return 2*n*F(n-1)
for i in range(1, 2025): F(i)
print((F(2024) + 2*F(2023)) // F(2022))

# Способ 2
f = [0]*2025
f[1] = 1
for n in range(2, 2025):
    f[n] = 2*n*f[n-1]
print((f[2024] + 2*f[2023]) // f[2022])

# Способ 3 (аналитически)
# F(n) = 2n*F(n-1), поэтому F(2024)/F(2022) = (2*2024)*(2*2023) = 4*2024*2023, F(2023)/F(2022) = 2*2023.
# Ответ: 4*2024*2023 + 2*2*2023 = 4*2023*(2024 + 1) = 4*2023*2025 = 16 386 300.

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

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