资源描述:
《实验二 最长公共子序列》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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