斐波那契数列（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*）
第一种：递推方法
递推法，就是递增法，时间复杂度是 O(n)，呈线性增长，如果数据量巨大，速度会越拖越慢
- for循环
def fib(n): if n < 0: raise IndexError('Index out of range') a, b = 0, 1 for _ in range(n): # 这里for遍历的时候元素不重要也不需要，所以写的_ a, b = b, a + b return a
测试是否实现基本功能
for i in range(9): print(fib(i),end='\t') C:\Users\zhuzhupoo\AppData\Local\Programs\Python\Python39\python.exe "D:/PyCharm 2021.3.3/py/feibolaqie.py" 0 1 1 2 3 5 8 13 21 Process finished with exit code 0
print(fib(-1)) C:\Users\zhuzhupoo\AppData\Local\Programs\Python\Python39\python.exe "D:/PyCharm 2021.3.3/py/feibolaqie.py" Traceback (most recent call last): File "D:\PyCharm 2021.3.3\py\feibolaqie.py", line 29, in <module> print(fib(-1)) File "D:\PyCharm 2021.3.3\py\feibolaqie.py", line 12, in fib raise IndexError('Index out of range') IndexError: Index out of range Process finished with exit code 1
- while循环
def fib(n): if n < 0: raise IndexError('Index out of range') a, b = 0, 1 while n > 0: a, b = b, a + b n -= 1 return a
功能测试与for的测试一致
第二种：递归方式
def fib(n): if n < 0: raise IndexError('Index out of range') elif n == 0: return 0 elif n < 3: return 1 return fib(n-1) + fib(n-2)
这种方法最简洁，甚至可以转化为单行代码，但是效率最低，会出现大量的重复计算
def fib(n): return 1 if n < 3 else fib(n-1) + fib(n-2)
由于有大量重复计算，我们可以稍微优化一下，设置一下缓存
from functools import lru_cache @lru_cache def fib(n): return 1 if n < 3 else fib(n-1) + fib(n-2)
第三种：用一个类写出比较全面的斐波拉契
class Fib: """一个方便调用的斐波拉契数列""" def __init__(self): self.items = [0, 1, 1] # 定义斐波拉契数列前3项(0,1,2) def __str__(self): # 提供可视化输出 return str(self.items) # def __repr__(self): # return self.__str__() __repr__ = __str__ # 提供不同情况下的可视化输出,简化上面的代码 def __len__(self): # 提供长度方法 return len(self.items) # 取列表的长度 def __iter__(self): # return iter(self.items) # 转化为一个生成器,与下面一行代码同功能 yield from self.items def __getitem__(self, index): # 提供索引方法 if index < 0: raise IndexError('Index out of range') # 索引为负数抛出异常 for i in range(len(self), index+1): # 计算列表中不包含的项 self.items.append(self.items[i-1] + self.items[i-2]) return self.items[index] # def __call__(self, index): # return self.__getitem__(index) # 提供实例调用方法，与下面一行代码功能一致，实际上都是将call丢给getitem处理 # return self[index] __call__ = __getitem__ # 简化上面的代码
测试是否实现基本功能
f = Fib() # 实例化 print(f) # 观察可视化是否实现 print(f[0], f[1], f[3],end='\t') # 观察能否使用实例索引 print(f(0), f(1), f(5),end='\t') # 观察实例能否调用 for i in range(9): print(f(i),end='\t') for x in f: # 打印列表中现有的项 print(x,end='\t') print(f) C:\Users\zhuzhupoo\AppData\Local\Programs\Python\Python39\python.exe "D:/PyCharm 2021.3.3/py/fib0130.py" [0, 1, 1] 0 1 2 0 1 5 0 1 1 2 3 5 8 13 21 0 1 1 2 3 5 8 13 21 [0, 1, 1, 2, 3, 5, 8, 13, 21] Process finished with exit code 0
print(f[-1]) C:\Users\zhuzhupoo\AppData\Local\Programs\Python\Python39\python.exe "D:/PyCharm 2021.3.3/py/fib0130.py" Traceback (most recent call last): File "D:\PyCharm 2021.3.3\py\fib0130.py", line 36, in <module> print(f[-1]) File "D:\PyCharm 2021.3.3\py\fib0130.py", line 21, in __getitem__ raise IndexError('Index out of range') # 索引为负数抛出异常 IndexError: Index out of range Process finished with exit code 1
