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

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

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

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

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

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

F(n) = $n^{2}$ + F(n – 9), если n ≥ 10.

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

Ответ:

Решение

# Способ 1
from functools import lru_cache
@lru_cache(None)
def F(n):
    if n < 10: return n
    return n**2 + F(n-9)
for i in range(0, 5102): F(i)
print(F(5101) - F(5074))

# Способ 2
f = [0]*5102
for n in range(0, 5102):
    if n < 10: f[n] = n
    else: f[n] = n**2 + f[n-9]
print(f[5101] - f[5074])

# Способ 3 (аналитически)
# F(n) = n**2 + F(n-9), значит разность накапливает квадраты с шагом 9.
# 5101 -> 5092 -> 5083 -> 5074, поэтому F(5101) - F(5074) = 5101**2 + 5092**2 + 5083**2 = 77 785 554.

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

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