动态规划—整数划分和矩阵连乘的java程序

《动态规划—整数划分和矩阵连乘的java程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告4课程数据结构与算法实验名称动态规划第1页班级11计本学号105032011130姓名刘川葆实验日期：2013年3月25日报告退发(订正、重做)一、实验目的掌握动态规划策略的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统，JavaSDK，Eclipse开发环境三、实验内容必做题：1.编写程序采用动态规划策略求解整数划分问题。要求：输出给定整数n的划分个数。2.编写程序求解矩阵连乘问题，要求输出最优解。要求：输出矩阵连乘最少需要的数乘次数，同时输出最优运算顺序，以A、B、C、D四个矩阵

2、连乘为例，输出最优解格式为：(A(B*C)*D)四、实验步骤和结果(附上代码和程序运行结果截图)1.动态规划—整数划分importjava.util.Scanner;publicclassZSHF{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstub//键盘输入nScannerin=newScanner(System.in);System.out.println("inputn:");intn=in.ne

3、xtInt();//建立b数组存放动态规划结果intb[][]=newint[n+1][n+1];//由于0行0列不用，故要加一//进入划分函数h_f_d(b);//输出最后结果System.out.println(b[n][n]);}privatestaticvoidh_f_d(int[][]b){//TODOAuto-generatedmethodstub//初始化数组，对任何数不大于1的划分进行赋值for(inti=1;i

4、r(intk=2;kk){if(l-k>k)/*由于数组的另一半并没有赋值，故要对l-k?k的情况进行分类*/b[l][k]=b[l][k-1]+b[l-k][k];elseb[l][k]=b[l][k-1]+b[l-k][l-k];}}}}}2动态规划—矩阵连乘publicclassJZLC{/***@para

5、margs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintp[]={30,35,15,5,10,20,25};//记录数组行列数量intb[][]=newint[p.length][p.length];//记录连乘次数ints[][]=newint[p.length][p.length];//记录最佳分割位置matrixChain(b,p,s);traceback(s,1,p.length-1);System.out.pr

6、intln();System.out.println(b[1][p.length-1]);}privatestaticvoidtraceback(int[][]s,inti,intj){//TODOAuto-generatedmethodstub//观察解的格式，发现如果只有单个的A，那么只要输出Ai，前后会有括号//如果是连续的A，则规律是i+1=j，那么此时不要使用括号//在分割点左边是用“（”，在分割点右边是用“）”,此时采用递归去求解使用括号的位置if(i==j)System.out.print("A"+

7、i);elseif(i+1==j)System.out.print("(A"+i+"*"+"A"+j+")");else{System.out.print("(");traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);System.out.print(")");}}privatestaticvoidmatrixChain(int[][]b,int[]p,int[][]s){//TODOAuto-generatedmethodstubintn=p.length-1;//初

8、始化对角线的位置为0；for(inti=1;i<=n;i++)b[i][i]=0;//开始进入for(intr=2;r<=n;r++)//从2列开始确定对角线以外的值for(inti=1;i<=n-r+1;i++){intj=i+r-1;//当k等于i时b[i][j]=b[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;//当k不等于i时intt=0