题解 | #矩阵幂#

矩阵幂

https://www.nowcoder.com/practice/31e539ab08f949a8bece2a7503e9319a

#include <iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
struct Matrix {
    int row, col;
    int matrix[10][10];
    Matrix(int r, int c): row(r), col(c) {}
};
void printMatrix(Matrix res) {
    for (int i = 0; i < res.row; i++) {
        for (int j = 0; j < res.col; j++) {
            cout << res.matrix[i][j] << " ";

        }
        cout << "\n";
    }
}
Matrix multiMatrix(Matrix A, Matrix B) {
    Matrix res(A.row, B.col);
    for (int i = 0; i < A.row; i++) {
        for (int j = 0; j < B.col; j++) {
            res.matrix[i][j] = 0;
            for (int k = 0; k < A.col; k++) {
                res.matrix[i][j] += A.matrix[i][k] * B.matrix[k][j];
            }
        }
    }
    return res;
}
//求k次幂
Matrix matricExp(Matrix A, int k) {
    Matrix res(A.row, A.col);
    for (int i = 0; i < A.row; i++) {
        for (int j = 0; j < A.col; j++) {
            if (i == j) {
                res.matrix[i][j] = 1;
            } else {
                res.matrix[i][j] = 0;
            }
        }
    }
    while (k != 0) {
        if (k % 2 == 1) { //如果最后一位为1
            res = multiMatrix(res, A);
        }
        A = multiMatrix(A, A); //下一次循环时,最后一位的权值
        k /= 2;
//      cout<<"当前矩阵为\n";
//      printMatrix(res);
    }
    return res;
}
int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF) {
        Matrix A(n, n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &A.matrix[i][j]);
//                cout<<"test1:"<<A.matrix[i][j]<<" "<<"\n";
            }
        }
//        printMatrix(A);
        Matrix answer = matricExp(A, k);
        printMatrix(answer);
    }
    return 0;
}

全部评论

相关推荐

09-01 11:31
门头沟学院 Java
buul:七牛云的吧,感觉想法是好的,但是大家没那么多时间弄他这个啊。。。不知道的还以为他是顶尖大厂呢还搞比赛抢hc,只能说应试者的痛苦考察方是无法理解的,他们只会想一出是一出
点赞 评论 收藏
分享
08-25 14:25
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务