实验三动态规划.doc

1 算法分析与设计实验报告学号 1207132229 姓名吕联栋班级软服 2班上课地点教师陈思上课时间实验三动态规划 理解动态规划算法的主要设计思想和基本步骤; 掌握用动态规划策略解决实际问题。 Eclipse Window XP 0-1 背包问题 : 日期: 成绩 2 实验报告细表 1 矩阵连乘问题 算法设计思想给定 n 个矩阵,其中 A1与 Ai+1 是可乘的 i=1,2...n 。考察这 n 个矩阵的连乘积:A1a2A3..An. 由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号, 则可以依此次序反复调用 2 个矩阵相乘的标准算法计算出矩阵连乘积。 程序源码 package suanfa; import ; public class shiyansan1 { public static void main(String[] args) { Scanner scan = new Scanner(System. in ); System. out .print( " 输入矩阵个数:" ); int n= (); // 矩阵的个数 int p[]= new int [100]; int x[]= new int [100]; int y[]= new int [100]; for ( int i=0;i<n;i++) { System. out .print( "第" +(i+1)+ " 个矩阵行数: " ); x[i]=(); System. out .print( "第" +(i+1)+ " 个矩阵列数: " ); y[i]=(); } // 通过行列数得到 p[i] 的值 for ( int i=0;i<=n;i++) { if (i==0) p[i]=x[i]; else p[i]=y[i-1]; } // 定义最少数乘量和断点位置 int m[][]= new int [100][100]; int s[][]= new int [100][100]; 3 // 调用函数 matrixChain (p,m,s); traceback (s,1,n); System. out .println( " 矩阵连乘的最少数乘量为:" +m[1][n]); // 输出最少数乘量} // 主要的方法,矩阵连乘的方法 public static void matrixChain( int []p, int [][]m, int [][]s) { int n=p. length -1; for ( int i=1;i<=n;i++) m[i][i]=0; // 对角线元素 m[i][i] 赋值为 0 // 控制矩阵的链长度 r=2~n for ( int r=2;r<=n;r++) for ( int i=1;i<=n-r+1;i++) { int j=i+r-1; //