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

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

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

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

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

F(n) = 3 × G(n – 3) + 7;

G(n) = n + 2, если n ≤ 20;

G(n) = G(n – 3) + 1, если n > 20.

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

Ответ:

Решение

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

# Способ 2
g = [0]*37809
for n in range(0, 37809):
    if n <= 20: g[n] = n+2
    else: g[n] = g[n-3] + 1
print(3*g[37808] + 7)

# Способ 3 (аналитически)
# G уменьшает аргумент на 3 и прибавляет 1, пока не дойдёт до n <= 20.
# 37 808 = 20 + 3*12 596, поэтому G(37 808) = G(20) + 12 596 = 22 + 12 596 = 12 618.
# F(37 811) = 3*G(37 808) + 7 = 3*12 618 + 7 = 37 861.

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

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