欢迎来到天天文库
浏览记录
ID:38670367
大小:277.00 KB
页数:17页
时间:2019-06-17
《动态规划算法实验报告》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、实验标题1、矩阵连乘2、最长公共子序列3、最大子段和4、凸多边形最优三角剖分5、流水作业调度6、0-1背包问题7、最优二叉搜索树实验目的掌握动态规划法的基本思想和算法设计的基本步骤。实验内容与源码1、矩阵连乘#include#includeusingnamespacestd;constintsize=4;//ra,ca和rb,cb分别表示矩阵A和B的行数和列数voidmatriMultiply(inta[][4],intb[][4],intc[][4],intra,intca,intrb,intcb){if(ca!=rb)cerr<<"矩阵不可
2、乘";for(inti=0;i3、*p[i]*p[j];s[i][j]=i;for(intk=i+1;k4、;}}intmain(){intw;cout<<"矩阵个数:";cin>>w;intp[w],s[w][w];cout<<"输入矩阵A1维数:";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"输入矩阵A"<>p[i-1]>>p[i];if(p[i-1]!=m){cout<#include5、#defineN100usingnamespacestd;//str1存储字符串x,str2存储字符串ycharstr1[N],str2[N];//lcs存储最长公共子序列charlcs[N];//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度intc[N][N];//flag[i][j]==0为str1[i]==str2[j]//flag[i][j]==1为c[i-1][j]>=s[i][j-1]//flag[i][j]==-1为c[i-1][j]6、x,char*y){inti,j;//分别取得x,y的长度intm=strlen(x);intn=strlen(y);for(i=1;i<=m;i++)c[i][0]=0;for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i]7、[j]=-1;}}returnc[m][n];}//求出最长公共子序列char*getLCS(char*x,char*y,intlen,char*lcs){inti=strlen(x);intj=strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len]=x[i-1];i--;j--;}elseif(flag[i][j]==1)i--;elsej--;}returnlcs;}intmain(){inti;cout<<"请输入字
3、*p[i]*p[j];s[i][j]=i;for(intk=i+1;k4、;}}intmain(){intw;cout<<"矩阵个数:";cin>>w;intp[w],s[w][w];cout<<"输入矩阵A1维数:";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"输入矩阵A"<>p[i-1]>>p[i];if(p[i-1]!=m){cout<#include5、#defineN100usingnamespacestd;//str1存储字符串x,str2存储字符串ycharstr1[N],str2[N];//lcs存储最长公共子序列charlcs[N];//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度intc[N][N];//flag[i][j]==0为str1[i]==str2[j]//flag[i][j]==1为c[i-1][j]>=s[i][j-1]//flag[i][j]==-1为c[i-1][j]6、x,char*y){inti,j;//分别取得x,y的长度intm=strlen(x);intn=strlen(y);for(i=1;i<=m;i++)c[i][0]=0;for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i]7、[j]=-1;}}returnc[m][n];}//求出最长公共子序列char*getLCS(char*x,char*y,intlen,char*lcs){inti=strlen(x);intj=strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len]=x[i-1];i--;j--;}elseif(flag[i][j]==1)i--;elsej--;}returnlcs;}intmain(){inti;cout<<"请输入字
4、;}}intmain(){intw;cout<<"矩阵个数:";cin>>w;intp[w],s[w][w];cout<<"输入矩阵A1维数:";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"输入矩阵A"<>p[i-1]>>p[i];if(p[i-1]!=m){cout<#include
5、#defineN100usingnamespacestd;//str1存储字符串x,str2存储字符串ycharstr1[N],str2[N];//lcs存储最长公共子序列charlcs[N];//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度intc[N][N];//flag[i][j]==0为str1[i]==str2[j]//flag[i][j]==1为c[i-1][j]>=s[i][j-1]//flag[i][j]==-1为c[i-1][j]
6、x,char*y){inti,j;//分别取得x,y的长度intm=strlen(x);intn=strlen(y);for(i=1;i<=m;i++)c[i][0]=0;for(i=0;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i]
7、[j]=-1;}}returnc[m][n];}//求出最长公共子序列char*getLCS(char*x,char*y,intlen,char*lcs){inti=strlen(x);intj=strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len]=x[i-1];i--;j--;}elseif(flag[i][j]==1)i--;elsej--;}returnlcs;}intmain(){inti;cout<<"请输入字
此文档下载收益归作者所有