浅议Fibonacci（斐波纳契）数列求解
Fibonacci数列：
描述了动物繁殖数量、植物花序变化等自然规律。作为一个经典的数学问题，Fibonacci数列常作为例子出现在程序设计、数据结构与算法等多个相关学科中。
下面简单地分析一下常见的Fibonacci数列求解算法。
1、递归法。大多数教材在讲解递归算法时总喜欢以Fibonacci数列为例，这是因为我们可以直观地从定义公式的第三行看出Fibonacci数列的递归性。其C++实现如下：
unsigned long Fib(int n)
{
if (n <= 1) {
return n;
} else {
return Fib(n - 1) + Fib(n - 2);
}
}
|
递归算法与定义公式十分吻合，容易理解，但计算过程存在大量重复的运算，时间复杂度达到了O(2^n)，使用的内存空间也随着函数调用栈的增长而增长。这显然不适于实用的程序。
2、表驱动的递归法。这里不提纯粹的表驱动法，因为对于项数未知的Fibonacci数列开启大片的空间来换取时间未免不值得且不负责。我们只是为了消除递归法中大量重复的运算，可以将已经计算过的中间值存入一个表，已备后续使用：
#define MAX_LOG 20
static unsigned long Logs[MAX_LOG] = {0};
unsigned long Fib(int n)
{
if (n <= 1) {
return n;
} else if (n < MAX_LOG && Logs[n] != 0) {
return Logs[n];
} else {
Logs[n] = Fib(n - 1) + Fib(n - 2);
return Logs[n];
}
}
|
当n小于保存的表长时，由于每个中间值只计算一次，时间复杂度降为O(n)。但随着n的增大，要想维持O(n)的时间复杂度，就必须扩大保存的表长，这就造成了存储空间的浪费。
3、迭代法。求Fibonacci数列第n项时虽然要用到前面两项的值，但它们仅作为临时计算的中间值，不作为结果输出，因此无保留的必要，完全可以转化成迭代法求解：
unsigned long Fib(int n)
{
int i;
unsigned long a = 0, b = 1, c;
if (n <= 1) {
return n;
} else {
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
|
迭代法的时间复杂度为O(n)，使用的内存空间也不会动态上涨。个人认为Fibonacci数列更适宜作为迭代法而非递归法的典例出现在教材上。
下面给出两种数学性较强的算法。考虑到表达的简洁性，用Matlab实现：
4、转移矩阵法。此方法通常见于线性代数中的Markov过程示例。Fibonacci数列第n项与第n-1项可以通过转移矩阵的n-1次迭代求出：
代码如下：
function y = Fib(n)
first = [1; 0];
trans = [1 1; 1 0];
last = trans ^ (n - 1) * first;
y = last(1, 1);
end
|
此算法的时间复杂度相当于计算矩阵乘方的时间复杂度。在计算2阶矩阵n次方时，如果直接按矩阵乘法定义式展开，不加特别优化，其时间复杂度为O(n)。
5、通项公式法。Fibonacci数列的通项公式如下（证明略）：
利用通项公式可以得到Fibonacci数列的任何项：
function y = Fib(n)
sr5 = sqrt(5);
y = uint32((((1 + sr5) / 2) ^ n - ((1 - sr5) / 2) ^ n) / sr5);
end
|
该方法的时间复杂度貌似为O(1)，但我们还应该考虑乘方运算的时间消耗。不加特别优化时，用乘法实现n次乘方的时间复杂度为O(n)。考虑到浮点数计算效率和精度问题，此方法在计算机实现时不如转移矩阵法。
下面再给出两种对计算机实现有特别意义，但同时有一定局限性的实现方法（只是实现方法，不能称为新的算法）。其中使用了一些C++编程技巧，对使用其它语言实现也有一定的参考价值：
6、模板元编程法。通常我们在C++中使用模板，仅限于类模板与函数模板。事实上C++支持模板元编程，理论上可以在编译时执行任何计算（甚至包含选择、循环、递归等结构）。代码如下：
#define Fib(N) FibT<N>::Val
template<int n> struct FibT
{
enum
{
Val = FibT<n - 1>::Val + FibT<n - 2>::Val
};
};
template<> struct FibT<0>
{
enum
{
Val = 0
};
};
template<> struct FibT<1>
{
enum
{
Val = 1
};
};
|
我们用一个结构体作为模板的载体，用一个枚举值保存运算结果。其中第一个模板为基本递归过程（使用递归算法是为了说明的简便，完全可以用其它算法替代，以加速编译过程），后两个模板为n=0、1时的模板特化。通过#define语句将模板调用简写成类似函数调用的方式。程序在编译时运算所需的 Fibonacci数列项，将结果作为常量嵌入编译好的程序。运行时直接使用结果，时间复杂度真正地变成了O(1)。但这一方法最大的局限就是只能对常量嵌入，程序中出现诸如计算Fib(i++)的情况则无能为力。尽管如此，这比在代码中手工计算并写入所需的值要直观准确，比通过纯粹的表驱动法“空间换时间”要方便快捷。
7、函数对象法。此方法主要用于C++ STL编程的通用算法方面，其执行行为也有别于以上其它方法：
class Fib
{
public:
Fib() : a(0), b(1), n(0)
{
}
unsigned long operator()()
{
if (n <= 1) {
n++;
return n - 1;
} else {
int c;
c = a + b;
a = b;
b = c;
return c;
}
}
private:
int a, b, n;
};
|
这个函数类对象的行为可以理解为一个“Fibonacci数列发生器”，其测试性调用如下，程序将依次打印
void test(int i)
{
Fib fib;
do {
cout << fib() << endl;
} while (i--);
}
|
函数对象具有与函数指针类似的行为，同时又能保存自身的一些属性，因此常用于STL通用算法编程。但针对单个的Fibonacci数列项求值，灵活性不如一般的方法。
希望读者能够从上面的算法分析中举一反三，有所领悟。
参考资料：
1、Bruce Eckel，Thinking In C++ Volume 2: Practical Programming，机械工业出版社，2006
2、William J. Collins，Data Structures and the Standard Template Library，机械工业出版社，2003
3、Knott's Surrey University，The Home page for Fibonacci Numbers and the Golden Section，http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/
