斐波那契数列(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(1.618^n),而且最深度1000)

1
2
3
4
5
6
7
8
9
10
def fib_func(n):
# 定义出口
if n <= 1:
return 1
return func(n-1)+func(n-2) #第一位数和第二位数相加的结果

for i in range(10):
print(fib_func(i),end=" ")

#1 1 2 3 5 8 13 21 34 55

生成器斐波那契数列

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

1
2
3
4
5
6
7
8
9
10
11
def fib_func(max):
n,a,b = 0,0,1
while n < max:
yield b
a,b = b,a+b
n += 1

fib_list = fib_func(10)
for i in fib_list: #使用for循环遍历
print(i,end=" ")
#1 1 2 3 5 8 13 21 34 55

评论





载入天数...载入时分秒...

Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

Use WZH as theme, total visits times