【斐波那契数列】今天聊聊 斐波那契数列，面试容易考，工作也能用，估计看这一篇就够了！！

鸢公子

1、关于【斐波那契】那点事
国庆前，领导让搞搞现在的问题，统计一下，分成几类，用于面试方面，顺道就想到整个面试题，帖子看了一堆，发现结果有些分散，大致思路都一样，随后抽烟时候和前后端的聊了聊，说之前有做面试题，找了找，看了看，怎么写的都有，天马行空，又臭又长，遂想着简单研究一下，发个帖子，略有匆忙，还请见谅。



2、简单上手
先小的溜的整俩，一般分成取下标第几个和遍历


（1）、取下标，获取第n项值
def fb_num(n, a=0, b=1):
    for _ in range(n - 1):  # n <= 1 不走循环
        a, b = b, a + b
    return n > 0 and b or a  # 负索引不报错返回0，第 0 项 0，第 1 项 1 ...
（2）、遍历，获取前n项所有值
def fb_iter(n, a=0, b=1):
    for _ in range(n): # n < 1 不走循环, 包括负索引
        yield b  # 0 开始的就 yield a, 1 开始的就 yield b
        a, b = b, a + b
你要想try下也行，自行修改

简单不，很简单，是不是



3、递归一下嘛
虽然 Python 递归有次数上限，但也有包突破上限，请自行寻找

来个尾递归的吧，正常递归的请自行实现(PY好像没有尾递归，其他语言有，大同小异)
def fb_num_d(n, a=0, b=1):  # 斐波那契数列 取下标 递归
    return n > 0 and fb_num_d(n - 1, b, a + b) or a  # 负索引不报错返回0，第 0 项 0，第 1 项 1 ...
看来还是很简单的嘛



4、lambda 一下行不行
当然行了，只要写成一行，就能用  lambda
fb_num_l = lambda n, a=0, b=1: n > 0 and fb_num_l(n - 1, b, a + b) or a
好像越来越神奇了，怎么可以这样写，怎么可以这么简单，小小的脑袋大大的问号



5、发现问题
（1）、非递归模式 iter 好像从 0 开始或从 【斐波那契数列】相邻的两个开始，但相邻的两个怎么得到呢，得用 fb_num 获取，这样一来，当 n 很大的时候，他还是从 0 开始计算的，例如：[获取 1w 下标的数] or [遍历 1w 到 2w 的数]，前 1w 个数最少算一次，有没有简单有效的方法直接拿到？

（2）、递归模式呢，也就这样实现的还好，如果是 fb(n) = fb(n-1) + fb(n-2) 这样就非常不推荐，因为要计算 fb(n)，就得先计算 fb(n-1) 和 fb(n-2), 计算 fb(n-1) 要 fb(n-2) 和 fb(n-3)，这样一来，fb(n-2) 就计算两次 ....
# fb() = fb(n-1) + fb(n-2)
# fb(n-1) = fb(n-2) + fb(n-3) 代入上面 --> fb() = fb(n-2) + fb(n-3) + fb(n-2)
# fb(n-2) = fb(n-3) + fb(n-4) 代入上面 --> fb() = fb(n-3) + fb(n-4) + fb(n-3) + fb(n-3) + fb(n-4)
# ..... 无穷无尽的重复计算

# 结论：
# 计算的次数是 0 调用 n 次， 1 调用 n-1 次， fb(2) 计算 n-2 次，fb(3) 计算 n-3 次 ..


6、解决问题



[ttreply]

那就查资料呗，从百度百科发现 fb(n) 可以用公式算出来，

从百度知道中得到计算公式：







公式： fb(n) = (((1+√5)/2)^n-((1-√5)/2)^n)/√5

这不就妥了嘛，这不就妥了嘛，

[/ttreply]
7、代码实现
[ttreply]
class Fibonacci:

    __G5 = 5 ** 0.5
    __JA = (1 + __G5) / 2
    __JS = (1 - __G5) / 2
    
    def __init__(self, start=0):
        self.start = start  # 开始下标
        self.current = start  # 当前下标
        self.num = self.__get(self.current)  # 当前值
        self.next = self.__get(self.current + 1)  # 下一次值
        
    def __get(self, index):  # 获取任意下标值
        return int((self.__JA ** index - self.__JS ** index) / self.__G5)
        
    def __next__(self):  # 获取当前的下一个值
        self.current += 1
        self.num, self.next = self.next, self.num + self.next
        return self.num
        
    def next_step(self, step):  # 获取当前的下几个后的值
        for _ in range(step):
            self.current += 1
            self.num, self.next = self.next, self.num + self.next
        return self.num
        
    def to_index(self, index):  # 跳转下标
        self.__init__(index)
        return self
        
    @property
    def iter(self):  # 迭代器
        while 1:
            yield self.__next__()
            
    def range(self, *args):  # 遍历
        if args and args.__len__() > 3:
            raise ValueError('参数多了')
        start, stop, step, *_ = [*args, None, None]
        if start != self.start:
            self.__init__(start)
        if start and not (stop and step):
            yield from (self.__next__() for _ in range(start))
        elif start and stop:
            yield from (self.__next__() for _ in range(start, stop))
        elif start and stop and step:
            yield from (self.next_step(stop) for _ in range(range(start, stop, step).__len__()))
这样用起来也方便
# f = Fibonacci(n)  # 指定起点索引
    # f.next  # 获取下一个数
    # f.next_step(x)  # 获取 x 后的数
    # f.to_index(x)  # 跳转下标 x 处开始
    # f.iter  # 是迭代器，用于遍历，但他是无限的，next(f.iter) 为好
    # f.range(start, stop, step)/f.range(start, stop)/f.range(stop)  # 用法和 range 用法一样
[/ttreply]

Cc_

学习了

鸢公子

666