备忘录矩阵连乘;最大公共子串算法java程序

《备忘录矩阵连乘;最大公共子串算法java程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告5课程数据结构与算法实验名称动态规划第页班级11计本学号105032011130姓名风律澈实验日期：2013年4月1日报告退发(订正、重做)一、实验目的掌握动态规划策略的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统，JavaSDK，Eclipse开发环境三、实验内容必做题：1.要求采用备忘录方法编写程序求解矩阵连乘问题，要求输出问题最优值及最优解。要求：输出矩阵连乘最少需要的数乘次数，同时输出最优运算顺序，以A、B、C、D四个矩阵连乘为例，输出最优解格式为：(A(B*C)*D)2.编写程序求解最长公共子序列问题，要求输出问题最优值及最优解。要求：输出最长公共子

2、序列长度，同时，依次输出该序列的每个元素。四、实验步骤和结果(附上代码和程序运行结果截图)1，备忘录版本的矩阵连乘publicclassLookupChain{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintp[]={30,35,15,5,10,20,25};//记录数组行列数量intb[][]=newint[p.length][p.length];//记录连乘次数ints[][]=newint[p.length][p.length];//记录最佳分割位置for(inti=

3、1;i

4、coutlc(i,s[i][j],s);coutlc(s[i][j]+1,j,s);System.out.print(")");}}privatestaticintlookupChain(int[][]b,int[]p,int[][]s,inti,intj){//TODOAuto-generatedmethodstubif(b[i][j]>0)returnb[i][j];if(i==j)return0;intu=lookupChain(b,p,s,i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

5、b,p,s,i,k)+lookupChain(b,p,s,k+1,j)+p[i-1]*p[k]*p[j];if(u>t){u=t;b[i][j]=u;s[i][j]=k;}}returnu;}}2.最长公共自序列publicclassLcslength{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubchara[]={'A','B','C','B','D','A','B'};charb[]={'B','D','C','A','B','A'};intx[][]=newint[b.l

6、ength+1][a.length+1];//initefor(inti=0;i

7、

8、

9、j==0)return;if(x[i-1][j-1]==x[i-1][j]&&x[i-1][j-1]==x[i][j-1]){coutlcs(x,i-1,j-1,b);System.out.print(b[i-1]);}elseif(x[i-1][j]>x[i][j-1])coutlcs(x,i-1,j,b);elsecoutlcs(x,i,j-1,b);}privatestaticvoidlcslength