题解 | #矩阵乘法计算量估算#

矩阵乘法计算量估算

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次乘法次数
故一共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

【牛客站内】华为机试题练习记录

全部评论

相关推荐

挣K存W养DOG:他真的很中意你,为什么不回他
点赞 评论 收藏
分享
评论
1
2
分享
牛客网
牛客企业服务