Найти N-й член заданной последовательности

Question

f (0) = p

f (1) = q

f (2) = r

для n> 2

f (n) = a f (n-1) + b f (n-2) + c * f (n-3) + g (n)

где g (n) = n * n * (n + 1)

p, q, r, a, b, c Вопрос в том, как найти n-й член этой серии.

Пожалуйста, помогите мне найти лучшее решение для этого.

Я пытался решить эту проблему с помощью рекурсии. Но этот способ потребляет много памяти.

Answer 1

Лучше, чем рекурсия, будет памятка . Вам просто нужно знать последние три значения для f (n). Решение в псевдокоде может выглядеть так:

if n == 0:
    return p
else if n == 1:
    return q
else if n == 2:
    return r
else:    
    f_n-3 = p
    f_n-2 = q
    f_n-1 = r
    for i from 3 to n:
        f_new = a * f_n-1 + b * f_n-2 + c * f_n-3 + g(n)
        fn-1 = fn-2
        fn-2 = fn-3
        fn-3 = f_new

return f_new

Таким образом, вам не нужно вызывать метод рекурсивно и сохранять все значения, которые были рассчитаны, в стеке, а просто хранить 4 переменные в своей памяти.

Это должно вычислить намного быстрее и использовать намного меньше памяти.

Answer 2

Проблема в том, что для каждого звонка на f с n > 2 это приводит к трем дополнительным звонкам на f.Например, если мы позвоним f(5), мы получим следующие вызовы:

- f(5)
    - f(4)
        - f(3)
            - f(2)
            - f(1)
            - f(0)
            - g(3)
        - f(2)
        - f(1)
        - g(4)
    - f(3)
        - f(2)
        - f(1)
        - f(0)
        - g(3)
    - f(2)
    - g(5)

Таким образом, мы сделаем один вызов f(5), один вызов f(4), два вызова f(3), четыре вызоваf(2), три вызова на f(1) и два вызова на f(0).

Поскольку мы делаем несколько вызовов, например, на f(3), это означает, что каждый раз это будет стоить ресурсов, особенно еслиf(3) сам сделает дополнительные вызовы.

Мы можем позволить Python сохранить результат вызова функции и вернуть результат, например, с помощью lru_cache [Python-doc] .Этот метод называется памятка :

from functools import <b>lru_cache</b>

def g(n):
    return n * n * (n+1)

<b>@lru_cache(maxsize=32)</b>
def f(n):
    if n <= 2:
        return (p, q, r)[n]
    else:
        return a*f(n-1) + b*f(n-2) + c*f(n-3) + g(n)

Это приведет к графу вызовов, как:

- f(5)
    - f(4)
        - f(3)
            - f(2)
            - f(1)
            - f(0)
            - g(3)
        - g(4)
    - g(5)

Так что теперь мы будем вычислять f(3) только один раз,lru_cache сохранит его в кеше, и если мы вызовем f(3) во второй раз, мы никогда не оценим сам f(3), кеш вернет предварительно вычисленное значение.

Выше здесьоднако может быть оптимизирован, так как мы каждый раз вызываем f(n-1), f(n-2) и f(n-3), нам нужно только сохранить последние три значения и каждый раз вычислять следующее значение на основе последних трех значений и сдвигать переменные, как:

def f(n):
    if n <= 2:
        return (p, q, r)[n]
    f3, f2, f1 = p, q, r
    for i in range(3, n+1):
        f3, f2, f1 = f2, f1, a * f1 + b * f2 + c * f3 + g(i)
    return f1