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

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

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

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

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

F(n) = 2 × (G(n – 3) + 8);

G(n) = 2 × n, если n < 10;

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

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

Ответ:

Решение

# Способ 1
from functools import lru_cache
@lru_cache(None)
def G(n):
    if n < 10: return 2*n
    return G(n-2) + 1
def F(n):
    return 2*(G(n-3) + 8)
for i in range(0, 15546): G(i)
print(F(15548))

# Способ 2
g = [0]*15546
for n in range(0, 15546):
    if n < 10: g[n] = 2*n
    else: g[n] = g[n-2] + 1
print(2*(g[15545] + 8))

# Способ 3 (аналитически)
# G уменьшает аргумент на 2 и прибавляет 1, пока не дойдёт до n < 10.
# 15545 нечётное, спускаемся до 9: шагов (15545 - 9)/2 = 7768, G(9) = 18, значит G(15545) = 18 + 7768 = 7786.
# F(15548) = 2*(G(15545) + 8) = 2*(7786 + 8) = 15588.

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

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