Поляков - сложная задача на рекурсию двух функций

Question

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

F(1) = 1; G(1) = 1;
F(n) = F(n–1) – 2·G(n–1), при n >=2 
G(n) = F(n–1) + G(n–1) + n, при n >=2

Чему равна сумма цифр величины G(36)?

def f(n):
    if n == 1:
        return 1
    return f(n-1) - 2 * g(n-1)


def g(n):
    if n == 1:
        return 1
    return f(n-1) + g(n-1) + n


def main():
    result = g(36)
    print(sum(int(n) for n in str(result)))


if __name__ == "__main__":
    main()

решения работает очень медленно. Пробовал функции кешировать, но не помогло. Ответ должен быть 40. Есть идеи как оптимизировать?

Answer 1

Нет смысла городить страшную (из-за ветвления) рекурсию там, где достаточно цикла. В принципе, мемоизация может помочь, но это все равно из серии "зачем просто, если можно сложно".

f = 1
g = 1
for n in range(2,37):
    f,g = f - 2*g, f + g + n

print(sum(int(n) for n in str(g)))

Вычисляется, в общем-то, мгновенно :)

БЛОГ НА HUSL

Поляков - сложная задача на рекурсию двух функций

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