循环的迭代

Question

函数f由规则定义

写一个函数f(n),f通过迭代过程计算

我写了这个.并且仍然没有做对.请告知如何解决它.

def f(n):
    if (n<3):
        return n
    else:
        for x in range (n):
            a = f(n-1) + 2*f(n-2) + 3*f(n-3)
            return (a)

Answer 1

只需使用内存缓存:

def f(n):
    if n < 3:
        return n
    a,b,c = 0,1,2
    for i in range(n-2):
        a,b,c = b,c,c+2*b+3*a
    return c

在这个函数中我们a用来表示f(n-3),b表示f(n-2),c对于f(n-1),在每个迭代步骤,我们计算f(n),因此我们移位:a变成b,b变成c并c获得新的价值.我们这样做直到达到要求为止n.

所以最初我们将计算f(3).在这种情况下,a是F(0)= 0,b是F(1)= 1,和c是F(2)= 2.在迭代之后,a取f(1)= 1,b取f(2)= 2,c取f(3)= f(2)+ 2×f(1)+ 3×f(0)= 5,你一直这样做,直到c有权利n.

这将更快地工作,因为在递归变体中,您需要f(n-2)并且f(n-1),但是f(n-1)将在他的路上调用f(n-2)因此引入重复的工作.