首页 > 代码库 > 矩阵链乘(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)