Рекурсивные алгоритмы: Алгоритм вычисления значения функции F(n),...

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

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

Профиматика Инф.

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

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

$F(n) = n \times F(n - 1)$ , если $n > 1$ .

Чему равно значение выражения $(F(2042) + 7 \times F(2041)) / F(2040)$ ?

Ответ:

Решение

# Способ 1
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def F(n):
    if n == 1: return 1
    return n * F(n-1)

for i in range(1, 2043): F(i)
print((F(2042) + 7 * F(2041)) // F(2040))

# Способ 2
f = [0]*2043
f[1] = 1
for n in range(2, 2043):
    f[n] = n * f[n-1]
print((f[2042] + 7 * f[2041]) // f[2040])

# Способ 3 (аналитически)
# F(n) = n!, значит F(2042) = 2042*2041*F(2040), F(2041) = 2041*F(2040).
# (F(2042) + 7*F(2041)) / F(2040) = 2041 * (2042 + 7) = 2041 * 2049 = 4182009.

$\textbf{Ответ: 4182009.}$

Рекурсивные алгоритмы: Алгоритм вычисления значения функции F(n),...

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