四种方法实现Fibonacci数列(python3)

时间:2022-06-11 20:45:14
  斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:
四种方法实现Fibonacci数列(python3)
1、迭代实现Fibonacci数列
 1 # -*- coding:utf-8 -*-
2 def fibo(n):
3 n1, n2 = 1, 1
4 if n == 1 or n == 2:
5 return 1
6 while(n-2 > 0):
7 n3 = n2 + n1
8 n1 = n2
9 n2 = n3
10 n -= 1
11 return n3
12
13 m = int(input('input a integer n:'))
14 for i in range(1, m + 1):
15 print(fibo(i))

2、递归实现Fibonacci数列

   递归:在函数内部可以调用其它可见函数也可以调用函数自身,递归就是函数调用自身的行为。在python3中对于递归默认的深度是100层,可以通过下面的方法设置递归的深度:

>>> import sys 

>>> sys.setrecursionlimit(1000000)

   递归的缺陷:递归每次调用自身都要进行压栈、弹栈保存和恢复寄存器的栈操作,非常浪费时间和空间。

    递归实现Fibonacci数列:

 1 # -*- coding:utf-8 -*-
2 def recurFibo(n):
3 #递归函数输出斐波拉契数列
4 if n == 1 or n ==2:
5 return 1
6 else:
7 return (recurFibo(n-1) + recurFibo(n-2))
8
9 m = int(input('input a integer n:'))
10 for i in range(1, m + 1):
11 print(recurFibo(i))

 3迭代器实现Fibonacci数列

  迭代的过程类似循环,关于迭代器,paython提供了两个内置函数:

  • iter()  对于容器对象调用iter就得到它的迭代器。

  ——__iter__()  iter的魔法方法,返回迭代器本身,相当于return self。

  • next()    调用next就会返回下一个值。

  ——__next__()  next的魔法方法,它决定了迭代器的规则。

  迭代器实现Fibonacci数列:

 1 # -*- coding:utf-8 -*-
2 class Fibs:
3 def __init__(self, n=10):
4 self.a = 0
5 self.b = 1
6 self.n = n
7 def __iter__(self):
8 return self
9 def __next__(self):
10 self.a, self.b = self.b, self.a + self.b
11 if self.a > self.n:
12 raise StopIteration
13 return self.a
14
15 fibs = Fibs(100)
16 for each in fibs:
17 print(each)

4、生成器实现Fibonacci数列

  迭代器需要定义一个类和实现相关的方法才可以定义一个灵活的迭代器器,而生成器则需要在普通的函数中加上yield语句。生成器就是一个特殊的函数,调用可以中断、可以暂停。

  生成器实现Fibonacci数列:

 1 # -*- coding:utf-8 -*-
2 def libs():
3 a = 0
4 b = 1
5 while True:
6 a, b = b, a + b
7 yield a
8
9 for each in libs():
10 if each > 100:
11 break
12 print(each, end=' ')