2回答

1收藏

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

信息分享 信息分享 2496 人阅读 | 2 人回复 | 2021-10-13

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]



本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x
分享到:
回复

使用道具 举报

回答|共 2 个

Cc_

发表于 2021-10-15 13:54:09 | 显示全部楼层

学习了
回复

使用道具 举报

鸢公子

发表于 2021-10-22 16:31:50 | 显示全部楼层

666
回复

使用道具 举报