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

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

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

2、ption;Importjava.io.InputStreamReader;Importjava.util.ArrayList;Importjava.util.Scanner;Importjava.util.List;/***动态规划法解最长公共子系列。*@author蓝冠恒*/PublicclassLcsLength{publicstatic.---ListresultList=NewArrayList();/***计算最优值*@paramx*字符系列数组*@paramy*字符系列数组*@paramc*存储x和y最长公共子系列长度数组.---*@p

3、aramb*记录c中元素对应子问题的解的数组*/public.---staticvoidlcsLength(charx[],chary[],int[][]c,int[][]b){intm=x.length-1;int.---n=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(inti=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][

4、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;}}}}publicstaticvoid.---lcs(inti,intj,charx[],int[][]b){if(i==0

5、

6、j==0){return;}.---if(b[i][j]==1){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);}}p

7、ublicstaticvoidmain(Stringarg[]){Stringa;Stringinput;char[]x;char[]y;Scannerscan=NewScanner(System.in);BufferedReaderin=NewBufferedReader(NewInputStreamReader(System.in));do{try{do{System.out.println("请输入第一串字符系列");input=in.readLine().trim();}while(input.equals(""));input="S"+input;x=input.toCharArra

8、y();do{System.out.println("请输入第二串字符系列");input=in.readLine().trim();}while(input.equals(""));.---input="S"+input;y=input.toCharArray();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();

9、System.out.print("最长公共子系列为:");for(inti=0;i