实验二 最长公共子序列
09电信实验班 I09660118 徐振飞
一、实验名称
实现书本P56页所描述的二分搜索技术
二、实验目的
（1）掌握并运用动态规划方法基本思想
（2）掌握并运用动态规划算法解题的4个步骤 （3）运用动态规划算法编写最长公共子序列程序
三、实验内容和原理
（1）实验内容
给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
最长公共子序列问题：给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn}，找出X和Y的最长公共子序列。运用动态规划算法实现最长公共子序列问题。
（2）实验原理
动态规划算法适用于解最优化问题。通常可按以下4个步棸设计： （1）找出最优解的性质，并刻画其结构特征 （2）递归地定义最优值
（3）以自底向上的方式计算出最优值
（4）根据计算最优值时得到的信息，构造最优解 1.最长公共子序列的结构
设序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}的最长公共子序列为Z={z1,z2,...,zk}，则
（1）若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列。 （2）若xm<>yn且zk<>xm，则Z是Xm-1和Y的最长公共子序列。 （3）若xm<>yn且zk<>yn，则Z是X和Yn-1的最长公共子序列。 2.子问题的递归结构
首先建立子问题的最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,...xi}；Yj={y1,y2,...yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：
0i?0,j?0c[i][j]?{c[i?1][j?1]?1i,j?0;xi?yj
max{c[i][j?1],c[i?1][j]}i,j?0;xi?yj3.计算最优值
计算最长公共子序列长度的动态规划算法LCSLength以序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}最为输入，输出两个数组c和b。其中c[i][j]存储Xi和Yj的最长公共子序列的长度，b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的，这在构造最长公共子序列时要用到。问题的最优值，即X和Y的最长公共子序列的长度记录于c[m][n]中。 4.构造最长公共子序列
由算法LCSLength计算得到的数组b可用于快速构造序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}的最长公共子序列。首先从b[m][n]开始，依其值在数组b中搜索。当在b[i][j]=1时，表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列。当b[i][j]=2时，表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。当b[i][j]=3时，表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。
四、流程图
开始检查是否输入第一个字符序列NY检查是否输入第二个字符序列NY调用LCSLength算法调用LCS算法显示输出结果结束
五、源程序
1.view.java //视图类
import java.awt.*;
import java.awt.event.ActionEvent; import java.awt.event.ActionListener;
import javax.swing.*;
public class View implements ActionListener { JTextField firstStr; JTextField secondStr; JButton search; JLabel result; public View(){
JFrame jf = new JFrame(); jf.setLocation(200,100); jf.setSize(500,270);
jf.setLayout(new GridLayout(3,1));
JLabel firstString = new JLabel(\请输入第一个字符串：\); firstStr = new JTextField(30); JPanel p1 = new JPanel(); p1.add(firstString); p1.add(firstStr);
JLabel secondString = new JLabel(\请输入第一个字符串：\); secondStr = new JTextField(30); JPanel p2 = new JPanel(); p2.add(secondString); p2.add(secondStr);
search = new JButton(\确定\); search.addActionListener(this); JPanel p3 = new JPanel(); result = new JLabel(); p3.add(search); p3.add(result); jf.add(p1); jf.add(p2); jf.add(p3);
jf.setVisible(true); }
public String getFirstString(){ return firstStr.getText(); }
public String getSeconndString(){ return secondStr.getText(); }
@Override
public void actionPerformed(ActionEvent e) { if(e.getSource() == search){
if(firstStr.getText().equals(\) secondStr.getText().equals(\)){
JOptionPane.showMessageDialog(null,\请先输入！\); return; }
else{
Search s = new Search();
s.init(getFirstString(), getSeconndString()); s.LCSLength();
s.LCS(firstStr.getText().length(), secondStr.getText().length());
if(s.doWork().equals(\)){ } }
result.setText(\最长公共子串为空！\); }
else{
||
result.setText(\最长公共子串为：\+s.doWork()); } } }
2.search.java //算法实现类
import java.util.Arrays;
public class Search { char[] x; char[] y;
String result = \; int m=0,n=0; int[][] c; int[][] b;
public void init(String first,String second){ m = first.length(); x = new char[m+1];
for(int i=1;i<=m;i++){
x[i] = first.charAt(i-1); }
n = second.length(); y = new char[n+1];
for(int i=1;i<=n;i++){
y[i] = second.charAt(i-1); }
c = new int[m+1][n+1]; b = new int[m+1][n+1]; }
public void LCSLength(){ int i,j;
for(i=1;i<=m;i++){ c[i][0] = 0; }
for(i=1;i<=n;i++){ c[0][i] = 0; }
for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(x[i] == y[j]){
c[i][j] = c[i-1][j-1] + 1; b[i][j] = 1; }
else if(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; } } } }
public void LCS(int i,int j){ if(i==0 || j==0){return;} if(b[i][j]==1){ LCS(i-1,j-1);
result=result+x[i]; }
else if(b[i][j]==2){ LCS(i-1,j); }
else{
LCS(i,j-1); } }
public String doWork(){