南京信息工程大学算法设计与分析实验.doc

南京信息工程大学 算法设计与分析 实验(实习)报告实验(实习)名称 最长公共子序列 实验(实习)日期 6.10 得分 指导老师 系 计软 专业 软件工程 班级 3 姓名 学号 一、 实验目的：(1)能够熟悉最长公共子序列问题这个算法(2)掌握并应用动态规划算法解决最长公共子序列问题二、 实验内容 使用动态规划解决最长公共子序列问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。三、 实验步骤源代码：import java.io.*;import java.util.ArrayList;import java.util.List;public class xd public static List re=new ArrayList();static int m,n;static int c;static char b;public xd()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 charx.lengthy.length; int c=new intx.lengthy.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,char b,int c) m=x.length-1; n=y.length-1;re.clear();for(int j=0;j=n;j+) c0j=0;b0j=;System.out.print(c0j);System.out.print(n);for(int i=0;i=m;i+) ci0=0;bi0=;for(int i=1;i=m;i+)System.out.print(0);for( int j=1;j=cij-1)cij=ci-1j;bij=;elsecij=cij-1;bij=;System.out.print(cij);System.out.print(n);for(int i=0;i=m;i+)for(int j=0;j=n;j+)System.out.print(bij);System.out.print(n); return cmn;/求公共子序列public static void lcsPut(int i,int j,char x,char b)if (i=0 | j=0)return;if (bij=)lcsPut(i-1,j-1,x,b);re.add(xi);else if(bij=) lcsPut(i-1,j,x,b);