算法设计与分析实验2 动态规划法解最长公共子序列

1、实验二动态规划法解最长公共子序列一、实验内容及要求要求按动态规划法原理求解问题；要求交互输入两个序列数据；要求显示结果。二、实验仪器和软件平台仪器：普通电脑一台软件平台：WIN-XP + MyEchpse 6.0三、源程序import java.io.*;unport java.util. AnayList;unport java.util. List;public class LCSTest( 存放两个序列chai X,Y;int C,B；public void nutData()Stimg s;Suing Ime;mtj=0;tiy(System.out.prmtln(M请输入第一个序列(

2、逗号分开)”)；BufferedReader m=new BufferedReader(new InputStreaniReader(System.in);line=iii.readLine();s=lme.split(，7，)；X=new chais.length+l;fbr(int i=l ;i=s.length;i-H-)Xi=si-l.cliarAt(O);System.out.prmtlnCiW输入第二个序列(逗号分开)”)；line=iii.readLine();s=lme.split(，7，)；Y=new chais.length+l;fbr(int i=l;is.length;

3、i+)Yi=si-l.cliarAt(O);in. close。；)catch (Exception e)e.prmtStackTiace();)C=new mtX.lengthY.length;B=new mtX.lengthY.length;public void LCSLength(int m. mt n)Hit 1J；C00=0;C1O=O;fbr(i=l;i=n;i+)CO1=O;fbr(j=lj=Ci|j-l)(Ci|j=Ci-l|j;Bij=2；else(Ci|j=Cij-l;Bi|j=3;1)LCS (X. length- 1,Y. length-1);public void

4、LCS(iiit i, int j)iRi=O|j=O)return;if(Bi|j=l)LCS(i-lj-l);System.out.print(Xi+IF ”);)else if(Bij=2)LCS(i-lj);elseLCS(ij-l);public void showResult()System.out.println(”X Y的最长公共子序列为;tills. LC SLength(X. length-1, Y. length-1);public static void niain(Striiig args) tluows ExceptionLCSTest t=new LCSTestQ;t.mitDataQ;t.showResult();五.运行结果 LCSTest Java Application D:MyEclipse 8.0Commonb!narycorr请输入第一个序列(逗号分开)请iXiz个序列(逗号分开)cf e,rrbfwFgX 丫的晶长公共子序列为；六.实验小结通过这次实验比较好地理解了动态规划法解最长公共子序列的算法。最长公 共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们 的雷同程度，从