矩阵乘法题解

题目概述

本题要求实现两个矩阵的乘法运算。给定一个 $n \times m$ 的矩阵 $A$ 和一个 $m \times p$ 的矩阵 $B$，计算它们的乘积 $C = A \times B$，其中 $C$ 是一个 $n \times p$ 的矩阵。

矩阵乘法原理

矩阵乘法的定义如下：对于结果矩阵 $C$ 中的每个元素 $c_{ij}$，有：

这意味着 $c_{ij}$ 是矩阵 $A$ 的第 $i$ 行与矩阵 $B$ 的第 $j$ 列对应元素乘积的和。

算法思路

1. 输入处理：读取矩阵 $A$ 和 $B$ 的维度及元素值
2. 结果初始化：创建一个 $n \times p$ 的矩阵 $C$，初始值全为0
3. 三重循环计算：
   • 外层循环遍历 $A$ 的行（$i$ 从 0 到 $n-1$）
   • 中层循环遍历 $B$ 的列（$j$ 从 0 到 $p-1$）
   • 内层循环遍历公共维度（$k$ 从 0 到 $m-1$），累加 $A[i][k] \times B[k][j]$ 到 $C[i][j]$
4. 输出结果：按行输出矩阵 $C$

代码实现

#include <iostream>
using namespace std;

int main() {
    int n, m, p;
    
    // 读取矩阵A的维度
    cin >> n >> m;
    
    // 定义矩阵A、B和结果矩阵C
    int A[105][105], B[105][105], C[105][105];
    
    // 读取矩阵A
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];
        }
    }
    
    // 读取矩阵B的列数
    cin >> p;
    
    // 读取矩阵B
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < p; j++) {
            cin >> B[i][j];
        }
    }
    
    // 初始化结果矩阵C
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;
        }
    }
    
    // 矩阵乘法计算
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            for (int k = 0; k < m; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    
    // 输出结果矩阵C
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            cout << C[i][j];
            if (j < p - 1) {
                cout << " ";
            }
        }
        cout << endl;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \times m \times p)$，由三重循环决定
• 空间复杂度：$O(n \times m + m \times p + n \times p)$，用于存储三个矩阵

注意事项

1. 矩阵乘法不满足交换律，即 $A \times B \neq B \times A$
2. 矩阵 $A$ 的列数必须等于矩阵 $B$ 的行数才能进行乘法运算
3. 结果矩阵 $C$ 的行数等于 $A$ 的行数，列数等于 $B$ 的列数
4. 在代码实现中，数组大小应略大于最大可能维度（如105），防止越界

示例演示

以题目样例为例：

输入：
2 3
1 2 3
3 2 1
2
1 1
2 2
3 3

计算过程：
C[0][0] = 1×1 + 2×2 + 3×3 = 1 + 4 + 9 = 14
C[0][1] = 1×1 + 2×2 + 3×3 = 1 + 4 + 9 = 14
C[1][0] = 3×1 + 2×2 + 1×3 = 3 + 4 + 3 = 10
C[1][1] = 3×1 + 2×2 + 1×3 = 3 + 4 + 3 = 10

输出：
14 14
10 10

这道题是线性代数和算法实现的基础题目，掌握矩阵乘法对于理解更复杂的数值计算和机器学习算法至关重要。