动态规划—整数划分和矩阵连乘的java程序.doc

实验报告4
课程 数据结构与算法 实验名称 动态规划 第 1 页
班级 11计本 学号 105032011130 姓名 刘川葆
实验日期：2013年3月25日 报告退发 (订正 、 重做)
一、实验目的
掌握动态规划策略的原理和应用。
二、实验环境
1、微型计算机一台
2、WINDOWS操作系统，Java SDK，Eclipse开发环境
三、实验内容
必做题：
1. 编写程序采用动态规划策略求解整数划分问题。
要求：输出给定整数n的划分个数。
2. 编写程序求解矩阵连乘问题，要求输出最优解。
要求：输出矩阵连乘最少需要的数乘次数，同时输出最优运算顺序，以A、B、C、D四个矩阵连乘为例，输出最优解格式为：(A(B*C)*D)
四、实验步骤和结果
(附上代码和程序运行结果截图)
1.动态规划—整数划分
import java.util.Scanner;
public class ZSHF {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//键盘输入n
Scanner in=new Scanner(System.in);
System.out.println("input n:");
int n=in.nextInt();
//建立b数组存放动态规划结果
int b[][]=new int[n+1][n+1];//由于0行0列不用，故要加一
//进入划分函数
h_f_d(b);
//输出最后结果
System.out.println(b[n][n]);
}

private static void h_f_d(int[][] b) {
// TODO Auto-generated method stub
//初始化数组，对任何数不大于1的划分进行赋值
for(int i=1;i<b.length;i++){
b[i][1]=1;
}
//对不大于其他值的划分的递推
for(int k=2;k<b.length;k++){//逐层深入，递归
for(int l=k;l<b.length;l++){
if(k==l)//应用书上的递推式组织函数
b[l][k]=1+b[l][k-1];
else if(l>k){
if(l-k>k)/*由于数组的另一半并没有赋值，故要对l-k?k的情况进行分类*/
b[l][k]=b[l][k-1]+b[l-k][k];
else
b[l][k]=b[l][k-1]+b[l-k][l-k];
}
}
}
}

}

2动态规划—矩阵连乘

public class JZLC {

/**
* @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];//记录最佳分割位置
matrixChain(b,p,s);
traceback(s,1,p.length-1);
System.out.println();
System.out.println(b[1][p.length-1]);
}

private static void traceback(int[][] s, int i, int j) {
// TODO Auto-generated method stub
//观察解的格式，发现如果只有单个的A，那么只要输出Ai，前后会有括号
//如果是连续的A，则规律是i+1=j，那么此时不要使用括号
//在分割点左边是用“（”，在分割点右边是用“）”,此时采用递归去求解使用括号的位置
if(i==j) System.out.print("A"+i);
else if(i+1==j) System.out.print("(A"+i+"*"+"A"+j+")");
else{
System.out.print("(");
traceback(s,i,s[i][j]);
traceback(s,s[i][j]+1,j);
System.out.print(")");
}
}

private static void matrixChain(int[][] b, int[] p, int[][] s) {
// TODO Auto-generated method stub
int n=p.length-1;
//初始化对角线的位置为0；
for(int i=1;i<=n;i++)
b[i][i]=0;
//开始进入
for(int r=2;r<=n;r++)//从2列开始确定对角线以外的值
for(int i=1;i<=n-r+1;i++){
int j=i+r-1;
//当k等于i时
b[i][j]=b[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
//当k不等于i时
int t=0;
for(int k=i+1;k<j;k++){
t=b[i][k]+b[k+1][j]+p[i-1]*p[k]*p[j];
if(t<b[i][j]){
b[i][j]=t;
s[i][j]=k;
}
}
}
}

}

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