中国矿业大学算法概论作业一 C、矩阵相乘
2021/10/15 11:14:32
本文主要是介绍中国矿业大学算法概论作业一 C、矩阵相乘,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
C、矩阵相乘
题目描述
给定n个矩阵{A1,A2,…,An},及m个矩阵连乘的表达式,判断每个矩阵连乘表达式是否满足矩阵乘法法则,如果满足,则计算矩阵的最小连乘次数,如果不满足输出“MengMengDa“。
输入
输入数据由多组数据组成(不超过10组样例)。每组数据格式如下:
第一行是2个整数n (1≤n≤26)和m(1≤m≤3),表示矩阵的个数。
接下来n行,每行有一个大写字母,表示矩阵的名字,后面有两个整数r和c,分别表示该矩阵的行数和列数,其中1<r, c<100。
第n+1行到第n+m行,每行是一个矩阵连乘的表达式(2<=矩阵个数<=100)。
输出
对于每个矩阵连乘表达式,如果运算不满足矩阵乘法法则的情况(即左矩阵列数与右矩阵的行数不同),则输出“MengMengDa”,否则输出最小矩阵连乘次数。
数据保证结果不超过1e9。
样例输入
3 2
A 10 100
B 5 50
C 100 5
ACB
ABC
样例输出
7500
MengMengDa
题解(动态规划问题)
#include <bits/stdc++.h> #include<string> using namespace std; struct node{ char name; int r=0; int c=0; }a[30]; int convert(char x, int n) { int i; for( i=0; i<n; i++) if(a[i].name == x) break; return i; } long int MatrixCharin(int *p, int n,long int m[][101]) { for(int i=0;i<=n;i++) m[i][i]=0; for(int r=2; r<=n; r++) // r个矩阵相乘 for(int i=1; i<=n-r+1; i++) { int j = i+r-1; // 本循环的最后一个矩阵 m[i][j] = m[i][i] + m[i+1][j] + p[i-1]*p[i]*p[j]; // 假设最优划分位于i处 for(int k= i+1; k<j; k++) // 变化最优分割的位置, 逐一测试 { long int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if(t < m[i][j] ) m[i][j] = t; // 如果更优替换原位置 } } return m[1][n]; } int main() { int m, n; char str[3][101]; // 输入的矩阵字符串 long int x[101][101]; int p[3][101]; int flag[3]; while(cin>>n>>m){ memset(str, 0, sizeof(' ')); for(int i=0; i < n; i++) cin>>a[i].name>>a[i].r>>a[i].c; for(int i=0; i< m ; i++) { cin>>str[i]; flag[i]=0; for(int k=0; k< strlen(str[i]); k++) { if(k==0){ p[i][k] = a[convert(str[i][k], n)].r; p[i][k+1] = a[convert(str[i][k], n)].c; } else { if(p[i][k] == a[convert(str[i][k], n)].r){ p[i][k+1] = a[convert(str[i][k], n)].c; } else{ flag[i]=1; } } } } for(int i=0; i<m ; i++) { if(flag[i] == 1){ cout<<"MengMengDa"<<endl; } else { long int result = MatrixCharin(p[i], strlen(str[i]), x); cout<<result<<endl; } } } return 0; }
这篇关于中国矿业大学算法概论作业一 C、矩阵相乘的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升