聲明：

本人只是剛開始學(xué)算法，了解可能不太透徹，有些東西也會說錯，見諒。只是希望做一個記錄，并且希望在一些小的知識點(diǎn)上可以恰好幫助到犯迷糊的同學(xué)。這里是我看的視頻上的一個斐波那契logn的一個算法，原理上不是很清楚，但是小的步驟是有的。

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、小程序制作、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了平遠(yuǎn)免費(fèi)建站歡迎大家使用！正文：

首先是原理部分。斐波那契可以用矩陣實(shí)現(xiàn)。具體為

|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次方??

計(jì)算|X|

首先寫下斐波那契那一組數(shù)

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了

矩陣的計(jì)算

想要計(jì)算最終結(jié)果，可以直接把n-2換成二進(jìn)制表示，有1的位就|F2,F1|*|X|,然后|X|自乘，接著此二進(jìn)制數(shù)右移1一位。 沒一的位直接|X|自乘，二進(jìn)制數(shù)進(jìn)一位（叫快速冪）

為什么矩陣可以這樣求最終結(jié)果。大概是數(shù)學(xué)上的知識。本人并不想深究。

代碼如下

public static int fib(int n) {
        if (n< 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        //下面的這幾個還是靠自己算出來的，不過如果是普通的斐波那契，那這幾個數(shù)是固定的
        int[][] base = {{1, 1}, {1, 0}};
                        //[1,1]
                        //[1,0]
        int[][] res = matrixPoewr(base, n - 2);
        //因?yàn)橐婚_始是兩個1    1,1,2,3,5,8,13,用矩陣乘出來的結(jié)果就拿豎著的兩個
        return res[0][0] + res[1][0];
    }

    public static int[][] matrixPoewr(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];//結(jié)果
        //初始化一個單位矩陣
        for (int i = 0; i< res.length; i++) {
            res[i][i] = 1;
        }
        int[][] t = m;//計(jì)數(shù)變量

        //方法名為   快速冪，為什么可以這樣不清楚，大概是數(shù)學(xué)上的知識，記住就好
        //把冪變成二進(jìn)制，從最后一位開始算
        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;
    }

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：斐波那契logn算法（利用矩陣）Java-創(chuàng)新互聯(lián)
瀏覽路徑：http://jinyejixie.com/article30/dehoso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、企業(yè)建站、網(wǎng)站排名、靜態(tài)網(wǎng)站、網(wǎng)站建設(shè)、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)