编程实现动态规划的算法实验报告.doc

《编程实现动态规划的算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告实验序号：　　　　　实验项目名称:编程实现动态规划的算法学　　号姓　　名专业、班11软服2班实验地点指导教师实验时间2013/11/29一、实验目的及要求1.体验实现程序的运行过程2.写出源程序，并编译运行。二、实验内容与步骤1.矩阵连乘问题（或多边形游戏问题）2.最长公共子序列问题（或最接近点对问题）三、实验方法四、实验结果与数据处理最长公共子序列：乘法五、分析与讨论对上机实践结果进行分析，上机的心得体会。六、教师评语签名：日期：附源程序清单：最长公共子序列：Importjava.io.Buff

2、eredReader;Importjava.io.IOException;Importjava.io.InputStreamReader;Importjava.util.ArrayList;Importjava.util.Scanner;Importjava.util.List;/***动态规划法解最长公共子系列。*@author蓝冠恒*/PublicclassLcsLength{publicstaticListresultList=NewArrayList();/***计算最优

3、值*@paramx*字符系列数组*@paramy*字符系列数组*@paramc*存储x和y最长公共子系列长度数组*@paramb*记录c中元素对应子问题的解的数组*/publicstaticvoidlcsLength(charx[],chary[],int[][]c,int[][]b){intm=x.length-1;intn=y.length-1;resultList.clear();for(inti=1;i<=m;i++){c[i][0]=0;}for(inti=1;i<=n;i++){c[0][i]=0;}for(i

4、nti=1;i<=m;i++){for(intj=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}}publicstaticvoidlcs(inti,intj,charx[],int[][]b){if(i==0

5、

6、j==0){return;}if(b[i][j]==1

7、){lcs(i-1,j-1,x,b);resultList.add(x[i]);}elseif(b[i][j]==2){lcs(i-1,j,x,b);}else{lcs(i,j-1,x,b);}}publicstaticvoidmain(Stringarg[]){Stringa;Stringinput;char[]x;char[]y;Scannerscan=NewScanner(System.in);BufferedReaderin=NewBufferedReader(NewInputStreamReader(System

8、.in));do{try{do{System.out.println("请输入第一串字符系列");input=in.readLine().trim();}while(input.equals(""));input="S"+input;x=input.toCharArray();do{System.out.println("请输入第二串字符系列");input=in.readLine().trim();}while(input.equals(""));input="S"+input;y=input.toCharArray()

9、;int[][]b=newint[x.length][y.length];int[][]c=Newint[x.length][y.length];lcsLength(x,y,c,b);//计算最优值lcs(x.length-1,y.length-1,x,b);//构造最长公共子系列intsize=resultList.size();System.out.print("最长公共子系列为:");for(inti=0;i

10、out.println("");}catch(IOExceptione){e.printStackTrace();}System.out.print("继续输入请按y。。退出请按任意键！");a=scan.nextLine();}while(a.equals("y"));}}连乘问题importja