最后三个数字的斐波那契式序列 [英] Fibbonaci-like sequence of last 3 numbers

问题描述

是否有一种非递归的方式，可以通过添加最后3个数字来构成类似于斐波那契"的序列?

Is there a non-recursive way I can make a "Fibonacci-like"sequence of the by adding the last 3 numbers?

这是我尝试执行的递归方法.

Here's the recursive way I tried to do it.

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)

任何帮助将不胜感激.

预先感谢

推荐答案

是的，非常优雅，具有Python的多重分配功能:

Yes, and quite elegantly, with Python's multiple assignment ability:

>>> 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

并且绝对肯定会优先使用递归方法-如@mu所写，递归实现的运行时间约为O(3 ^ n)，而此方法为O(n).

And the iterative method would definitely be preferred to the recursive method - as @mu writes, the running time of the recursive implementation is approximately O(3^n), while this method is O(n).

这篇关于最后三个数字的斐波那契式序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！