发烧的斐波那契数列

斐波那契数列

提问

1. 指定一个数值n，返回斐波那契数列中的前n项，如 6 返回[1, 1, 2, 3, 5, 8]
2. 指定一个数值n，返回斐波那契数列中比n小的所有值， 如10 返回 [1, 1, 2, 3, 5, 8]

思考

对于问题一，我们可以只需要实现一个生成斐波那契数列的迭代器

对于问题二，我们可以修改下问题一的迭代器，新增判断条件就可以

实现

def fib(n, max_num=float('inf')):
    a, b = 0, 1
    while True:
        a, b = b, a + b
        if a > max_num or n == 0: break
        yield a
        n -= 1
        
assert list(fib(5)) == [1, 1, 2, 3, 5]
assert list(fib(-1, 10)) == [1, 1, 2, 3, 5, 8]

原理

斐波那契数列的前两项n1,n2是1，从第三项n3开始，n3 = n1 + n2

因此只需要记住前两项的，便能推导出后面的项

而问题二又新增了一个最大值，Python中float('inf')表示的是正无穷

因此新增一个判断即可

被淘汰的版本

from itertools import takewhile, cycle
from typing import Iterator

def fib(n):
    a, b = 0, 1
    if isinstance(n, Iterator):
        l = n
    else:
        assert isinstance(n, int) and n >= 1
        l = range(n)

    for _ in l:
        a, b = b, a + b
        yield a
        
assert list(fib(5)) == [1, 1, 2, 3, 5]
assert list(takewhile(lambda x: x < 100, fib(cycle([1])))) == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

利用了takewhile 和 cycle，后来发现更加繁琐了 。。。。。

cycle是循环一个可迭代对象

[print(i) for i in cycle([1, 2, 3])]
# 1
# 2
# 3
# 1
# 2
# 3
# ...

takewhile是将一个可迭代对象迭代到不满足条件为止

assert list(takewhile(lambda x: x < 3, [1, 2, 3, 4, 5, 6])) == [1, 2]