首页 > 代码库 > 矩阵链乘(Matrix Chain Multiplication)
矩阵链乘(Matrix Chain Multiplication)
输入n个矩阵的维度和一些矩阵链乘表达式，输出乘法的次数。如果乘法无法进行，则输出error。假定A是m*n矩阵，B是n*p矩阵，那么A*B是m*p矩阵，乘法次数为m*n*p。如果A的列数不等于B的行数，则乘法无法进行。
例如，A是50*10的，B是10*20的，C是20*5的，则(A(BC))的乘法次数为10*20*5（BC的乘法次数） +50*10*5（A(BC)的乘法次数） = 3500。
#include<cstdio>
#include<stack>
#include<string>
#include<iostream>
using namespace std;
struct Matrix {
int a, b;
Matrix(int a = 0, int b = 0) :a(a), b(b) {}
}m[26];
stack<Matrix> s;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string name;
cin >> name;
int k = name[0] - ‘A‘;
cin >> m[k].a >> m[k].b;
}
string expr;
while (cin >> expr) {
int len = expr.length();
bool error = false;
int ans = 0;
for (int i = 0; i < len; i++) {
if (isalpha(expr[i])) s.push(m[expr[i] - ‘A‘]);
else if (expr[i] == ‘)‘) {
Matrix m2 = s.top(); s.pop();
Matrix m1 = s.top(); s.pop();
if (m1.b != m2.a) { error = true; break; }
ans += m1.a *m1.b *m2.b;
s.push(Matrix(m1.a, m2.b));
}
}
if (error) printf("error\n"); else printf("%d\n", ans);
}
return 0;
}
矩阵链乘(Matrix Chain Multiplication)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。