如何用Python输出一个Fibonacci数列

斐波那契数列

斐波那契数列 (Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

斐波那契数列,难点在于算法,还有如果变成生成器,generator,就要用for循环去遍历可迭代的generator 。

实现

第一种 递归法

def fib_recur(n):
  assert n >= 0, "n > 0"
  if n <= 1:
    return n
  return fib_recur(n-1) + fib_recur(n-2)

for i in range(1, 20):
    print(fib_recur(i), end=' ')

写法最简洁,但是效率最低,会出现大量的重复计算,时间复杂度O(1.618^n),而且最深度1000

第二种 递推法

def fib_loop(n):
  a, b = 0, 1
  for i in range(n + 1):
    a, b = b, a + b
  return a


for i in range(20):
  print(fib_loop(i), end=' ')

递推法,就是递增法,时间复杂度是 O(n),呈线性增长,如果数据量巨大,速度会越拖越慢

第三种 生成器

def fib_loop_while(max):
    a, b = 0, 1
    while max > 0:
        a, b = b, a + b
        max -= 1
        yield a


for i in fib_loop_while(10):
    print(i)

带有yield的函数都被看成生成器,生成器是可迭代对象,且具备__iter__ 和 __next__方法, 可以遍历获取元素
python要求迭代器本身也是可迭代的,所以我们还要为迭代器实现__iter__方法,而__iter__方法要返回一个迭代器,迭代器自身正是一个迭代器,所以迭代器的__iter__方法返回自身即可

第四种 类实现内部魔法方法

class Fibonacci(object):
    """斐波那契数列迭代器"""

    def __init__(self, n):
        """
        :param n:int 指 生成数列的个数
        """
        self.n = n
        # 保存当前生成到的数据列的第几个数据,生成器中性质,记录位置,下一个位置的数据
        self.current = 0
        # 两个初始值
        self.a = 0
        self.b = 1

    def __next__(self):
        """当使用next()函数调用时,就会获取下一个数"""
        if self.current < self.n:
            self.a, self.b = self.b, self.a + self.b
            self.current += 1
            return self.a
        else:
            raise StopIteration

    def __iter__(self):
        """迭代器的__iter__ 返回自身即可"""
        return self


if __name__ == '__main__':
    fib = Fibonacci(15)
    for num in fib:
        print(num)
for循环的本质是通过不断调用next()函数实现的
    for x in [1, 2, 3, 4, 5]:
        pass

相当于:

    # 首先获取可迭代对象
    it = iter([1, 2, 3, 4, 5])
    # while next
    while True:
        try:
            next(it)
        except StopIteration:
            # 遇到StopIteration就退出循环
            break

应用

斐波那契数列中的斐波那契数会经常出现在我们的眼前——比如松果、凤梨、树叶的排列、某些花朵的花瓣数(典型的有向日葵花瓣),蜂巢,蜻蜓翅膀,超越数e(可以推出更多),黄金矩形、黄金分割、等角螺线,十二平均律等。

黄金分割
随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…
杨辉三角
将杨辉三角左对齐,成如图所示排列,将同一斜行的数加起来,即得一数列1、1、2、3、5、8、……
矩形面积
斐波那契数列与矩形面积的生成相关,由此可以导出一个斐波那契数列的一个性质。
斐波那契数列前几项的平方和可以看做不同大小的正方形,由于斐波那契的递推公式,它们可以拼成一个大的矩形。这样所有小正方形的面积之和等于大矩形的面积。则可以得到如下的恒等式:

质数数量
斐波那契数列的整除性与质数生成性

赞(4) 打赏
特别声明:除特殊标注,本站文章均为原创,遵循CC BY-NC 3.0,转载请注明出处。三伏磨 » 如何用Python输出一个Fibonacci数列

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏