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

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

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

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

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

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

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

Чему равно значение выражения (F(247 563) / 519 – 477 × F(247 560)) / F(247 557)?

Ответ:

Решение

# Способ 1
from functools import lru_cache
@lru_cache(None)
def F(n):
    if n < 10:
        return 1
    return (n + 3) * F(n - 3)

for i in range(0, 247564):
    F(i)
print((F(247563) // 519 - 477 * F(247560)) // F(247557))

# Способ 2
f = [0] * 247564
for n in range(0, 247564):
    if n < 10:
        f[n] = 1
    else:
        f[n] = (n + 3) * f[n - 3]
print((f[247563] // 519 - 477 * f[247560]) // f[247557])

# Способ 3 (аналитически)
# F(n) = (n+3)*F(n-3), поэтому F(247 563) = 247 566*F(247 560), а F(247 560) = 247 563*F(247 557).
# F(247 563)/519 = 247 566*247 563/519 * F(247 557), и 247 566*247 563 делится на 519 нацело: получается 118 088 982.
# Ответ: 118 088 982 - 477*247 563 = 118 088 982 - 118 087 551 = 1431.