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

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

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

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

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

F(n) = n, если n < 10;

F(n) = (n – 2) × F(n – 5), если n ≥ 10.

Чему равно значение выражения (F(3220) – 2 × F(3215)) / F(3210)?

В ответе запишите целую часть полученного числа.

Ответ:

Решение

# Способ 1
from functools import lru_cache
@lru_cache(None)
def F(n):
    if n < 10: return n
    return (n-2)*F(n-5)
for i in range(0, 3221): F(i)
print((F(3220) - 2*F(3215)) // F(3210))

# Способ 2
f = [0]*3221
for n in range(0, 3221):
    if n < 10: f[n] = n
    else: f[n] = (n-2)*f[n-5]
print((f[3220] - 2*f[3215]) // f[3210])

# Способ 3 (аналитически)
# F(n) = (n-2)*F(n-5), поэтому F(3220) = 3218*F(3215), а F(3215) = 3213*F(3210).
# (F(3220) - 2*F(3215)) / F(3210) = (3218 - 2)*F(3215)/F(3210) = 3216*3213 = 10 333 008.

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

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