題目

題目一：給定整數(shù)N薄翅，返回斐波那契數(shù)列的第N項(xiàng)微峰，斐波那契數(shù)列：1,1,2,3,5,8,12......

補(bǔ)充題目一：給定整數(shù)N舷丹，代表臺(tái)階數(shù)，一次可以跨2個(gè)或1個(gè)臺(tái)階蜓肆，返回有多少種走法颜凯。

補(bǔ)充題目二：農(nóng)場(chǎng)的母牛每年只會(huì)生出1頭小母牛，并且永遠(yuǎn)不會(huì)死仗扬，小母牛3年后成熟又可以生小母牛症概，求N年后牛的數(shù)量

要求

實(shí)現(xiàn)時(shí)間復(fù)雜度為O(logN)的解法

解答

題目一：

O(2ⁿ)的解法：遞歸，除了第一項(xiàng)早芭，第二項(xiàng)之外彼城，其他項(xiàng)的結(jié)果都有

實(shí)現(xiàn)

public int f1(int n) {
    if (n < 1) {
        return 0;
    }
    if (n==1 || n==2) {
        return 1;
    }
    return f1(n-1) + f1(n-2);
}

O(N)的解法：

1. 當(dāng)n>2時(shí)，申請(qǐng)三個(gè)變量：res 表示 第 n 項(xiàng)的值退个，pre 表示 res 前一個(gè)的值(n-1)募壕，tmp 表示臨時(shí)值
2. 計(jì)算 res = res + pre, 原來(lái)的 res 變?yōu)?pre, 以此類推

public int f1(int n) {
    if (n < 1) {
        return 0;
    }
    if (n==1 || n==2) {
        return 1;
    }
    int res = 1;
    int pre = 1;
    int tmp = 0;
    for (int i = 3; i <=n; i++){
        tmp = res;
        res = res + pre;
        pre = tmp;
    }
    return res;
}

O(logN)的解法：使用矩陣乘法

二階遞推數(shù)列用二階矩陣表示：

推動(dòng)公式：

則有

使用矩陣方程表示：

當(dāng) n > 2 時(shí)

最終有：

所以，求斐波那契數(shù)列第N項(xiàng)就變成了求矩陣的第N次方的問(wèn)題语盈，而求矩陣的N次方能夠在O(logN) 時(shí)間內(nèi)解決

要求矩陣的N次方的O(logN) 舱馅，先看整數(shù)的N次方的O(logN)的求法

整數(shù)的N次方的O(logN) 解法，以10的 75 次方為例

1. 求 75 的 二進(jìn)制刀荒，結(jié)果為 1001011, 75 = (1001011)₂ = (1000000)₂ + (1000)₂ + (10)₂ + (1)₂ = 64 + 8 + 2 +1
2. 所以 10⁷⁵ = 10⁶⁴ * 10⁸ * 10² * 10¹
3. 首先求 10¹, 根據(jù) 10¹ -> 10², 10² -> 10⁴, 10⁴ -> 10⁸,...
4. 當(dāng)遇到位為1代嗤，則累成，否則則跳過(guò)

實(shí)現(xiàn)

public int ex2(int number, int power) { // number = 10, power = 75
    int result = 1;
    int tmp = number;
    while (power != 0) {
        if((power & 1) == 1) { // 1001011 & 0000001 = 0000001 = 1
            result = result * tmp; // 1 * 10
        }
        tmp = tmp * tmp // 10 * 10 = 10^2
        power = power >> 1 // 1001011 >> 1 = 0100101
    }
    return result;
}

矩陣的N次方的O(logN)解法

實(shí)現(xiàn)

public int[] [] matrixPower(int[][] m, int p) {
    int[] res = new int[m.length][m[0].length];
    // 把 res 設(shè)置為單位矩陣
    for (int i = 0; i < res.length; i++) {
        res[i][i] = 1;
    }
    int[][] tmp = m;
    for(; p != 0; p >>= 1) {
        if((p & 1) != 0) {
            res = muliMatrix(res, tmp);
        }
        tmp = multiMatrix(tmp, tmp);
    }
    return res;
}

private int[][] multiMatrix(int[][] m1, int[][]m2) {
    int[][] res = new int[m1.length][m2[0].length];
    for (int i = 0; i < m2[0].length; i++) {
        for(int j = 0; j < m1.length; j++) {
            for(int k = 0; k < m2.length; k++) {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}

斐波那契求法

public int f3(int n) {
    if(n < 1) {
        return 0;
    }
    if(n == 1 || n ==2) {
        return 1;
    }
    int[][] base = {{1,1}, {1,0}};
    int[][] res = matrixPower(base, n-2);
    return res[0][0] + res[1][0];
}