资源描述：
《实验二 最长公共子序列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验二最长公共子序列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、最长公共子序列问题。（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是
3、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。其他情况下，由最优子结构性质可建立递归关系如下：3.计算最优值计算最长公共子序列长度的动态规划算法LCSLength以序列X={x1,x2,.
4、..,xm}和Y={y1,y2,...,yn}最为输入，输出两个数组c和b。其中c[i][j]存储Xi和Yj的最长公共子序列的长度，b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的，这在构造最长公共子序列时要用到。问题的最优值，即X和Y的最长公共子序列的长度记录于c[m][n]中。2.构造最长公共子序列由算法LCSLength计算得到的数组b可用于快速构造序列X={x1,x2,...,xm}和Y={y1,y2,...,yn}的最长公共子序列。首先从b[m][n]开始，依其值在数组b中搜索。当在
5、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的最长公共子序列相同。四、流程图五、源程序1.view.java//视图类importjava.awt.*;importjava.awt.event.ActionEvent;importjava.awt.event.ActionL
6、istener;importjavax.swing.*;publicclassViewimplementsActionListener{JTextFieldfirstStr;JTextFieldsecondStr;JButtonsearch;JLabelresult;publicView(){JFramejf=newJFrame();jf.setLocation(200,100);jf.setSize(500,270);jf.setLayout(newGridLayout(3,1));JLabelfirst
7、String=newJLabel("请输入第一个字符串：");firstStr=newJTextField(30);JPanelp1=newJPanel();p1.add(firstString);p1.add(firstStr);JLabelsecondString=newJLabel("请输入第一个字符串：");secondStr=newJTextField(30);JPanelp2=newJPanel();p2.add(secondString);p2.add(secondStr);search=ne
8、wJButton("确定");search.addActionListener(this);JPanelp3=newJPanel();result=newJLabel();p3.add(search);p3.add(result);jf.add(p1);jf.add(p2);jf.add(p3);jf.setVisible(true);}publicStringgetFirstString(){returnfir
