Как ускорить выдачу результата 16 задачи из ЕГЭ?

Question

Просто я написал программу по заданию: Функции F(n) и G(n) заданы следующими строчками:

F(1) = G(1) = 1,
F(2) = G(2) = 4,
F(n) = 5 * F(n - 1) - G(n - 2) + 8 * n - 15, при n > 2,
G(n) = 2 * F(n - 2) + 3 * G(n - 1) - n * 2, при n > 2.

В ответ запишите сумму цифр значения, возвращаемого функцией G(n), если в неё передать аргумент n = 53. Вроде ошибок в задании нет, но ответ он не выдал спустя уже 20 минут. То ли что-то неправильно написал, то ли огромная сумма цифр получается.

def f(n):
    if n == 1:
        return 1
    elif n==2:
        return 4
    else: 
        return 5*f(n-1)-g(n-2)+8*n-15

def g(n):
    if n == 1:
        return 1
    elif n==2:
        return 4
    else:
        return 2*f(n-2)+3*g(n-1)-n*2
print(g(53))

Answer 1

Лайфхак для ЕГЭ: используйте lru_cache

from functools import lru_cache


@lru_cache(None)
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 4
    else:
        return 5 * f(n - 1) - g(n - 2) + 8 * n - 15


@lru_cache(None)
def g(n):
    if n == 1:
        return 1
    elif n == 2:
        return 4
    else:
        return 2 * f(n - 2) + 3 * g(n - 1) - n * 2


print('Число:', g(53))
print('Ответ:', sum(map(int, str(g(53)))))

Число: 391294163594391175455446622030378362

Ответ: 152

Answer 2

По-моему, здесь рекурсия не нужна, а, возможно, мешает.
Делаем 2 списка, где сохраняем результаты вычислений f и g, далее рекуррентно подставляем прошлые результаты в текущие формулы.

def G(num):
    f = [0] * (num + 1)
    g = [0] * (num + 1)
    for n in range(1, num + 1):
        if n == 1:
            f[n] = g[n] = 1
        elif n == 2:
            f[n] = g[n] = 4
        else:
            f[n] = 5 * f[n - 1] - g[n - 2] + 8 * n - 15
            g[n] = 2 * f[n - 2] + 3 * g[n - 1] - n * 2
    return g[-1]


num = 53
x = G(num)
s = sum(map(int, str(x)))
print(f'Результат функции G({num}) = {x}; сумма цифр значения, возвращаемого функцией G({num}) = {s}')

Результат функции G(53) = 391294163594391175455446622030378362; сумма цифр значения, возвращаемого функцией G(53) = 152

А вообще можно ограничиться глубиной запоминания в 2 ячейки:

def G(num):
    f = [1, 4]
    g = [1, 4]
    for n in range(3, num + 1):
        a, b = f[-1], g[-1]
        f[-1] = 5 * f[- 1] - g[- 2] + 8 * n - 15
        g[-1] = 2 * f[- 2] + 3 * g[- 1] - n * 2
        f[-2], g[-2] = a, b
    return g[-1]


num = 53
x = G(num)
s = sum(map(int, str(x)))
print(f'Результат функции G({num}) = {x}; сумма цифр значения, возвращаемого функцией G({num}) = {s}')

Результат тот же.

Answer 3

def outer_f():
    f1 = 1
    g1 = 1
    f2 = 4
    g2 = 4

    def inner_f(n):
        nonlocal f1, f2, g1, g2
        if n == 1: return f1
        if n == 2: return f2
        f = 5 * f2 - g1 + 8 * n - 15
        g = 2 * f1 + 3 * g2 - n * 2
        f1 = f2
        f2 = f
        g1 = g2
        g2 = g
        return g

    return inner_f


def res(m):  # Получаем результат функции
    fn = outer_f()
    for i in range(3, m):
        fn(i)
    return fn(m)


def sum_l(d):  # Сумма цифр полученного числа
    return sum(map(int, str(d)))


an = res(53)
print(an)
print(sum_l(an))

391294163594391175455446622030378362  # Результат функции
152                                   # Сумма цифр полученного числа

Answer 4

В дополнение к ответу @ИванИпатов.

lru_cache(None) можно заменить на cache.

У lru_cache есть аргумент - максимальная длинна кеша. Если указать None, она будет не ограничена.

Но у cache она не ограничена по умолчанию.

Так что вот код:

from functools import cache


@cache()
def f(n):
    ...


@cache()
def g(n):
    ...

...

БЛОГ НА HUSL

Как ускорить выдачу результата 16 задачи из ЕГЭ?

Ответы (4 шт):