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

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

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

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

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

F(n) = 2 × G(n) + G(n – 1);

G(n) = n, если n ≤ 10;

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

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

Ответ:

Решение

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

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

# Способ 3 (аналитически)
# G уменьшает аргумент на 2 и прибавляет 1, пока не дойдёт до n <= 10.
# G(26728) = G(10) + (26728 - 10)/2 = 10 + 13 359 = 13 369; G(26727) = G(9) + (26727 - 9)/2 = 9 + 13 359 = 13 368.
# F(26728) = 2*13 369 + 13 368 = 40 106.

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

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