首页 > 试题广场 >

矩阵乘法计算量估算

[编程题]矩阵乘法计算量估算
  • 热度指数：79272 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的 a 行 b 列的矩阵：
A = \begin{bmatrix} A_{1,1} & A_{1,2} & \cdots & A_{1,b} \\ A_{2,1} & A_{2,2} & \cdots & A_{2,b} \\ \vdots & \vdots & \ddots & \vdots \\ A_{a,1} & A_{a,2} & \cdots & A_{a,b} \end{bmatrix}
\hspace{15pt}和 b 行 c 列的矩阵：
B = \begin{bmatrix} B_{1,1} & B_{1,2} & \cdots & B_{1,c} \\ B_{2,1} & B_{2,2} & \cdots & B_{2,c} \\ \vdots & \vdots & \ddots & \vdots \\ B_{b,1} & B_{b,2} & \cdots & B_{b,c} \end{bmatrix}
\hspace{15pt}和 c 行 d 列的矩阵：
C = \begin{bmatrix} C_{1,1} & C_{1,2} & \cdots & C_{1,d} \\ C_{2,1} & C_{2,2} & \cdots & C_{2,d} \\ \vdots & \vdots & \ddots & \vdots \\ C_{c,1} & C_{c,2} & \cdots & C_{c,d} \end{bmatrix}
\hspace{15pt}在计算 A \times B \times C 时，不同的运算顺序会带来不同的运算量。例如，(A \times B) \times C 的运算量是 a \times b \times c + a \times c \times d，而 A \times (B \times C) 的运算量是 b \times c \times d + a \times b \times d。

\hspace{15pt}现在，对于给定的 n 个矩阵的大小与运算式，请你计算出所需要的运算量。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 15\right) 代表矩阵的个数。
\hspace{15pt}此后 n 行，第 i 行输入两个整数 a_i 和 b_i \left(1 \leqq a_i, b_i \leqq 100\right) 代表第 i 个矩阵的行数和列数。
\hspace{15pt}最后一行输入一个长度为 1 \leqq {\rm len}(s) \leqq 10^3 的字符串 s 代表运算式。运算式中只包含前 n 个大写字母与括号，第 i 个大写字母对应输入的第 i 个矩阵，括号成对出现，保证运算式合法且正确。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表计算需要的运算量。
示例1

输入

3
50 10
10 20
20 5
(A(BC))

输出

3500
示例2

输入

3
50 10
10 20
20 5
((AB)C)

输出

15000

备注:
\hspace{15pt}本题数据已进行修复（2025/01/09）。
算法知识视频讲解
开通博客
头像 从8开始倒车
发表于 2020-07-03 19:00:55
输入和输出部分都很常规，我直接写中间的处理过程。 一、前提 假设矩阵乘法的矩阵存在arr_list中，计算的规则存在role_str中。arr_list = [[m,n], [n,p], [p,q]]role_str = (A(BC)) 二、运算 2.1.整体思路 通过对role_str进行逐个字符 展开全文
去ta的博客 赞 (48) 回复(6) 收起
头像 不会做题的小菜鸡
发表于 2021-12-10 02:38:16
题目分析 题目给出了矩阵的个数n，并紧接着给出n行矩阵的行和列，最后给出一个矩阵相乘的顺序，其中A、B、C等等分别直接对应每一个按顺序输入的矩阵 最终题目要求输出按照既定顺序规定的运算次数 方法一：栈思路处理 实现思路 我们发现在规定的矩阵相乘的顺序中，是由括号所规定的 每次我们读到一 展开全文
去ta的博客 赞 (41) 回复(10) 收起
头像 牛客834002708号
发表于 2021-08-13 21:44:59
import java.util.*; public class Main {     public static void main(String[] args) { 展开全文
去ta的博客 赞 (28) 回复(6) 收起
头像 AimerAimer
发表于 2021-12-06 21:19:17
题意：         A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵         计算 展开全文
去ta的博客 赞 (12) 回复(6) 收起
头像 朱德康
发表于 2022-05-15 12:30:19
1、字符 是左括号，什么也不做 2、字符 是右括号，出栈 3、字符 是非括号，入栈 import java.util.Scanner; import java.util.Stack; // 注意类名必须为&nbs 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 牛客940206908号
发表于 2021-10-10 14:55:02
#计算式的题目，考出入栈处理括号 #先摘抄优秀答案： #按照出入栈处理括号的思路，自己重写如下代码。 while True: try: n = int(input()) mdict = {} for i in range(n): 展开全文
去ta的博客 赞 (9) 回复(5) 收起
头像 牛客825869540号
发表于 2021-07-17 18:34:19
Python3: 栈 while True: try: n,dic,stk,num = int(input()),{},[],0 for i in range(n): key = chr(ord('A')+i) 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 必不可能秃头
发表于 2022-03-18 19:56:59
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.ne 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 daydayup牛
发表于 2022-03-29 10:50:45
其实这道题抽象一下，我们可以发现它其实就是表达式求值，唯一的问题就是矩阵乘法需要自己定义，还有一个问题就是让输入的字符串和具体的数据如何对应，看代码。 这道题它说的很简单就是总是会有括号，你可以通过括号来判断是否要乘，但下面这个更普适，只要矩阵能够相乘，他可以按乘法结合律从左至右，不需要括号。 这道 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 Lchenglong
发表于 2022-01-09 19:51:16
Python 代码实现： while True: try: alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' num = 0 n = int(input()) dict_a = {} fo 展开全文
去ta的博客 赞 (7) 回复(2) 收起

问题信息

字符串 栈
难度：
345条回答 35274浏览

热门推荐

通过挑战的用户

查看代码

相关试题

矩阵乘法计算量估算

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号