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

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

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

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

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

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

F(n) = n – 1 + F(n – 1), если n ≥ 10.

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

Ответ:

Решение

# Способ 1
from functools import lru_cache
@lru_cache(None)
def F(n):
    if n < 10: return n
    return n - 1 + F(n-1)
for i in range(0, 8568): F(i)
print(F(8567) - F(8563))

# Способ 2
f = [0]*8568
for n in range(0, 8568):
    if n < 10: f[n] = n
    else: f[n] = n - 1 + f[n-1]
print(f[8567] - f[8563])

# Способ 3 (аналитически)
# F(n) - F(n-1) = n - 1.
# F(8567) - F(8563) = 8566 + 8565 + 8564 + 8563 = 34 258.

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

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