7-31打卡

wlxdaydayup / 2023-08-01 / 原文

矩阵快速幂求斐波那契数列

快速幂
将指数n表示成二进制形式。
从二进制的最低位开始遍历，如果当前位为1，则累乘底数x；否则，不进行任何操作。
将底数x不断平方，并更新指数n为n的一半。
重复步骤2和步骤3，直到遍历完整个二进制表示。

public class FibonacciMatrix {
    public static void main(String[] args) {
        int n = 10; // 求第10个斐波那契数列的值

        long result = fibonacci(n);
        System.out.println("F(" + n + ") = " + result);
    }

    public static long fibonacci(int n) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }

        // 定义初始矩阵
        long[][] baseMatrix = {{1, 1}, {1, 0}};

        // 使用矩阵快速幂算法求解矩阵的n次方
        long[][] resultMatrix = matrixPow(baseMatrix, n - 1);

        // 矩阵中的第一个元素就是F(n)
        return resultMatrix[0][0];
    }

    public static long[][] matrixPow(long[][] matrix, int n) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        // 创建单位矩阵
        long[][] identityMatrix = new long[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                identityMatrix[i][j] = (i == j) ? 1 : 0;
            }
        }

        // 使用快速幂算法求解矩阵的n次方
        while (n > 0) {
            if (n % 2 == 1) {
                identityMatrix = matrixMultiply(identityMatrix, matrix);
            }
            matrix = matrixMultiply(matrix, matrix);
            n /= 2;
        }

        return identityMatrix;
    }

    public static long[][] matrixMultiply(long[][] A, long[][] B) {
        int rowsA = A.length;
        int colsA = A[0].length;
        int colsB = B[0].length;

        long[][] result = new long[rowsA][colsB];

        for (int i = 0; i < rowsA; i++) {
            for (int j = 0; j < colsB; j++) {
                for (int k = 0; k < colsA; k++) {
                    result[i][j] += A[i][k] * B[k][j];
                }
            }
        }

        return result;
    }
}