这是我为Ruby中文电子期刊写的第一篇文章，顺便发在自己blog上。我准备抽空写出一个系列，在展示Ruby的语言特性的同时讨论一些程序设计和算法应用的技巧。错误在所难免，欢迎留言改正。
第一篇从一个所有学过程序设计的人都熟悉的问题说起，那就是 Fabonacci 数：
大学的第一门程序设计课时候通常会以这个为例子介绍递归。大家都知道用递归求 Fabonacci 数很慢，求第n个数的时间复杂度是
。大家也都知道改为迭代可以把时间复杂度降低到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))。注意到下面的等式成立：
所以要计算
只要计算：
实现这个算法需要 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秒。效率显著提高的原因在于计算
只需要O(log(n))步。作为验证，我们不使用 Ruby 提供的幂操作符，自己求矩阵的n次方：
只需要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 数的计算