斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89…
这个数列从第3项开始，每一项都等于前两项之和。
公式：f(n)=f(n-1)+f(n-2)
fib(0)=0
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(8)=21
for
def fib(n):
if n<2:
return n
a,b=0,1
for i in range(1,n):
# for i in range(n-2):
a,b=b,a+b
return b
公式递归
def fib(n):
if n < 2:
return n
return fib(n-1)+fib(n-2)
fib(6)
def fib_v2(n):
return 1 if n<3 else fib(n-1)+fib(n-2)
fib_v2(6)
公式递归改进
def fib_v3(n,a=1,b=1):
if n<3:
return b
a,b=b,a+b
return fib_v3(n-1,a,b)
def fib_v3(n,a=1,b=1):
return b if n<3 else fib_v3(n-1,b,a+b)
fib_v3(5)
yield
def fib():
a,b=0,1
yield b
while True:
a,b=b,a+b
yield b
f=fib()
for i in range(6):
print(i+1,next(f))
1 1
2 1
3 2
4 3
5 5
6 8