一、实验内容及要求
1．要求按动态规划法原理求解问题；
2．要求在20以内整数随机产生两个序列数据；
3．要求显示随机产生的序列及最长公共子序列。
二、实验步骤
1、随机产生数列；
2、输出随机序列；
2、计算公共序列后，输出公共序列。
Java源代码：
package suanfafenxi;
import java.util.Random;
public class shiyan4 {
static int langth=10; //随机字符串的长度
static int[] x = new int[langth];
static int[] y= new int[langth];
static int [][]b=new int [ langth][langth];
//产生随机字符串x函数
public static void suijishux(){
Random rad=new Random(); //产生随机数
for (int i = 0; i<langth; i ++)
{
x[i] = rad.nextInt(20);
}
}
//产生随机字符串Y函数
public static void suijishuy(){
Random rad=new Random(); //产生随机数
for (int i = 0; i<langth; i ++)
{
y[i] = rad.nextInt(20);
}
}
//输出随机字符串X函数
public static void prinfx(){
System.out.print("随机字符串X:");
for (int i = 1; i < langth; i ++)
{
System.out.print("["+x[i]+"] ");
}
}
//输出随机字符串Y函数
public static void prinfy(){
System.out.print("
随机字符串Y:");
for (int i = 1; i < langth; i ++)
{
System.out.print("["+y[i]+"] ");
}
}
//主函数
public static void main(String[] args) {
try
{
suijishux();
System.out.println("随机序列X生成功。。。。");
}
catch(Exception e)
{
System.out.println("随机序列X生成失败！！");
}
try
{
suijishuy();
System.out.println("随机序列Y生成功。。。。");
}
catch(Exception e)
{
System.out.println("随机序列Y生成失败！！");
}
prinfx();
prinfy();
shiyan4 shiyan=new shiyan4();
shiyan.mixLength(x,y,b);
System.out.println("
X和Y的最长公共子序列 是：");
shiyan.bijiaojieguo(langth-1,langth-1,x,b);
}
public void mixLength(int []x,int []y,int [][]b){
int [][]c=new int[langth][langth];
for (int i=1;i<langth;i++) c[i][0]=0;
for (int i=1;i<langth;i++) c[0][i]=0;
for(int i=1;i<langth;i++)
for(int j=1;j<langth;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][1];
b[i][j]=2;
}
else{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
public void bijiaojieguo(int i,int j,int []x,int[][]b){
if(i==0 || j==0) return;
if(b[i][j]==1){
bijiaojieguo(i-1,j,x,b);
System.out.print(x[i]+" ");
}
else if (b[i][j]==2) bijiaojieguo(i-1,j,x,b);
else bijiaojieguo(i,j-1,x,b);
}
}
运行结果如下：
