斐波那契logn算法（利用矩阵）Java-创新互联
本人只是刚开始学算法，了解可能不太透彻，有些东西也会说错，见谅。只是希望做一个记录，并且希望在一些小的知识点上可以恰好帮助到犯迷糊的同学。这里是我看的视频上的一个斐波那契logn的一个算法，原理上不是很清楚，但是小的步骤是有的。
首先是原理部分。斐波那契可以用矩阵实现。具体为
|F3,F2| = |F2,F1| * |X| (X暂时是未知矩阵）
|F4,F3| = |F3,F2| * |X| = |F2,F1| * |X| * |X|
|F5,,F4| = |F4,F3| * |X| = |F2,F1| * |X| * |X| *|X|
以此类推
|Fn,Fn-1| = |F2,F1| * |X|的n-2次方
计算|X|首先写下斐波那契那一组数
1 , 1 , 2 , 3 , 5 , 8 , 13
|2,1| = |1,1| * |X|
|3,2| = |2,1| * |X|
按照矩阵的算法，1*a+1*c = 2 1*b+1*d = 1
2*a+1*c = 3 2*b+1*d = 2
算出a,b,c,d分别为1,1，1,0
所以|X|为|1 1|
|1 0|
算出来|X|就可以直接算想要的fn了
矩阵的计算想要计算最终结果，可以直接把n-2换成二进制表示，有1的位就|F2,F1|*|X|,然后|X|自乘，接着此二进制数右移1一位。 没一的位直接|X|自乘，二进制数进一位（叫快速幂）
为什么矩阵可以这样求最终结果。大概是数学上的知识。本人并不想深究。
代码如下public static int fib(int n) {
if (n< 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
//下面的这几个还是靠自己算出来的，不过如果是普通的斐波那契，那这几个数是固定的
int[][] base = {{1, 1}, {1, 0}};
//[1,1]
//[1,0]
int[][] res = matrixPoewr(base, n - 2);
//因为一开始是两个1 1,1,2,3,5,8,13,用矩阵乘出来的结果就拿竖着的两个
return res[0][0] + res[1][0];
}
public static int[][] matrixPoewr(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];//结果
//初始化一个单位矩阵
for (int i = 0; i< res.length; i++) {
res[i][i] = 1;
}
int[][] t = m;//计数变量
//方法名为 快速幂，为什么可以这样不清楚，大概是数学上的知识，记住就好
//把幂变成二进制，从最后一位开始算
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {//判断末位是不是一个1，如果是1返回1
res = muliMatrix(res, t);
}
t = muliMatrix(t, t);
}
return res;
}
//矩阵相乘，返回的也是矩阵
public static int[][] muliMatrix(int[][] a, int[][] b) {
int n = a.length;//行
int m = b[0].length;//列
int k = a[0].length;
int[][] ans = new int[n][m];
for (int i = 0; i< n; i++) {
for (int j = 0; j< m; j++) {
for (int c = 0; c< k; c++) {
ans[i][j] += a[i][c] * b[c][j];
}
}
}
return ans;
}你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：斐波那契logn算法（利用矩阵）Java-创新互联
文章URL：http://mswzjz.cn/article/dehoso.html