备忘录矩阵连乘;最大公共子串算法JAVA程序.doc

实验报告5
课程 数据结构与算法 实验名称 动态规划 第 页
班级 11计本 学号 105032011130 姓名 风律澈
实验日期：2013年4月1日 报告退发 (订正 、 重做)
一、实验目的
掌握动态规划策略的原理和应用。
二、实验环境
1、微型计算机一台
2、WINDOWS操作系统，Java SDK，Eclipse开发环境
三、实验内容
必做题：
1. 要求采用备忘录方法编写程序求解矩阵连乘问题，要求输出问题最优值及最优解。
要求：输出矩阵连乘最少需要的数乘次数，同时输出最优运算顺序，以A、B、C、D四个矩阵连乘为例，输出最优解格式为：(A(B*C)*D)
2. 编写程序求解最长公共子序列问题，要求输出问题最优值及最优解。
要求：输出最长公共子序列长度，同时，依次输出该序列的每个元素。
四、实验步骤和结果
(附上代码和程序运行结果截图)
1，备忘录版本的矩阵连乘

public class LookupChain {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int p[]={30,35,15,5,10,20,25};//记录数组行列数量
int b[][]=new int[p.length][p.length];//记录连乘次数
int s[][]=new int[p.length][p.length];//记录最佳分割位置
for(int i=1;i<p.length;i++)//初始化数组 b
b[i][i]=0;
System.out.println(lookupChain(b,p,s,1,p.length-1));
coutlc(1,p.length-1,s);
}

private static void coutlc(int i,int j,int s[][]) {
// TODO Auto-generated method stub

if(i==j)
System.out.print("A"+i);
else if(i+1==j)
{System.out.print("(A"+i+"*"+"A"+j+")");}
else
{
System.out.print("(");
coutlc(i,s[i][j],s);
coutlc(s[i][j]+1,j,s);
System.out.print(")");
}
}

private static int lookupChain(int[][] b, int[] p, int[][] s,int i,int j) {
// TODO Auto-generated method stub
if(b[i][j]>0)
return b[i][j];
if(i==j)
return 0;

int u=lookupChain(b,p,s,i+1,j)+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;k<j;k++){
int t=lookupChain(b,p,s,i,k)+lookupChain(b,p,s,k+1,j)+p[i-1]*p[k]*p[j];
if(u>t)
{
u=t;
b[i][j]=u;
s[i][j]=k;
}
}
return u;
}
}

2.最长公共自序列
public class Lcslength {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
char a[]={'A','B','C','B','D','A','B'};
char b[]={'B','D','C','A','B','A'};
int x[][]=new int[b.length+1][a.length+1];
//inite
for(int i=0;i<a.length+1;i++)
x[0][i]=0;
for(int i=0;i<b.length+1;i++)
x[i][0]=0;
//lcs
lcslength(a,b,x);
//print
System.out.println(x[b.length][a.length]);
coutlcs(x,b.length,a.length,b);

}

private static void coutlcs(int[][] x, int i, int j,char []b) {
// TODO Auto-generated method stub
if(i==0||j==0)
return;
if(x[i-1][j-1]==x[i-1][j]&&x[i-1][j-1]==x[i][j-1])
{
coutlcs(x,i-1,j-1,b);
System.out.print(b[i-1]);
}
else if(x[i-1][j]>x[i][j-1])
coutlcs(x,i-1,j,b);
else
coutlcs(x,i,j-1,b);
}

private static void lcslength(char[] a, char[] b, int[][] x) {
// TODO Auto-generated method stub
for(int i=1;i<=b.length;i++)
for(int j=1;j<=a.length;j++)
{
if(b[i-1]==a[j-1])
x[i][j]=x[i-1][j-1]+1;
else if(x[i][j-1]>x[i-1][j])
x[i][j]=x[i][j-1];
else
x[i][j]=x[i-1][j];
}
}

}

五、实验总结
(本次实验完成的情况，心得体会)