参考文献：《算法导论》、dalao的blog

我真的觉得本篇良心，大大干货

引言：

题目：

斐波那契数列很喜欢被研究，其前几项为：1 1 2 3 5 8 13 ……

则，求斐波那契数列的第n项是？

解法：

1.朴素求解：

由斐波那契数列的定义，可以由递推求解

f(1)=1,f(2)=1

f(n)=f(n-1)+f(n-2)    (n>=3)

f[1]=f[2]=1;
for(int i=1;i<=n;i++)
    f[n]=f[n-1]+f[n-2];
out(f[n]);

2.矩阵快速幂优化递推式：

学习这个首先要了解一下几个东西：

1.矩阵

2.矩阵的运算

3.快速幂

4.矩阵快速幂优化

矩阵乘法快速幂

1.矩阵

矩阵是二维的一个由n*m构成的”数列“（我想不到其他解释的名词了）

大概长这样：

其数学上的定义方式为：

矩阵名=一对括号里面为矩阵的内容

矩阵的向量简单来说就是矩阵的一行或者是一列 

我们把矩阵的行和列交换记作（以矩阵A举例）

零矩阵为所有元素都是0的矩阵

单位向量是第i个元素是1而其他皆为0 的向量

那么，矩阵有以下特殊的几种

1.1对角矩阵

当i!=j时，有aij=0

大概长这样：（盗用一下G_congratulationdalao单位矩阵的图2333，这里的1可以换成其他任意数，但下面的单位矩阵就不可以了）

1.2单位矩阵

矩阵里的元素为0,1，且

当i=j的时候，有aij=1

大概长这样（卑鄙如我2333）

1.3三对角矩阵

当 | i - j |>1 时，aij=0    <=>  非零出现在主对角线上，且仅靠上下两侧

大概长这样：

1.4上三角矩阵

当i>j的时候，aij=0

大概长这样：

1.5下三角矩阵

当i<j的时候，aij=0

大概长这样：

1.6置换矩阵

每一行每一列有且仅有1个1

大概长这样：

1.7对称矩阵

  :行与列互换的结果

大概长这样：

2.矩阵的运算

2.1加法

2.1.(1)

设A=(aij).B=(bij)，为矩阵，则矩阵和记为C=(cij)=A+B

定义为cij=aij+bij    (i | 1<=i<=m) (j | 1<=j<=n)

2.1(2)

零矩阵式矩阵加法运算的单位元：A+0=A=0+A

2.1(3)

若为常数，则有：A=(aij)  => 当=-1时，A+A=0=A+A

2.2减法

由2.1(3)可得A-B=A+(-B)

2.3.乘法

2.3.(1)要求：可以相乘的2个矩阵必须满足两个矩阵相容（一个矩阵行数=另一个矩阵列数）

2.3.(2)设：A=(aij)是矩阵，B=(bij)是矩阵

那么=C=(cij)是一个

分析这个公式，可以发现做了次的乘法与次的加法

由很多blog说自己推一遍就理解了

但这里给出一个很直观的计算方法：得出来的矩阵第i行第j列=第一个矩阵的第i行m个数与第二个矩阵第j列的m个数的分别乘积的和

2.3.(3)性质：

a.不满足交换率，AB!=BA

b.满足分配率，A(B+C)=AB+AC    (B+C)D=BD+CD

c.满足结合律，A(BC)=(AB)C

3.快速幂

（blog施工中，请绕行至其他dalao的blog）

4.矩阵乘法快速幂

用于优化递推的话，就要写出递推式。

下面给出本题的写法：

斐波那契的递推式是：

那么可以改写成这个形式：

以及将f(n-1)写成这个形式

然后由于矩阵乘法的定义，可以得到这个公式：

然后将后面的那个矩阵由结合律又可以得出：

（blog未完成然后就点了发布了！！！？？？点个收藏尽请期待）

代码

下面是我的学习手记（逃）