实验三动态规划.doc

算法分析与设计实验报告

学号
1207132229
姓名
吕联栋
班级
软服2班
上课地点
教师
陈思
上课时间
实验三动态规划
1. 实验目的
;
。
2. 实验环境
Eclipse
Window XP
3. 实验内容
矩阵连乘问题
最长公共子序列问题
0-1背包问题
4. 教师批改意见
签字:
日期:
成绩
实验报告细表
1矩阵连乘问题
算法设计思想
给定n个矩阵,其中A1与Ai+1是可乘的i=1,2...n。考察这n个矩阵的连乘积:A1a2A3..,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。
程序源码
package suanfa;
import ;
public class shiyansan1
{
public static void main(String[] args)
{
Scanner scan=new Scanner();
("输入矩阵个数:");
int n = ();//矩阵的个数
int p[]=new int[100];
int x[]=new int[100];
int y[]=new int[100];
for (int i=0;i<n;i++)
{
("第"+(i+1)+"个矩阵行数: ");
x[i]=();
("第"+(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];

//调用函数
matrixChain(p,m,s);
traceback(s,1,n);
("矩阵连乘的最少数乘量为:"+m[1][n]);//输出最少数乘量
}
//主要的方法,矩阵连乘的方法
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]赋值为 0

//控制矩阵的链长度r=2~n
for(int r=2