动态规划求解矩阵连乘问题JAVA实现.doc

动态规划求解矩阵连乘问题JAVA实现
import java.io.*;

//输入类

class Testio
{

public static double readDouble()
{
try
{
return Double.valueOf(readString().trim()).doubleValue();}
catch(NumberFormatException ne)
{
System.err.println("Console.readDouble:Not a double...");
System.exit(-1);
return 0.0;
}
}
public static int readInt()
{
try{return Integer.valueOf(readString().trim()).intValue();}
catch(NumberFormatException ne){
System.err.println("Console.readInt:Not an integer....");
System.exit(-1);
return -1;
}
}
public static String readString()
{
String string=new String();

BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
try{
string=in.readLine();}
catch(IOException e)
{
System.out.println("Console.readInt:Not an integer....");
System.exit(-1);
}return string;
}
}

//
public class Juzhen
{
public static void Matrix(int p[],int n,int m[][],int s[][])
{
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;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}

//
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
System.out.print(m[i][j]+"\t");
}
System.out.println();
}
System.out.println();
System.out.println();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
System.out.print(s[i][j]+"\t");
}
System.out.println();
}
}

public static void TrackBack(int i,int j,int s[][])
{
if(i==j)
{
System.out.print("A"+i);
return ;
}
if(i<s[i][j])
System.out.print("(");
TrackBack(i,s[i][j],s);
if(i<s[i][j])
System.out.print(")");
if(s[i][j]+1<j)
System.out.print("(");
TrackBack(s[i][j]+1,j,s);
if(s[i][j]+1<j)
System.out.print(")");
//
//cout<<"(A"<<i<<"*A"<<s[i][j];
//cout<<")"<<"A"<<(s[i][j]+1)<<"*A"<<j<<endl;
}

public static void main(String[] args)
{
System.out.println();
System.out.println("￥￥￥￥￥￥￥￥欢迎使用矩阵连乘问题￥￥￥￥￥￥￥￥￥￥");
System.out.println("By meter！");
System.out.println("请输入矩阵个数：");
int n=Testio.readInt();
System.out.println("请输入"+n+"个矩阵的维数：");
System.out.println("(@温馨提示@：维数的个数应为："+(n+1)+")");
int p[]=new int[100];
for(int i=0;i<=n;i++)
{
p[i]=Testio.readInt();
// System.out.println(p[i]);
}
System.out.println();
int m[][]=new int[100][100];
int s[][]=new int[100][100];
Matrix(p,n,m,s);
TrackBack(1,n,s);

}
}