查找提供的序列的第N个术语 [英] Find Nth term of provided sequence

问题描述

f（0）= p

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）

f(n) = af(n-1) + bf(n-2) + c*f(n-3) + g(n)

其中g （n）= n * n *（n + 1）

where g(n) = n* n* (n+1)

p，q，r，a，b，c被赋予
问题是，如何找到本系列的第n个术语。

p,q,r,a,b,c are given The question is, How to find the nth term of this series.

请帮助我找到一个更好的解决方案。

Please help me in finding a better solution for this.

我尝试使用递归解决此问题。但这会消耗大量内存。

I have tried solving this using recursion. But that way is consuming high memory.

推荐答案

比递归更好的方法是记忆力。您只需要知道f（n）的最后三个值即可。
伪代码的解决方案如下所示：

A better way than recursion would be memoization. You just need to know the last three values for f(n). A solution in pseudocode could look like this:

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个变量即可。

This way you don't need to call the method recursively and keep all the values, that were calculated, on the stack, but just keep 4 variables in your memeory.

这应该可以更快地计算并使用更少的内存。

This should calculate much faster and use much less memory.

这篇关于查找提供的序列的第N个术语的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！