C++程序 实现矩阵相乘
给定两个矩阵,任务是将它们相乘。矩阵可以是正方形的,也可以是长方形的。
举个例子:
输入: mat1[][] = {{1, 2},
{3, 4}}
mat2[][] = {{1, 1},
{1, 1}}
输出: {{3, 3},
{7, 7}}
输入: mat1[][] = {{2, 4},
{3, 4}}
mat2[][] = {{1, 2},
{1, 3}}
输出: {{6, 16},
{7, 18}}
正方形矩阵相乘:
下面的程序将两个大小为4*4的正方形矩阵相乘,我们可以为不同的尺寸改变N。
//C++ 程序乘两个正方形矩阵。
#include <iostream>
using namespace std;
#define N 4
//这个函数乘mat1[][]和mat2[][], 保存在res[][]中。
void multiply(int mat1[][N],
int mat2[][N],
int res[][N])
{
int i, j, k;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
res[i][j] = 0;
for (k = 0; k < N; k++)
res[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
//主函数
int main()
{
int i, j;
int res[N][N]; //存储结果
int mat1[N][N] = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 4, 4, 4, 4 } };
int mat2[N][N] = { { 1, 1, 1, 1 },
{ 2, 2, 2, 2 },
{ 3, 3, 3, 3 },
{ 4, 4, 4, 4 } };
multiply(mat1, mat2, res);
cout << "结果矩阵是" << endl;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
cout << res[i][j] << " ";
cout << endl;
}
return 0;
}
输出
结果矩阵是
10 10 10 10
20 20 20 20
30 30 30 30
40 40 40 40
时间复杂度: O(n3)。可以使用Strassen的矩阵乘法进行优化。
辅助空间: O(n2)
长方形矩阵相乘:
我们使用C中的指针来乘以两个矩阵。请参阅以下帖子作为代码的先决条件如何将2D数组作为参数传递在C中?
//C++程序乘以两个长方形矩阵
#include <bits/stdc++.h>
using namespace std;
//乘法两个矩阵mat1[][]和mat2[][],并打印结果。(m1)乘以(m2)和(n1)乘以(n2)是给定矩阵的维度。
void multiply(int m1, int m2, int mat1[][2], int n1, int n2,
int mat2[][2])
{
int x, i, j;
int res[m1][n2];
for (i = 0; i < m1; i++)
{
for (j = 0; j < n2; j++)
{
res[i][j] = 0;
for (x = 0; x < m2; x++)
{
*(*(res + i) + j) += *(*(mat1 + i) + x)
* *(*(mat2 + x) + j);
}
}
}
for (i = 0; i < m1; i++)
{
for (j = 0; j < n2; j++)
{
cout << *(*(res + i) + j) << " ";
}
cout << endl;
}
}
//主函数
int main()
{
int mat1[][2] = { { 2, 4 }, { 3, 4 } };
int mat2[][2] = { { 1, 2 }, { 1, 3 } };
int m1 = 2, m2 = 2, n1 = 2, n2 = 2;
//函数调用
multiply(m1, m2, mat1, n1, n2, mat2);
return 0;
}
输出
6 16
7 18
时间复杂度: O(n 3 )。它可以使用Strassen的矩阵乘法进行优化
辅助空间: O(m1 * n2)