实验三动态规划.docx

实验三动态规划
　 算法 分析 与 设计 试验报告
　 学号
　姓名
　班级
　上课地点
　老师
　上课时间
　试验 三
　动态规划 1. 试验目的 理解动态规划算法的主要设计思想和基本步骤； 驾驭用动态规ia */
　 package juzhenliancheng;
　public class juzhenliancheng {
　public static void main(String[] args) {
　 int[]p = {30, 35, 15, 5, 10, 20, 25}; // 矩阵的维数存放于数组p中
　 matrixMultiply (p);
　 }
　 //矩阵连乘
　 public static void matrixMultiply( int[] p) {
　 int dimen = ;
　 int[][]m = new int[dimen][dimen];
　//定义了存放最优值数组m
　 int[][]s = new int[dimen][dimen];
　//定义了记录断开位置的数组s
　MatrixChain (p,m,s);
　System. out .println(最优乘法次数： + m[1][dimen - 1]);
　 System. out .println(划分规则为：);
　 traceback (s, 1, dimen - 1);
　 }
　/*1：首先计算出m[i][i]
　 2：然后依据递归式按矩阵链长递增的方式以此计算m[i][i+1]i=1,2,3.。。。
　 3：计算m[i][j]时，只要用到m[i][k]和m[k+1][j]*/ public static void MatrixChain( int []p, int [][]m, int [][]s) {
　int n=-1;
　for( int i=1;i<=n;i++)m[i][i]=0;//计算单一矩阵
　//依据递归式按矩阵链长递增的方式以此计算m[i][i+1]i=1,2,3.。。。
　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;k<j;k++)
　 {
　 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
　//更新m[i][j]，s[i][j]的值
　f if(t<m[i][j])
　{
　 m[i][j]=t;
　 s[i][j]=k;
　}
　 }
　 } } // 按算法MatrixChain计算出断点矩阵s指示的加括号方式
　public static void traceback( int [][]s, int i, int j)
　{
　 f if(i==j) return;
　 traceback (s,i,s[i][j]);
　 traceback (s,s[i][j]+1,j);
　 System. out .println(Multiply A+i+,+s[i][j]+and A+(s[i][j]+1)+,+j);
　} }
　
　试验结论
　 4 心得体会 算法设计真的须要逻辑思维，能得到结果挺快乐的。
　: 2: 最长公共子序列
　 算法设计思想 (1)
　设 序 列 X={x 1 ,x 2 ,,x m } 和 Y={y 1 ,y 2 ,,y n } 的 最 长 公 共 子 序 列 为Z={z 1 ,z 2 ,,z k } ，则 若 x m =y n ，则 z k =x m =y n ，且 Z k-1 是 X m-1 和 Y n-1 的最长公共子序列。
　若 x m ≠y n 且 z k ≠x m ，则 Z 是 X m-1 和 Y 的最长公共子序列。
　若 x m ≠y n 且 z k ≠y n ，则 Z 是 X 和 Y n-1 的最长公共子序列
　(2)建立递归关系：由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 c[i][j]记录序列和的最长公共子序列的长度。其中， X i ={x 1 ,x 2 ,,x i }；Y j ={y 1 ,y 2 ,,y j }。当 i=0 或 j=0 时，空序列是 X i 和 Y j 的最长公