矩阵乘法计算量估算代码实现

矩阵乘法计算量估算代码实现

这篇文章介绍了矩阵乘法计算量估算代码实现,分享给大家做个参考,收藏极客大全收获更多编程知识

题目描述

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

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

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

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

输入描述:

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

输出描述:

输出需要进行的乘法次数

示例

输入:424 33 4646 3939 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;
}

 



原文链接:https://www.cnblogs.com/glodears/p/16544946.html

    

站长公告

极客大全专注硬核技术知识分享,助您享受知识的乐趣

热门标签