长宁区网站建设网,深圳工信部网站备案信息查询,IT科技资讯新闻类织梦网站模板,成都美誉网站设计一分钟学一个算法题目。
今天我们要学习的是用递归算法求解斐波那契数列。
首先我们要知道什么是斐波那契数列。
斐波那契数列#xff0c;又称黄金分割数列#xff0c;是一个经典的数学数列#xff0c;其特点是第一项#xff0c;第二项为1#xff0c;后面每个数字都是前…
一分钟学一个算法题目。
今天我们要学习的是用递归算法求解斐波那契数列。
首先我们要知道什么是斐波那契数列。
斐波那契数列又称黄金分割数列是一个经典的数学数列其特点是第一项第二项为1后面每个数字都是前两个数字之和。推导过程如视频所示非常非常简单。
知道了斐波那契数列的定义后我们将其代入到递归问题的分析当中。
首先确定边界条件就是第一项和第二项为1接着确定递归关系后一项等于前两项的和。确定了上面这些关系我们就可以写出下面的代码了。
def fib(x):# 边界条件if x1 or x2: return 1# 递归关系return fib(x-2)fib(x-1)print(fib(1))
print(fib(2))
print(fib(3))
print(fib(4))
print(fib(5))
print(fib(6))没错去掉注释和空行后只有三行代码简洁精炼是递归问题的共性你学习过肯定深有体会。下面我们稍微解读下代码这是一个求解斐波那契数列第n项数字的函数函数名为fib接受一个参数n。 如果n等于1或者2那么就返回1否则就返回fib(n-2)与fib(n-1)的和怎么样脑子转过来弯了吗没错就是这么简单。我们来尝试运行使用函数检验一下正确性发现都输出了正确结果。
但是这个函数还有很大的优化空间在哪里呢没错递归算法让我们使用简洁的代码解决复杂的问题。但他的时间复杂度很高一不小心没做好边界与转换关系判断就会导致无限循环或者栈溢出。
我们以此题为例假如我们要求解斐波那契数列的第一百项数字那麽我们会得到这张调用关系图同一项会被重复计算非常非常多次。所以你运行此函数可能会导致很长时间都计算不出结果。
那么我们该如何优化呢 我们该如何避免重复计算某一项的值呢
我们可以在计算出每一项的时候把计算结果存到一个字典里。这样我们在每次计算前先去字典中寻找这一项如果有值那么直接拿出来使用如果没有再计算它。
这样的话我们就可以保证每一项仅被计算一次。运行时间也将会大大缩短。按照以上思路我们对代码进行如下变化。
def fib(n):# 边界条件if n1 or n2: return 1if hash.get(n,0):return hash.get(n)# 递归关系ansfib(n-2)fib(n-1)hash[ans]ansreturn anshash{}在代码中我们增加了以下变化 每次计算某一项时先去集合中查询如果已经计算过那么直接返回值如果没有则计算并且在返回值之前先在集合中记录一下。
这样代码的算法复杂度已经优化了很多了没有优化版本求解第70项都非常费力现在优化后已经可以轻松算出第100项了。但要想算出第一百项还是需要很久时间。
因为其中还存在大量的分支判断。
而且此解法还远远不是最优解法关注up主我们下集就来讲讲更快的方法。
