矩阵链乘 Matrix Chain Multiplication Uva442

Phaedra ·

更新时间:2024-09-20

· 532 次阅读

题目描述:
输入n个矩阵的维度和一些矩阵链乘表达式，输出乘法的次数。如果乘法无法进行，输出error。假定A是m*n矩阵，B是n*p矩阵，那么AB是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
输入：首先输入矩阵数量n，接下来n行输入矩阵的字母及其第一二维的基数，接下来一行输入需要计算的表达式。
输出：对于每一个表达式有一个输出，即需要乘法的次数，若乘法无法进行则输出error

样例输入输出
在这里插入图片描述
代码源自算法竞赛入门经典（刘汝佳编著）P142
本文只是增添一些注释
代码如下：

//6-3 矩阵链乘
#include 
#include 
#include 
#include 
using namespace std;
struct Matrix{
    int a,b;
    Matrix(int a=0,int b=0):a(a),b(b){};//构造函数
}m[26]; //26个字母代表式子中不同的变量，每一个变量代表一个矩阵
stack  s;//用于存放未参与计算的变量（字母）
int main()
{
   int n;       //字母数量
   cin>>n;
   for(int i=0;i>name;
       int k=name[0]-'A';
       cin>>m[k].a>>m[k].b;
   }
   string expr;//保存需要计算的式子
   while(cin>>expr){
       int len=expr.length();
       bool _judge=true; //判断这个式子能否计算
       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){           //矩阵相乘的前提是左矩阵的列数等于右矩阵的行数
                   ans+=m1.a*m1.b*m2.b;
                   s.push(Matrix(m1.a,m2.b));
               }
               else{
                   _judge=false;
                   break;
               }
           }
       }
       if(_judge)
           printf("%d\n",ans);
       else {
           printf("error\n");
       }
   }
   return 0;
}

作者：青铜亡者

matrix 矩阵

1024 个赞