循环序列

Question

给定序列f0，f1，f2。。。由递推关系给出f0=0，f1=1，f2=2和fk=f（k-1）+f（k-3）

写一个程序，用数字k1，k2，…，kn计算这个序列的n个元素。你知道吗

输入格式

输入的第一行包含整数n（1<；=n<；=1000） 第二行包含n个非负整数ki（0<；=ki<；=16000），用空格分隔。你知道吗

输出格式

fk1、fk2…的输出空间分隔值。。。fkn公司。你知道吗

内存限制：10MB

时限：1秒

问题是大值的递归函数超出了极限。你知道吗

def f (a):
    if a <= 2:
        return a
    return f (a - 1) + f (a - 3)


n = int (input ())
nums = list (map (int, input (). split ()))
for i in range (len (nums)):
    if i <len (nums) - 1:
        print (f (nums [i]), end = '')
    else:
        print (f (nums [i]))

我也试着通过一个循环来解决问题，但任务不经过时间（1秒）：

fk1 = 0
fk2 = 0
fk3 = 0
n = int (input ())
nums = list (map (int, input (). split ()))
a = []
for i in range (len (nums)):
    itog = 0
    for j in range (1, nums [i] + 1):
        if j <= 2:
            itog = j
        else:
            if j == 3:
                itog = 0 + 2
                fk1 = itog
                fk2 = 2
                fk3 = 1
            else:
                itog = fk1 + fk3
                fk1, fk2, fk3 = itog, fk1, fk2
    if i <len (nums) - 1:
        print (itog, end = '')
    else:
        print (itog)

你还能怎样解决这个问题，使它在时间和内存上都是最优的呢？你知道吗

Answer 1

关于内存，最好的解决方案可能是迭代法。我想你离答案不远了。我们的想法是首先检查简单情况f（k）=k（即k<；=2），对于所有其他情况k>；2，您可以使用（fi-3，fi-2，fi-1）简单地计算fi，直到i=k。在这个过程中，您需要做的实际上是跟踪最后三个值（类似于您在fk1, fk2, fk3 = itog, fk1, fk2行中所做的）。你知道吗

另一方面，你需要在这里做一件事。如果你只是计算fk1，fk2。。。fkn独立的话，你就完蛋了（除非你使用超高速机器或者Cython实现）。另一方面，没有理由执行n独立计算，您只需计算x=max（k1，k2，…，kn）的fx，同时存储fk1，fk2，…，fkn的每个答案（这将使fx的计算速度减慢一点，但是你只会做一次，而不是做n次。这样，即使n=1000，也可以在1s下求解。你知道吗

在我的机器上，f15000，f15001，…，f16000的独立计算大约需要30秒，“一次完成”的解大约需要0.035秒

老实说，这并不是一个简单的练习，在code review这样的网站上展示您的解决方案会很有趣，以便在找到解决方案后获得一些反馈：）。你知道吗