斐波那契数列

题目

题目一：给定整数N，返回斐波那契数列的第N项，斐波那契数列：1,1,2,3,5,8,12......

补充题目一：给定整数N，代表台阶数，一次可以跨2个或1个台阶，返回有多少种走法。

补充题目二：农场的母牛每年只会生出1头小母牛，并且永远不会死，小母牛3年后成熟又可以生小母牛，求N年后牛的数量

要求

实现时间复杂度为O(logN)的解法

解答

题目一：

O(2ⁿ)的解法：递归，除了第一项，第二项之外，其他项的结果都有

实现

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. 当n>2时，申请三个变量：res 表示 第 n 项的值，pre 表示 res 前一个的值(n-1)，tmp 表示临时值
2. 计算 res = res + pre, 原来的 res 变为 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)的解法：使用矩阵乘法

二阶递推数列用二阶矩阵表示：

推动公式：

则有

使用矩阵方程表示：

当 n > 2 时

最终有：

所以，求斐波那契数列第N项就变成了求矩阵的第N次方的问题，而求矩阵的N次方能够在O(logN) 时间内解决

要求矩阵的N次方的O(logN) ，先看整数的N次方的O(logN)的求法

整数的N次方的O(logN) 解法，以10的 75 次方为例

1. 求 75 的 二进制，结果为 1001011, 75 = (1001011)₂ = (1000000)₂ + (1000)₂ + (10)₂ + (1)₂ = 64 + 8 + 2 +1
2. 所以 10⁷⁵ = 10⁶⁴ * 10⁸ * 10² * 10¹
3. 首先求 10¹, 根据 10¹ -> 10², 10² -> 10⁴, 10⁴ -> 10⁸,...
4. 当遇到位为1，则累成，否则则跳过

实现

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)解法

实现

public int[] [] matrixPower(int[][] m, int p) {
    int[] res = new int[m.length][m[0].length];
    // 把 res 设置为单位矩阵
    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];
}