实验02 刘红亮

[实验目的]

1. 掌握动态规划算法的基本方法 2. 掌握动态规划算法中最优子结构的分析 3. 掌握递归求解最优值的方法 4. 掌握最优解的构造.

[预习要求]

1. 认真阅读算法设计教材,了解动态规划原理;

2. 设计用动态规划算法求解矩阵连乘、最长公共子序列以及电路布线的java程序.

[实验题]

1. 给定n个矩阵{A1, A2, …,An}，其中，Ai与Ai+1是可乘的，计算这n个矩阵的连乘积。

从中找出一种乘次数最少的计算次序。

2. 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 3. 在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))

将上端接线柱与下端接线柱相连，确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。

[实验步骤]

1. 设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2. 应用设计的算法和程序求解问题; 3. 将程序整理成功能模块存盘备用.

[实验报告要求]

1. 阐述实验目的和实验内容; 2. 阐述求解问题的算法原理; 3. 提交实验程序的功能模块; 4. 记录最终测试数据和测试结果。 [实验结果]： 1.public class Matrix {

private int MN; private int[] p;

private int [][][]A; private int [][]m;

private int [][]s; public Matrix() { }

MN=0;

p=new int [MN];

public Matrix(int L) { }

private void CreatMatrix(int [][]a,int m,int n) {

for(int i=0;ifor(int j=0;ja[i][j]=(int) Math.round(Math.random

MN=L;

p=new int [MN+1]; A=new int [MN][][]; m=new int [MN+1][MN+1]; s=new int [MN+1][MN+1]; for(int i=0;i<=MN;i++) { }

for(int i=0;iA[i]=new int [p[i]][p[i+1]]; CreatMatrix(A[i],p[i],p[i+1]);

p[i]=(int) Math.round(Math.random()*10)+1;

()*99)-50;

}

private void printAllM() {

for (int i=0;iSystem.out.println(\"A\"+(i+1)+\": \"+A[i].length

+\"*\"+A[i][0].length );

}

private void printM(int [][]a) {

for(int i=0;iSystem.out.print(\" \"); for(int j=0;jSystem.out.print(String.format(\"%4d\

}

printM(A[i]);

a[i][j]));

}

public static void main(String [] args) {

Matrix M=new Matrix(7); M.printAllM();

M.matrixChain(M.p,M.m,M.s);

System.out.print(\"矩阵链所需的最少乘次数为：\"+M.m[1] }

System.out.println();

[M.MN]);

System.out.println();

String []s=new String[M.MN+1]; for(int i=1;i<=M.MN;i++) { }

M.traceback(M.s, 1, M.MN,s); for(int i=1;i<=M.MN;i++) { }

System.out.print(s[i]);

s[i]=\"A\"+i;

}

public static void matrixMultiply(int [][]a,int [][]

b,int [][]c,int ra,int ca,int rb,int cb)

{

if(ca!=rb)

throw new IllegalArgumentException(\"

矩阵不可乘\");

}

public static void matrixChain(int []p, int [][]m,

}

for(int i=0;ifor (int j=0;jint sum =a[i][0]*b[0][j]; for(int k=1;ksum+=a[i][k]*b[k][j];

c[i][j]=sum;

int [][]s)

{

int n=p.length-1;

for (int i=1;i<=n;i++) m[i][i]=0; for (int r=2;r<=n;r++)

for(int i=1;i<=n-r+1;i++) {

int j=i+r-1;

m[i][j]=m[i+1][j]+p[i-1]*p

[i]*p[j];

s[i][j]=i;

for (int k=i+1; kint t=m[i][k]+m[k+1]

[j]+p[i-1]*p[k]*p[j];

if (t}

}

}

{ }

m[i][j]=t; s[i][j]=k;

public static void traceback(int [][]s,int i,int

j,String []c)

{

if(i==j) return; traceback(s,i,s[i][j],c); traceback(s,s[i][j]+1,j,c); c[i]=\"(\"+c[i]; c[j]=c[j]+\")\";

System.out.println(\"Multiply A\"+i+\

[j]+\"and A\"+(s[i][j]+1)+\ }

}

2.public class Xl { private char []x; private char []y; private int xl; private int yl; public Xl(int m,int n) { xl=m; yl=n; x=new char [xl]; y=new char [yl]; for(int i=0;i } for(int i=0;iprivate void print() { for(int i=0;ipublic static void main(String []args) { Xl xl1=new Xl(10,12); int [][]b=new int [xl1.xl][xl1.yl]; int lcsl=lcsLength(xl1.x,xl1.y,b); xl1.print(); System.out.println(); System.out.print(\"最长公共子序列的长度为：\"+lcsl); System.out.println(); xl1.lcs(xl1.xl-1,xl1.yl-1,xl1.x, b); }

public static int lcsLength(char []x,char []y,int [][]b) { int m=x.length-1; int n=y.length-1; int [][]c=new int [m+1][n+1]; for(int i=1;i<= m;i++) c[i][0]=0; for(int i=1;i<= n;i++) c[0][i]=0; for(int i=1;i<= m;i++) for (int j=1;j<=n;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][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } return c[m][n];

}

public static void lcs(int i,int j,char []x,int [][]b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { lcs(i-1,j-1,x,b); System.out.print(String.format(\"%3s\ } else if (b[i][j]== 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); }

}

3.public class WireSet { private int n; private int m; private int []c; private int [][]size; private int []net; public WireSet(int num) { n=num; c=new int [n+1]; size=new int [n+1][n+1]; net=new int [n+1]; c[1]=(int)(Math.random()*(n)+1); int i=2; while(i<=n) { int f=0; int t=(int)(Math.random()*(n)+1); for(int j=1;j System.out.print(\"上端线路编号：\"); for(int i=0;i<=n;i++) { System.out.print(String.format(\"%3d\ } System.out.println(); System.out.println(); System.out.print(\"下端线路编号：\"); for(int i=0;i<=n;i++) { System.out.print(String.format(\"%3d\ } System.out.println(); System.out.print(\"最大不相交子集的大小为：\"+size[n][n]); System.out.println(); System.out.print(\"上端线路编号：\"); for(int i=this.m-1;i>=0;i--) { System.out.print(String.format(\"%3d\ } System.out.println(); System.out.print(\"下端线路编号：\"); for(int i=this.m-1;i>=0;i--) { System.out.print(String.format(\"%3d\ } }

public static void main(String []args){ WireSet ws= new WireSet(10); ws.mnset(ws.c, ws.size); ws.m=ws.traceback(ws.c, ws.size, ws.net); ws.print(); }

public static void mnset(int []c,int [][]size) { int n=c.length-1; for(int j=0;jpublic static int traceback(int []c,int [][]size ,int []net) { int n=c.length-1; int j=n; int m=0; for(int i=n;i>1;i--)

}

}

if(size[i][j]!=size[i-1][j]) { net[m++]=i; j=c[i]-1; } if(j>=c[1]) net[m++]=1; return m;