2022年 11月 3日

斐波那契数列之python（5种方法）

斐波那契数列（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>=2，n∈N*）

 

1、递归方法

  1. def fib_recur(n):
  2.     if n<=1:
  3.         return n
  4.     else:
  5.         return fib_recur(n-1)+fib_recur(n-2)
  6.  
  7. def ex(c):
  8.     return int(c)
  9.  
  10. X=input().strip().split()
  11. N=list(map(lambda a:int(a), X))[0]
  12.  
  13. for i in range(1, N):
  14.     print(fib_recur(i),end=' ')

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

2、递推方法

  1. def fib_loop(n):
  2.     a,b=0,1
  3.     for i in range(n+1):
  4.         a,b=b,a+b
  5.     return a
  6.     
  7.  
  8. for i in range(20):
  9.     print(fib_loop(i),end=' ')

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

3、生成器

  1. def fib_loop_while(n):
  2.     a,b=0,1
  3.     for i in range(0,n):
  4.         a,b=b,a+b
  5.         yield a
  6.     
  7.  
  8. for i in fib_loop_while(20):
  9.     print(i,end=' ')

怎么去解释这个生成器呢，我记得在以前的博客里面有提及到yield和yield from的区别，实际上更多只知道yield他是返回一个值而不退出这个函数执行。自然也就没有过多关注 fib_loop_while函数的返回对象类型是啥！

在这里系统解释一下：

1、带有yield关键字的函数对象 他是返回一个列表list，list中的每个元素 都是 yield返回的每一个值 （每次执行yield输出值构成的列表）

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

4、类实现内部魔法方法

  1. class Fibonacci(object):
  2.     """斐波那契数列迭代器"""
  3.  
  4.     def __init__(self,n):
  5.         self.n=n
  6.         self.a=0
  7.         self.b=1
  8.         self.cur=0
  9.  
  10.     def __next__(self):
  11.         """当使用next()函数调用时，就会获取下一个数"""
  12.         if self.cur<self.n:
  13.             self.a,self.b=self.b,self.a+self.b
  14.             self.cur=self.cur+1
  15.             return self.a
  16.  
  17.         else:
  18.             raise StopIteration #让他异常停止
  19.  
  20.     def __iter__(self):
  21.         """迭代器的__iter__ 返回自身即可"""
  22.         return self
  23.  
  24.  
  25.  
  26. if __name__=="__main__":
  27.     lst=list(map(int,input().strip().split()))
  28.     M=lst[0]
  29.     
  30.     fib=Fibonacci(M)
  31.     for n in fib:
  32.         print(n,end=' ')
  33.

5、 矩阵

  1. ### 1
  2. import numpy as np
  3.  
  4. def fib_matrix(n):
  5.     res = pow((np.mat([[1, 1], [1, 0]])), n) * np.mat([[1], [0]]) #使用mat方法直接定义矩阵
  6.     return res[0][0]
  7.  
  8. for i in range(10):
  9.     print(int(fib_matrix(i)), end=' ')
  10. print('\n')
  11.  
  12.  
  13. ### 2
  14. # 使用矩阵计算斐波那契数列
  15. def Fibonacci_Matrix_tool(n):
  16.     Matrix = np.matrix([[1, 1], [1, 0]]) #matrix和mat函数等效
  17.     # 返回是matrix类型
  18.     return pow(Matrix, n)  # pow函数速度快于 使用双星好 **
  19.  
  20. def Fibonacci_Matrix(n):
  21.     result_list = []
  22.     for i in range(0, n):
  23.         result_list.append(np.array(Fibonacci_Matrix_tool(i))[0][0])
  24.     return result_list
  25.  
  26. # 调用
  27. result=Fibonacci_Matrix(10)
  28. for r in result:
  29.     print(r,end=' ')

因为幂运算可以使用二分加速，所以矩阵法的时间复杂度为 O(log n)
用科学计算包numpy来实现矩阵法 O(log n)