唯她
频道主
斐波那契数列算法
斐波那契数列(Fibonacci sequence),又称黄金分割数列 ,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称“兔子数列”,其数值为:1、1、2、3、5、8、13、21、34……在数学上,这一数列以如下递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)。
本文举例了实现斐波那契数列求值常用的三种算法
定义算法
(defun fib (n)
"斐波那契数列"
(cond
((= n 0) 0)
((= n 1) 1)
(t (+ (fib (- n 1))
(fib (- n 2))))
))
首先,我们很容易使用递归算法来设计该算法。但是计算出结果是一个指数阶的算法,当n到100的时候,每多算一个斐波那契数需要至少多算一年。
那我们今天就主要介绍一下优化后的算法。
线性迭代法
两数辗转相加,每次记录前一项,时间复杂度为O(n),空间复杂度降低到了O(1)。代码如下:
(defun fib (n)
"迭代法求fibonacci.线性迭代"
(fib-iter 1 0 n))
(defun fib-iter (a b count)
(if (= 0 count)
b
(fib-iter (+ a b) a (- count 1))))
在这种算法中,我们每次递归都将a+b的值赋给a,把a的值赋给b,通过观察可以发现,从1和0开始将规则反复应用n次,将产生一对数fib(n)和fib(n+1)。
现在将这种规则看成 a = bq + aq + a*p , b = bp + aq ,其中p=0,q=1把这种变换称为 T 变换。
T变换
计算过程中状态变量a 和 b 的变换规则, a = a + b , b = a 。
对数阶迭代算法
Tpq 变换有个特性是 Tpq 的二次方等于Tp‘q’,
p‘ = pp + qq , q’ = 2pq + q*q
即:a = (bp+aq)p+(bq+aq+ap)q+(bq+aq+ap)p = b(2pq+q^2)+a(p^2+2pq+2q^2)
b = (bp+aq)p+(bq+aq+ap)q = b(p^2+q^2)+a(q^2+2pq)
接下来我们来看看对数阶的斐波那契数列算法。先来看下面这种算法:
(defun fib1 (n)
"迭代法求fibonacci.对数阶迭代"
(fib-iter1 1 0 0 1 n))
(defun fib-iter1 (a b p q count)
(cond
((= count 0) b)
((m:evenp count)
(fib-iter1 a
b
(+ (* p p)(* q q))
(+ (* 2 p q)(* q q))
(/ count 2)))
(t (fib-iter1 (+ (* b q)(* a q)(* a p))
(+ (* b p)(* a q))
p
q
(- count 1)))))
这样的算法时间复杂度可以达到对数阶。大幅地提高了算法的效率。
实现斐波那契数列求值常用的三种算法。定义法简单明了但是计算复杂度太大,耗时太长。后面两种算法优化非常明显。体现了尾递归的优势。
在使用递归算法时,尽量转化为尾递归形式。
- 下载图片
- 复制图片
2024-11-13
浏览73
开发相关
登录后评论
点赞
评论
分享