最新消息:20190717 VPS服务器:Vultr新加坡,WordPress主题:大前端D8,统一介绍入口:关于

【推荐】【转】Fabonacci 数的计算

工作和技术 crifan 636浏览 0评论

【推荐】【转】Fabonacci 数的计算

这是我为Ruby中文电子期刊写的第一篇文章,顺便发在自己blog上。我准备抽空写出一个系列,在展示Ruby的语言特性的同时讨论一些程序设计和算法应用的技巧。错误在所难免,欢迎留言改正。

第一篇从一个所有学过程序设计的人都熟悉的问题说起,那就是 Fabonacci 数:

LaTeX element

大学的第一门程序设计课时候通常会以这个为例子介绍递归。大家都知道用递归求 Fabonacci 数很慢,求第n个数的时间复杂度是LaTeX element。大家也都知道改为迭代可以把时间复杂度降低到O(n)。用 Ruby 写出来就是:

f0=0
f1=1
for i in (2..100000)
    f0, f1 = f1, (f0+f1)
end
puts f1

这个程序计算第10万个 Fabonacci 数,不包括输出需要14.48秒(这个数字是用ruby -r profile得到的)。能不能更快些呢?或许很多人会想到去找一个闭合公式(closed form),其实仅依靠定义就可以找到更快的解法。下面介绍的算法时间复杂度为O(log(n))。注意到下面的等式成立:

LaTeX element

所以要计算LaTeX element只要计算:

LaTeX element

实现这个算法需要 Ruby 的 Matrix 模块:

require "matrix"

a = Matrix[[1,1],[1,0]]
b = Matrix[[1,0]]
c = b * (a ** (100000-1))
puts c[0,0]

这个新的程序只需要0.77秒。效率显著提高的原因在于计算LaTeX element只需要O(log(n))步。作为验证,我们不使用 Ruby 提供的幂操作符,自己求矩阵的n次方:

require "matrix"

a = Matrix[[1,1],[1,0]]
b = Matrix[[1,0]]
t = Matrix.I(2)    # 单位矩阵
i = 100000-1
c = a
while i != 1
    if (i % 2) == 0
        i = i / 2
        c = c * c
    else
        i = i - 1
        t = t * c
    end
end
d = b * t * c
puts d[0,0]

这个程序只需要0.65秒,说明 Ruby 内部对幂的实现基本是这样的。用自己的实现在效率上有微小的提高,原因可能是 Ruby 对幂操作符的实现有一些额外的操作。但对比最后两个程序,显然用语言提供的结构要简练很多,益处远超过效率的提高。

就语言的设计来说,上面的例子也体现了使用 Ruby 或 Python 这类动态语言描述算法的自然和优雅。不相信的话可以试试用C++或者Java实现一下上面的算法。;-)

转载请注明:在路上 » 【推荐】【转】Fabonacci 数的计算

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (1)

  1. do you have any application using this method? (If you do have, can you sent me one? I will appreciate it)Thank you.
    匿名网友12年前 (2007-11-22)回复
59 queries in 0.126 seconds, using 18.87MB memory