• 欢迎光临~

HJ70 矩阵乘法计算量估算

开发技术 开发技术 2022-08-02 次浏览

题目描述

矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如:

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

计算A*B*C有两种顺序:((AB)C)或者(A(BC)),前者需要计算15000次乘法,后者只需要3500次。

编写程序计算不同的计算顺序需要进行的乘法次数。
 
数据范围:矩阵个数:1le nle 15 1n15 ,行列数:1le row_i,col_ile 1001rowi,coli100 ,保证给出的字符串表示的计算顺序唯一。
进阶:时间复杂度:O(n)O(n) ,空间复杂度:O(n)O(n) 

输入描述:

输入多行,先输入要计算乘法的矩阵个数n,每个矩阵的行数,列数,总共2n的数,最后输入要计算的法则
计算的法则为一个字符串,仅由左右括号和大写字母('A'~'Z')组成,保证括号是匹配的且输入合法!

输出描述:

输出需要进行的乘法次数

示例

输入:
4
24 3
3 46
46 39
39 36
(A(B(CD)))
输出:
72144

 

解题思路:

该题与四则运算这道题有些类似,但是运算只有矩阵乘法一种,所以不需要考虑运算符的事,我们只需要考虑矩阵、'(',和')'。

我们还是使用双栈法,创建两个栈,一个存放表达式进度(stOper),一个存放矩阵边长边宽(stValue)。遇到'('直接进栈,遇到')'需要考虑是否可以弹栈计算(如果括号内只有一个矩阵,就不用计算了)。

这里表达式中的矩阵,在记录表达式计算进度的栈中都用符号'A'表示。遇到矩阵先查看stOper栈顶是否为矩阵,若是则说明该矩阵要与栈中的矩阵进行计算,否则只需将该矩阵压入栈中。

遇到')'时,stOper栈中栈顶往下两个元素一定是'A'和'(',我们需要将'('从栈(表达式计算进度)中消除,然后用'A'代替'(A)'。去除后,如果栈顶是符号'A',则需要计算'AA'的结果。

代码如下:

#include <iostream>
#include <stack>
#include <vector>
#include <string>
using namespace std;

struct Matrix {
    int x, y;
};

int main() {
    int n;
    string reg;
    while (cin >> n) {
        Matrix matrix[16];
        for (int i = 0; i < n; i++) {
            cin >> matrix[i].x >> matrix[i].y;
        }
        cin >> reg;
        int len = reg.length();
        int num = 0, index = 0;
        stack<Matrix> stValue;
        stack<char> stOper;

        for (int i = 0; i < len; i++) {
            if (reg[i] == '(') {
                stOper.push('(');
            }
            else if (reg[i] == ')') {
                stOper.pop();
                stOper.pop();
                if (stValue.size() >= 2 && stOper.top() == 'A') {
                    stOper.push('A');
                    Matrix tmp1 = stValue.top();
                    stValue.pop();
                    stOper.pop();
                    Matrix tmp2 = stValue.top();
                    stValue.pop();
                    stOper.pop();
                    num += tmp1.x*tmp1.y*tmp2.x;
                    tmp2.y = tmp1.y;
                    stValue.push(tmp2);
                    //stOper.push('A');
                }
                stOper.push('A');
            }
            else {
                if (!stValue.empty() && stOper.top() == 'A') {
                    Matrix tmp = stValue.top();
                    stValue.pop();
                    num += tmp.x*tmp.y*matrix[index].y;
                    tmp.y = matrix[index].y;
                    stValue.push(tmp);
                    index++;
                    stOper.pop();
                }
                else {
                    stValue.push(matrix[index++]);
                }
                stOper.push('A');
            }
        }
        cout << num << endl;
    }
    return 0;
}

 

程序员灯塔
转载请注明原文链接:HJ70 矩阵乘法计算量估算
喜欢 (0)