最长公共子序列算法分析实验报告.docVIP

实验报告 课程名称 算法设计与分析 实验项目名称 实验1：最长公共子序列 班级与班级代码 实验室名称（或课室） 专 业 计算机科学与技术 任课教师 学 号： 姓 名： 实验日期： 2014 年 11月 16日 广东财经大学教务处 制 姓名 实验报告成绩 完成情况 项目 很好 好 一般 及格 差 实验目的实现 实验内容完成 实验步骤和操作 是否符合要求 分析与思考 总成绩 指导教师（签名） 2014年 月 日 说明：指导教师评分后，实验报告交院（系）办公室保存。 实验目的： (1)能够熟悉最长公共子序列问题这个算法 (2)掌握并应用动态规划算法解决最长公共子序列问题 实验内容 使用动态规划解决最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 三、实验环境 Window7、eclipse 四、实验步骤与结果 （1）当输入的两个字符串没有公共子序列时： （2）当输入的两个字符串有公共子序列时： 数值表和状态表如下图： 实验结果： 五、心得体会 从本次实验中，我对动态规划算法有了进一步的认识，从代码的一步步完成，更加深刻体会到了理论与实践的结合是多么不容易了。 六、实验源代码： package suanfa; import java.io.*; import java.util.ArrayList; import java.util.List; public class Lcs { public static List re=new ArrayListCharacter(); static int m,n; static int c[][]; static char b[][]; public Lcs(){//构造方法 String in; char x[],y[]; BufferedReader buf=new BufferedReader(new InputStreamReader(System.in)); do{ try{ do{ System.out.println(请输入第一个字符串：); in=buf.readLine().trim(); }while(in.equals()); in=S+in; x=in.toCharArray(); do{ System.out.println(请输入第二个字符串：); in=buf.readLine().trim(); }while(in.equals()); in=S+in; y=in.toCharArray(); char b[][]=new char[x.length][y.length]; int c[][]=new int[x.length][y.length]; int len=lcsLength(x,y,b,c);//计算最长公共子序列的长度 System.out.println(最长公共子序列的长度为:+len); if(len==0){System.out.println(没有公共子序列!);return;} else{ lcsPut(x.length-1,y.length-1,x,b); int size=re.size(); System.out.print(最长公共子序列为：); for(int i=0;isize;i++){ System.out.print(re.get(i)); } System.out.print(\n);} }catch(IOException e){ e.printStackTrace(); } }while(true); } //求长度的方法 public int lcsLength(char x[],char y[],c