最后3个数字的腓波纳纤类序列

Question

有没有一种非递归的方法可以通过加上最后3个数字来生成“类似斐波那契”的序列？在

这是我尝试的递归方法。在

def fib3(n):
    if n < 3:
        return 1
    else:
        return fib3(n-1) + fib3(n-2) + fib3(n-3)

返回1+1+1+3+5+9+17...+(n-1) + (n-2) + (n-3)

任何帮助都将不胜感激。在

提前谢谢

Answer 1

是的，而且非常优雅，有了Python的多重赋值功能：

>>> def fib3(n):
...     if n < 3:
...         return 1
...     a = b = c = 1
...     for i in range(3, n):
...         # We "shift" a, b, and c to the next values of the sequence.
...         a, b, c = b, c, (a + b + c)
...     return c
...
>>> fib3(4)
3
>>> fib3(5)
5
>>> fib3(6)
9
>>> fib3(7)
17

迭代方法绝对优于递归方法as @mu writes，递归实现的运行时间约为O（3^n），而该方法的运行时间为O（n）。在

Answer 2

我在聚会上迟到了，但是：我们可以很容易地推导出一个公式来得到任何线性递归的第n个元素，比如斐波纳契序列或其推广，而不必计算所有中间元素。假设你的循环是f[n]=a[1]f[n-1]+a[2]f[n-2]+。。。+[m-无]。假设f[n]=（某个常数）^n（这是一种经常出现在微分方程解中的“幸运猜测”假设。我不知道如何证明它是先验的。然后这个常数必须是多项式x^m-a[1]x^（m-1）-a[2]x^（m-2）-。。。-a[米]。任何解的线性组合也必须是解。通过求解由第一个m值导出的线性系统，可以找到线性组合的系数c[1]，…，c[m]（显然，序列中所有后面值的值都是由第一个m值确定的）。在

对于给定的递归f[n]=f[n-1]+f[n-2]+f[n-3]，我们有a[1]=a[2]=a[3]=1，并且x^3-x^2-x-1的根分别为-0.6063%i-0.4196，0.6063%i-0.4196，1.839。给定前3个值是1，1，1。求解c[1]+c[2]+c[3]=1，c[1]a[1]+c[2]a[2]+c[3]a[3]=1，c[1]a[1]^2+c[2]a[2]^2+c[3]a[3]^2=1，分别得到0.3592%i+0.2822，0.2822-0.3592%i，0.4356。（我把它们写成近似的浮点数。作为有理系数多项式的根，这些都是代数数，但精确表达式很容易变得混乱。）

综上所述，f[n]=c[1]a[1]^n+c[2]a[2]^n+c[3]a[3]^n是一个函数，它给出了递归f[n]=f[n-1]+f[n-2]+f[n-3]，其中f[2]=f[1]=f[0]=1。在

我计算了Maxima中的a和c。如果我有什么兴趣的话。在

Answer 3

计算m最后一个整数的fib_sum：

>>> def fib_sum(n,m):
        if n < m:
            return "n should be greater than m"
        a,b,sumit = 0,1,0
        for x in range(n):
            print b,
            if x >= n-m:
                sumit += b
            a,b = b,a+b
        return sumit

>>> fib_sum(3,4)
'n should be greater than m'
>>> fib_sum(3,2)
1 1 2
3
>>> fib_sum(3,1)
1 1 2
2
>>> fib_sum(2,1)
1 1
1
>>> fib_sum(2,2)
1 1 
2
>>> fib_sum(7,2)
1 1 2 3 5 8 13
21
>>> fib_sum(7,3)
1 1 2 3 5 8 13
26
>>> fib_sum(8,6)
1 1 2 3 5 8 13 21
52
>>> fib_sum(8,8)
1 1 2 3 5 8 13 21
54