题解 | #矩阵乘法计算量估算#可计算括号内有三矩阵的情况A(BCD)
矩阵乘法计算量估算
http://www.nowcoder.com/practice/15e41630514445719a942e004edc0a5b
def wukh(ss): #无括号情况
ls = []
for i in range(len(ss)): #取得矩阵行列信息
ls.append(jzs[zm.index(ss[i])])
ccj = 0
for i in range(0, len(ss)-1):
ccj += ls[i][1] * ls[i+1][1]
cc = ls[0][0] * ccj #计算这部分的乘法次数
return cc
def youkh(fz1): #有括号时的情况
global outs,fz
ind2 = fz1.find(')')
ind1 = fz1.rfind('(', 0, ind2)
ss = fz1[ind1 + 1:ind2] # 截取括号内片段
res = wukh(ss)
outs += res
zm.append(chr(ord(zm[-1]) + 1)) #添加新字母,取代括号部分
jzs.append([jzs[zm.index(ss[0])][0], jzs[zm.index(ss[-1])][1]]) #新矩阵的行列
A=fz1[ind1:ind2 + 1]
fz=fz.replace(A,zm[-1]) # 用新矩阵替换括号内部分
n = int(input())
jzs = []
outs = 0
for i in range(n):
jz = list(map(int, input().split()))
jzs.append(jz) # 矩阵行列信息
fz = input()
zm = []
for i in fz:
if i != '(' and i != ')' and i not in zm:
zm.append(i)
zm = sorted(zm) # 字母对应矩阵信息
while '(' in fz: # 有括号一直去括号
youkh(fz)
ress = wukh(fz) #去完括号计算最终值
outs += ress
print(outs)
查看1道真题和解析
