题解 | #矩阵乘法计算量估算#

矩阵乘法计算量估算

https://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b?tpId=37&&tqId=21293&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking

题意：

A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵

计算A*B*C有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。

编写程序计算不同的计算顺序需要进行的乘法次数。

方法一：

栈

思路：

        栈存储矩阵的行和列。

      遍历字符串：

                                如果是字符，则直接入栈；

                               如果是右括号，则栈弹出两个元素，并累加乘法次数，再形成新的矩阵并入栈。

在这过程并累加乘法次数，最后输出乘法次数。

#include <bits/stdc++.h>

using namespace std;
int a[20][2];
string s;

int main(){
    int n;
    while(cin >> n){
        for(int i=0;i<n;i++)
            cin >> a[i][0] >> a[i][1];//输入矩阵的行列
        cin >>s;
        stack<pair<int,int>> st;//栈存储矩阵的行列
        int len=s.size();
        int res=0;
        for(int i=0;i<len;i++){//遍历字符串
            if(s[i]==')'){//如果是右括号，则栈弹出两个元素，并累加乘法次数
                auto y=st.top();
                st.pop();
                auto x=st.top();
                st.pop();
                if(x.second==y.first){
                    res+=x.second*x.first*y.second;
                    st.push({x.first,y.second});//形成新的矩阵并入栈
                }else if(x.first==y.second){
                    res+=x.first*x.second*y.first;
                    st.push({x.second,y.first});
                }
                
            }else if(s[i]!='('){//如果是字符，则直接入栈
                int t=s[i]-'A';
                st.push({a[t][0],a[t][1]});
            }
        }
        cout << res << endl;//输出答案
    }
    
    return 0;
}

时间复杂度： $O(n),n是字符串的长度，遍历字符串。$

空间复杂度： $O(n),n是字符串大小，栈的存储空间。$

方法二

递归

思路：

      通过递归找到左右边界点。

      规则：

              遍历给定字符串的 l , r 区间，如果找到左括号，则循环找到匹配的右括号，并递归下去。

              最后，计算两个矩阵的值赋给全局变量res,并且生成新的矩阵。

#include <bits/stdc++.h> using namespace std; int a[20][2]; string s; int res=0,n; //递归 pair<int,int> f(int l,int r){ stack<pair<int,int>> st; for(int i=l;i<=r;i++){ if(s[i]=='('){ int j=i+1; int level=1; while(j<=r){//循环找到匹配的右括号 if(s[j]=='('){ level++; }else if(s[j]==')'){ level--; if(level==0){ auto t=f(i+1,j-1);//递归 st.push(t);//后序入栈 break; } } j++; } i=j; }else if(isalpha(s[i])){ int x=s[i]-'A'; st.push({a[x][0],a[x][1]}); } } auto t2=st.top(); st.pop(); auto t1=st.top(); st.pop(); res+=t1.first*t1.second*t2.second;//构造新的矩阵 return {t1.first,t2.second}; } int main(){ while(cin >> n){ res=0; for(int i=0;i<n;i++) cin >> a[i][0] >> a[i][1];//输入矩阵的行列 cin >>s; f(1,s.size()-2);//递归 cout << res << endl;//输出答案 } return 0; }