题解 | #矩阵乘法计算量估算#
矩阵乘法计算量估算
http://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
'''
A是一个50×10的矩阵,B是10×20的矩阵,C是20×5的矩阵
((AB)C)
AB,即50x10与10x20->50x20,新矩阵一共1000个值,获得每个值需要有10个数相乘求和,故1000x10=10000次乘法次数
(AB)C,即50x20与20x5->50x5,新矩阵一共250个值,获得每个值需要有20个数相乘求和,故250x20=5000次乘法次数
'''
while True:
try:
n = int(input())# 相乘矩阵的个数
arr = []# 存放所有矩阵行列数据
res = 0# 用于累加每次矩阵相乘的乘法次数
for i in range(n):# arr=[[50,10],[10,20],[20,5]]
arr.append(list(map(int, input().split())))
order = []# 用于构造栈
f = input()# 计算的法则字符串
for i in f:
if i.isalpha():
order.append(arr[ord(i)-65]) # 将字母转换成第几个矩阵的处理信息
elif i == ')' and len(order) >= 2:# 读到右括号就处理最近的两个矩阵相乘的结果
b = order.pop()
a = order.pop()
res += a[0]*b[1]*a[1]# 累计到res中
order.append([a[0], b[1]])
print(res)
except:
break
A是一个50×10的矩阵,B是10×20的矩阵,C是20×5的矩阵
((AB)C)
AB,即50x10与10x20->50x20,新矩阵一共1000个值,获得每个值需要有10个数相乘求和,故1000x10=10000次乘法次数
(AB)C,即50x20与20x5->50x5,新矩阵一共250个值,获得每个值需要有20个数相乘求和,故250x20=5000次乘法次数
故一共10000+5000=15000次
解题思路:
while True:
try:
n = int(input())# 相乘矩阵的个数
arr = []# 存放所有矩阵行列数据
res = 0# 用于累加每次矩阵相乘的乘法次数
for i in range(n):# arr=[[50,10],[10,20],[20,5]]
arr.append(list(map(int, input().split())))
order = []# 用于构造栈
f = input()# 计算的法则字符串
for i in f:
if i.isalpha():
order.append(arr[ord(i)-65]) # 将字母转换成第几个矩阵的处理信息
elif i == ')' and len(order) >= 2:# 读到右括号就处理最近的两个矩阵相乘的结果
b = order.pop()
a = order.pop()
res += a[0]*b[1]*a[1]# 累计到res中
order.append([a[0], b[1]])
print(res)
except:
break
【牛客站内】华为机试题—中等 文章被收录于专栏
【牛客站内】华为机试题练习记录