|
斐波那契数列（Fibonacci sequence），欧博abg又称黄金分割数列、因数学家列昂纳多·斐波那契（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*）
斐波那契数列，难点在于算法，还有如果变成生成器，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_for(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b return a def fib_loop_while(n): a, b = 1, 1 while n > 0: a, b = b, a + b n -= 1 return a for i in range(20): print(fib_loop_for(i), end=' ')递推法，就是递增法，时间复杂度是 O(n)，呈线性增长，如果数据量巨大，速度会越拖越慢 第三种生成器 def fib_yield_while(max): a, b = 0, 1 while max > 0: a, b = b, a+b max -= 1 yield a def fib_yield_for(n): a, b = 0, 1 for _ in range(n): a, b = b, a + b yield a for i in fib_yield_for(10): print(i, end=' ')带有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 循环的本质 for x in [1, 2, 3, 4, 5]: pass相当于： # 首先获取可迭代对象 it = iter([1, 2, 3, 4, 5]) while True: try: next(it) except StopIteration: # 遇到StopIteration就跳出循环, 且自动频闭StopIteration异常 break 第五种-矩阵
因为幂运算可以使用二分加速，所以矩阵法的时间复杂度为 O(log n) 装饰器就是 fib(n) = trace(fib)(n), 即将函数当作参数，与此同时，类实现了__call__方法之后也是一个callable 递归版斐波那契函数 要求如下： 1.输出文档说明 2.输出函数每次执行的函数名，所用参数，返回值，执行时间 3.输出总耗时 class TiemTrace: def __init__(self, f): self.f = f print(f.__doc__) def __now(self): return time.time() def __enter__(self): self.start = self.__now() return self def __exit__(self, exc_type, exc_val, tb): self.end = self.__now() print('cost {}'.format(self.end - self.start)) def __call__(self, n): start = self.__now() val = self.f(n) end = self.__now() print('{}, {}, {}, cost: {} seconds'.format(self.f.__name__, n , val, (end - start))) return val def fib(n): """ :params n 个数 :return 当前斐波那契数值 """ if n <= 1: return n return fib2(n-1) + fib2(n-2) with TimeTrace(fib) as fib: print(fib(5))使用装饰器的话要统计递归我暂时只想到用global变量统计递归总耗时，有知悉的大佬请告知，感谢！！ 两种方法的执行效率对比，
下图为装饰器方法
上下文方式比装饰器方式更快一点。 (责任编辑：) |
