一句话先回答问题：因为斐波那契数列在数学和生活以及自然界中都非常有用。
下面我就尽我所能，讲述一下斐波那契数列。
一、起源和定义
斐波那契数列最早被提出是印度数学家Gopala，他在研究箱子包装物件长度恰好为1和2时的方法数时首先描述了这个数列。也就是这个问题：
有n个台阶，你每次只能跨一阶或两阶，上楼有几种方法？
而最早研究这个数列的当然就是斐波那契（Leonardo Fibonacci）了，他当时是为了描述如下情况的兔子生长数目：
•第一个月初有一对刚诞生的兔子
•第二个月之后（第三个月初）它们可以生育
•每月每对可生育的兔子会诞生下一对新兔子
•兔子永不死去
这个数列出自他赫赫有名的大作《计算之书》（没有维基词条，坑），后来就被广泛的应用于各种场合了。这个数列是这么定义的：
The On-Line Encyclopedia of Integer Sequences® (OEIS®)序号为A000045 - OEIS
（注意，并非满足第三条的都是斐波那契数列，卢卡斯数列（A000032 - OEIS）也满足这一特点，但初始项定义不同）
二、求解方法
讲完了定义，再来说一说如何求对应的项。斐波那契数列是编程书中讲递归必提的，因为它是按照递归定义的。所以我们就从递归开始讲起。
1.递归求解
int Fib(int n)
{
return n < 2 ? 1 : (Fib(n-1) + Fib(n-2));
}
这是编程最方便的解法，当然，也是效率最低的解法，原因是会出现大量的重复计算。为了避免这种情况，可以采用递推的方式。
2.递推求解
int Fib[1000];
Fib[0] = 0;Fib[1] = 1;
for(int i = 2;i < 1000;i++) Fib[i] = Fib[i-1] + Fib[i-2];
递推的方法可以在O(n)的时间内求出Fib(n)的值。但是这实际还是不够好，因为当n很大时这个算法还是无能为力的。接下来就要来讲一个有意思的东西：矩阵。
3.矩阵递推关系
学过代数的人可以看出，下面这个式子是成立的：
不停地利用这个式子迭代右边的列向量，会得到下面的式子：
这样，问题就转化为如何计算这个矩阵的n次方了，可以采用快速幂的方法。快速幂_百度百科是利用结合律快速计算幂次的方法。比如我要计算，我们知道
，而可以通过来计算，而可以通过计算，以此类推。通过这种方法，可以在O（lbn）的时间里计算出一个数的n次幂。快速幂的代码如下：
int Qpow(int a,int n)
{
int ans = 1;
while(n)
{
if(n&1) ans *= a;
a *= a;
n >>= 1;
}
return ans;
}
将上述代码中的整型变量a变成矩阵，数的乘法变成矩阵乘法，就是矩阵快速幂了。比如用矩阵快速幂计算斐波那契数列：
#include
#include
using namespace std;
const int MOD = 10000;
struct matrix//定义矩阵结构体
{
int m[2][2];
}ans, base;
matrix multi(matrix a, matrix b)//定义矩阵乘法
{
matrix tmp;
for(int i = 0; i < 2; ++i)
{
for(int j = 0; j < 2; ++j)
{
tmp.m[i][j] = 0;
for(int k = 0; k < 2; ++k)
tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
}
}
return tmp;
}
int fast_mod(int n) // 求矩阵 base 的 n 次幂
{
base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
base.m[1][1] = 0;
ans.m[0][0] = ans.m[1][1] = 1; // ans 初始化为单位矩阵
ans.m[0][1] = ans.m[1][0] = 0;
while(n)
{
if(n & 1) //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t ans = multi(ans, base);
base = multi(base, base);
n >>= 1;
}
return ans.m[0][1];
}
int main()
int n;
while(scanf("%d", &n) && n != -1)
{
printf("%d\n", fast_mod(n));
}
return 0;
}
4.通项公式
无论如何，对于一个数列，我们都是希望可以建立与n的关系，也就是通项公式，而用不同方法去求解通项公式也是很有意思的。
（1）构造等比数列
设,
化简得,
比较系数得，
解得，
由于
故有，设.则有
,设,
解得，即{}是等比数列。这样就有
到了现在，把上述解出的结果全部带入上式，稍作变形，我们就可以写出斐波那契数列的通项公式了
