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

实验(实习)名称 最长公共子序列   实验(实习)日期       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 char[x.length][y.length];

             int c[][]=new int[x.length][y.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;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++) {c[0][j]=0;b[0][j]='→';System.out.print(c[0][j]);}System.out.print("\\n");

        for(int i=0;i<=m;i++) {c[i][0]=0;b[i][0]='→';}

        for(int i=1;i<=m;i++){

            System.out.print(0);

            for( int j=1;j<=n;j++){

                if (x[i]==y[j]){

                    c[i][j]=c[i-1][j-1]+1;

                    b[i][j]='↘';

                }

                else if (c[i-1][j]>=c[i][j-1]){

                    c[i][j]=c[i-1][j];

                    b[i][j]='↓';

                }

                else{

                    c[i][j]=c[i][j-1];

                    b[i][j]='→';

                }

                System.out.print(c[i][j]);

            }System.out.print("\\n");

        }

        for(int i=0;i<=m;i++){

            for(int j=0;j<=n;j++){

                System.out.print(b[i][j]);

            }

            System.out.print("\\n");

         }

            return c[m][n];

        }

    //求公共子序列

    public static void lcsPut(int i,int j,char x[],char b[][]){

        if (i==0 || j==0)

        return;

        if (b[i][j]=='↘'){

            lcsPut(i-1,j-1,x,b);

            re.add(x[i]);

        }

        else if(b[i][j]=='↓') lcsPut(i-1,j,x,b);

            else lcsPut(i,j-1,x,b);

    }

//主方法

    public static void main(String args[]){

        jsc xd=new xd();

   }

}

四、实验截图