描述

输入描述：

输入包含多组数据，每组数据包含： 第一行包含一个正整数x，代表第一个矩阵的行数 第二行包含一个正整数y，代表第一个矩阵的列数和第二个矩阵的行数 第三行包含一个正整数z，代表第二个矩阵的列数 之后x行，每行y个整数，代表第一个矩阵的值 之后y行，每行z个整数，代表第二个矩阵的值

输出描述：

对于每组输入数据，输出x行，每行z个整数，代表两个矩阵相乘的结果

知识点：数组

难度：⭐⭐⭐

题解

方法一：模拟

图解：

解题思路：

根据矩阵相乘的特性，处理行和列的关系进行模拟即可

算法流程：

• 先处理输入和矩阵的初始化和赋值
• 遍历arr1每一行，计算矩阵相乘后的结果，逐行输出
• 遍历arr2 每一列, 矩阵乘法是arr1的行乘以arr2的列
• 遍历arr1每一列，arr2每一行
• 最后根据矩阵相乘的特性，对结果进行空格分隔和分行操作

Java 版本代码如下：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int x = in.nextInt();
            int y = in.nextInt();
            int z = in.nextInt();
            // 矩阵初始化和赋值
            int[][] arr1 = new int[x][y];
            int[][] arr2 = new int[y][z];
            for (int i = 0; i < x; i++) {
                for (int j = 0; j < y; j++) {
                    arr1[i][j] = in.nextInt();
                }
            } 
            for (int i = 0; i < y; i++) {
                for (int j = 0; j < z; j++) {
                    arr2[i][j] = in.nextInt();
                }
            }
            // 遍历arr1每一行，计算矩阵相乘后的结果，逐行输出
            for (int i = 0; i < x; i++) {
                StringBuilder res = new StringBuilder();
                // 遍历arr2 每一列, 矩阵乘法是arr1的行乘以arr2的列
                for (int j = 0; j < z; j++) {
                    int temp = 0;
                    // 遍历arr1每一列，arr2每一行
                    for (int k = 0; k < y; k++) {
                        temp += arr1[i][k] * arr2[k][j];
                    }
                    // 对于arr1的当前行，与arr2的每一列列相乘后，空格隔开
                    res.append(temp).append(" ");
                }
                // arr1的当前行和arr2的所有列相乘后，换行
                System.out.println(res.substring(0, res.length() - 1));
            }
        } 
    }
}

复杂度分析：

时间复杂度：$O(xyz)O(xyz)$， 其中x是arr1的行数，y是arr1的列数，z是arr2的列数

空间复杂度：$O(xy+yz)O(xy\; +\; yz)$，两个辅助矩阵的空间开销

方法二：逐行运算

解题思路：

从逐个值计算变为逐行计算，即改变三重for循环的顺序

代码如下：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int x, y, z;
    while (cin >> x >> y >> z){
        vector<vector<int>> A(x, vector<int>(y, 0));
        vector<vector<int>> B(y, vector<int>(z, 0));
        vector<vector<int>> C(x, vector<int>(z, 0));
        for(int i = 0; i < x; ++i){//输入矩阵A
            for(int j = 0; j < y; ++j)
                cin >> A[i][j];
        }
        for(int i = 0; i < y; ++i){//输入矩阵B
            for(int j = 0; j < z; ++j)
                cin >> B[i][j];
        }
        
        for(int i = 0; i < x; ++i){
            for(int j = 0; j < y; ++j){
                for(int k = 0; k < z; ++k){
                	//计算C第i行的值
                    C[i][k] += A[i][j] * B[j][k];
                }
            }
        }
        for(int i = 0; i < x; ++i){//输出C
            for(int j = 0; j < z-1; ++j)
                cout << C[i][j] << " ";
            cout << C[i][z-1] << endl;
        }
    }
    return 0;
}

复杂度分析：

时间复杂度：$O(xyz)O(xyz)$， 逐行计算，三重for循环计算C中的值。

空间复杂度：$O(xy+yz)O(xy\; +\; yz)$，两个辅助矩阵的空间开销