首页 > 试题广场 >

矩阵乘法计算量估算

[编程题]矩阵乘法计算量估算
  • 热度指数:78668 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的 ab 列的矩阵:
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}bc 列的矩阵:
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}cd 列的矩阵:
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_ib_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进行逐个字符 展开全文
头像 不会做题的小菜鸡
发表于 2021-12-10 02:38:16
题目分析 题目给出了矩阵的个数n,并紧接着给出n行矩阵的行和列,最后给出一个矩阵相乘的顺序,其中A、B、C等等分别直接对应每一个按顺序输入的矩阵 最终题目要求输出按照既定顺序规定的运算次数 方法一:栈思路处理 实现思路 我们发现在规定的矩阵相乘的顺序中,是由括号所规定的 每次我们读到一 展开全文
头像 牛客834002708号
发表于 2021-08-13 21:44:59
import java.util.*; public class Main {     public static void main(String[] args) { 展开全文
头像 AimerAimer
发表于 2021-12-06 21:19:17
题意:         A是一个50×10的矩阵,B是10×20的矩阵,C是20×5的矩阵         计算 展开全文
头像 朱德康
发表于 2022-05-15 12:30:19
1、字符 是左括号,什么也不做 2、字符 是右括号,出栈 3、字符 是非括号,入栈 import java.util.Scanner; import java.util.Stack; // 注意类名必须为&nbs 展开全文
头像 牛客940206908号
发表于 2021-10-10 14:55:02
#计算式的题目,考出入栈处理括号 #先摘抄优秀答案: #按照出入栈处理括号的思路,自己重写如下代码。 while True: try: n = int(input()) mdict = {} for i in range(n): 展开全文
头像 牛客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) 展开全文
头像 必不可能秃头
发表于 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 展开全文
头像 daydayup牛
发表于 2022-03-29 10:50:45
其实这道题抽象一下,我们可以发现它其实就是表达式求值,唯一的问题就是矩阵乘法需要自己定义,还有一个问题就是让输入的字符串和具体的数据如何对应,看代码。 这道题它说的很简单就是总是会有括号,你可以通过括号来判断是否要乘,但下面这个更普适,只要矩阵能够相乘,他可以按乘法结合律从左至右,不需要括号。 这道 展开全文
头像 Lchenglong
发表于 2022-01-09 19:51:16
Python 代码实现: while True: try: alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' num = 0 n = int(input()) dict_a = {} fo 展开全文