|
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
|