斐波那契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次方  

首先写下斐波那契那一组数

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元起，快前往官网查看详情吧