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

备忘录法的矩阵连乘以及完全加括号法;分析两个串的最大公共子串,并输出其中一个最大公共自串;

实验报告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 {

private static void coutlc(int i,int j,int s[][]) { // TODO Auto-generated method stub /** * @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); }

备忘录法的矩阵连乘以及完全加括号法;分析两个串的最大公共子串,并输出其中一个最大公共自串;

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

} // TODO Auto-generated method stub if(b[i][j]>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++){ } return u; int if(u>t) { } u=t; b[i][j]=u; s[i][j]=k; return b[i][j]; return 0; if(i==j) j) { t=lookupChain(b,p,s,i,k)+lookupChain(b,p,s,k+1,j)+p[i-1]*p[k]*p[j];

备忘录法的矩阵连乘以及完全加括号法;分析两个串的最大公共子串,并输出其中一个最大公共自串;

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

/** * @param args */ public static void main(String[] args) { } 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]) { // 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]; 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; lcslength(a,b,x); //print System.out.println(x[b.length][a.length]); coutlcs(x,b.length,a.length,b);

备忘录法的矩阵连乘以及完全加括号法;分析两个串的最大公共子串,并输出其中一个最大公共自串;

} 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]; } }

}

五、实验总结

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