Python斐波那契数列

Fibonacci Sequence

Posted by BlueFat on Saturday, August 13, 2022

斐波那契数列指的是这样一个数列: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