动态规划实现矩阵连乘-C++.doc

#include<iostream.h>
#include<math.h>
#include <time.h>
#include "windows.h"
#define M 100
#define N 50
int cou=0;
int v[M];
struct Arry //存放一次相乘后的数组
{
int**a;
};

struct Arryt
{
int row;
int cowl;
int number;
int**p;
};
int Common[N-1][N-1];
void MartrixChain(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][i]+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;} //记录最优的断开位置

}
}
}

void Traceback(int i,int j,int **s)//返回一共记录的下个数

{
//s[i][j]记录了断开的位置，即计算A[i:j]的加括号方式为

//(A[i:s[i][j]])*(A[s[i][j]+1:j])
//int k=0;
if(i==j)return ;

Traceback(i,s[i][j],s);//递归打印A[i:s[i][j]]的加括号方式

Traceback(s[i][j]+1,j,s);//递归打印A[s[i][j]+1:j]的加括号方式

// cout<<"A"<<i<<"和A"<<(s[i][j]+1)<<"相乘"<<endl;
cout<<"multiply A"<<i<<","<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;
v[4*cou]=i; //记录乘法下标11,22,23等
v[4*cou+1]=s[i][j];
v[4*cou+2]=s[i][j]+1;
v[4*cou+3]=j;
cou=cou+1;
// return k;
}

//----------------------------------------
void selectMultiply(Arry *A,int v[],int c,int*p,Arryt *temp)
{
int k;
int s;
int t;
int m;
int j,n,l,x,y;
//k=c;
// Arryt *temp=new Arryt[c];
for(int i=0;i<c;i++)
{
if(v[i*4]==v[i*4+1])
{
if(v[i*4+2]==v[i*4+3])
{
k=v[i*4]; //kk下标为11、22,33类型
s=v[i*4+2]; //ss下标为11、22类型

temp[i].p=new int*[p[k-1]];
for(j=0;j<p[k-1];j++)
temp[i].p[j]=new int[p[s]];
temp[i].row=p[k-1];
temp[i].cowl=p[s];
temp[i].number=10*k+s;
for(j=0;j<p[k-1];j++)
for(n=0;n<p[s];n++)
{
int sum=0;
for(l=0;l<p[s-1];l++)
sum=sum+A[k-1].a[j][l]*A[s-1].a[l][n];
temp[i].p[j][n]=sum
}

}
else
{
k=v[i*4]; //kk下标为11、22类型

s=v[i*4+2]; //}
//}st下标23、35类型
t=v[i*4+3]; //}
for(j=0;j<i;j++)
if(temp[j].number=10*s+t) x=j;

temp[i].p=new int*[p[k-1]];
for(j=0;j<p[k-1];j++)
temp[i].p[j]=new int[temp[x].cowl];

temp[i].row=p[k-1];
temp[i].cowl=temp[x].cowl;
temp[i].number=10*k+t;

for(j=0;j<p[k-1];j++)
for(n=0;n<temp[x].cowl;n++)
{
int sum=0;
for(l=0;l<p[k];l++)
sum=sum+A[k-1].a[j][l]*temp[x].p[l][n];
temp[i].p[j][n]=sum;
}
}
}
else
{
if(v[i*4+2]==v[i*4+3])
{
k=v[i*4]; //}
//}ks下标23、35类型
s=v[i*4+1];//}
t=v[i*4+2];//tt下标为11、22类型
for(j=0;j<i;j++)
if(temp[j].number=10*k+s) x=j;
temp[i].p=new int*[temp[x].row];
for(j=0;j<temp[x].row;j++)
temp[i].p[j]=new int[p[t]];
temp[i].row=temp[x].row;
temp[i].cowl=p[t];
temp[i].number=10*k+t;
for(j=0;j<temp[x].row;j++)
for(n=0;n<p[t];n++)
{
int sum=0;
for(l=0;l<temp[x].cowl;l++)
sum=sum+temp[x].p[j][l]*A[t-1].a[l][n];
temp[i].p[j][n]=sum;
}
}
else
{
k=v[i*4]; //}ks下标23、35类型
s=v[i*4+1];//}
t=v[i*4+2];//tm下标23、35类型
m=v[i*4+3];
for(j=0;j<i;j++)
{
if(temp[j].number=10*k+s) x=j;
if(temp[j].number=10*t+m) y=j;
}
temp[i].p=new int*[temp[x].row];
for(j=0;j<temp[x].row;j++)
temp[i].p[j]=new int[temp[y].cowl];
temp[i].row=temp[x].row;
temp[i].cowl=temp[y].cowl;
temp[i].number=10*k+m;
for(j=0;j<temp[x].row;j++)
for(n=0;n<temp[y].cowl;n++)
{
int sum=0;
for(l=0;l<temp[x].cowl;l++)
sum=sum+temp[x].p[j][l]*temp[y].p[l][n];
temp[i].p[j][n]=sum;
}
}
}
}
}
void outputselect(int c,int n,Arryt *temp)
{
int i,j;
int s=10+n;
for(i=0;i<temp[c-1].row;i++)
{
for(j=0;j<temp[c-1].cowl;j++)
cout<<temp[c-1].p[i][j]<<" ";
cout<<endl;
}
}
void main()
{
int n,i,j;//连乘的数组的个数
cout<<"输入连乘的数组的个数：";
cin>>n;
int *p;//维数
int **m; //保存最优值数组
int**s;
//分配空间
p=new int[n+1]; //分配矩阵维数数组空间
cout<<"请输入第一个矩阵的行列数以及其他矩阵的列数："<<endl;
for (i=0;i<=n;i++)
cin>>p[i];
m=new int*[n+1]; //分配空间
for(i=0;i<=n ; i++)
m[i]=new int[n+1];
s=new int*[n+1]; //分配空间
for (i=0;i<=n ; i++)
s[i]=new int[n+1];
s=new int*[10]; //分配空间
for (i=0;i<=10 ; i++)
s[i]=new int[10];
for(i=0;i<n;i++)
cout<<"---矩阵A"<<i+1<<":"<<p[i]<<"x"<<p[i+1]<<endl;
//给数组分配空间并且给数组随机赋值
Arry *A=new Arry[n];
for(i=0;i<n;i++)
{
A[i].a=new int*[p[i]];
for(j=0;j<p[i];j++)
A[i].a[j]=new int[p[i+1]];
for(int k=0;k<p[i];k++)
for(j=0;j<p[i+1];j++)
{
//srand(time(0));
A[i].a[k][j]=rand()%6;
}
}
MartrixChain(p,n,m,s);
cout<<"\n----动态规划的路径"<<endl;
Traceback(1,n,s);
Arryt *temp=new Arryt[n];
selectMultiply(A,v,cou,p,temp);
cout<<"\n----输出最后的矩阵"<<endl;
outputselect(cou,n,temp);
for(i=0;i<n+1 ; i++) delete[] m[i];
delete[] m; //释放二维数组空间
delete[] p; //释放矩阵维数数组空间
}