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

#include#include#include #include windows.h#define M 100#define N 50int cou=0;int vM;struct Arry /存放一次相乘后的数组int*a;struct Arrytint row; int cowl;int number;int*p;int CommonN-1N-1;void MartrixChain(int *p,int n,int *m,int*s) for(int i=1;i=n;i+) mii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mii+mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi-1*pk*pj;/选择最小的if (tmij) mij=t;sij=k; /记录最优的断开位置void Traceback(int i,int j,int *s)/返回一共记录的下个数 /sij记录了断开的位置，即计算Ai:j的加括号方式为 /(Ai:sij)*(Asij+1:j) /int k=0; if(i=j)return ; Traceback(i,sij,s);/递归打印Ai:sij的加括号方式 Traceback(sij+1,j,s);/递归打印Asij+1:j的加括号方式 / coutAi和A(sij+1)相乘endl; coutmultiply Ai,sij; coutand A(sij+1),jendl; v4*cou=i; /记录乘法下标11,22,23等 v4*cou+1=sij; v4*cou+2=sij+1; v4*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 Arrytc;for(int i=0;ic;i+)if(vi*4=vi*4+1)if(vi*4+2=vi*4+3)k=vi*4; /kk下标为11、22,33类型s=vi*4+2; /ss下标为11、22类型tempi.p=new int*pk-1;for(j=0;jpk-1;j+)tempi.pj=new intps;tempi.row=pk-1;tempi.cowl=ps;tempi.number=10*k+s;for(j=0;jpk-1;j+)for(n=0;nps;n+)int sum=0;for(l=0;lps-1;l+) sum=sum+Ak-1.ajl*As-1.aln;tempi.pjn=sumelsek=vi*4; /kk下标为11、22类型s=vi*4+2; / /st下标23、35类型 t=vi*4+3; / for(j=0;ji;j+)if(tempj.number=10*s+t) x=j;tempi.p=new int*pk-1;for(j=0;jpk-1;j+)tempi.pj=new inttempx.cowl; tempi.row=pk-1;tempi.cowl=tempx.cowl;tempi.number=10*k+t; for(j=0;jpk-1;j+)for(n=0;ntempx.cowl;n+)int sum=0;for(l=0;lpk;l+)sum=sum+Ak-1.ajl*tempx.pln;tempi.pjn=sum;elseif(vi*4+2=vi*4+3)k=vi*4; / /ks下标23、35类型 s=vi*4+1;/t=vi*4+2;/tt下标为11、22类型 for(j=0;ji;j+)if(tempj.number=10*k+s) x=j; tempi.p=new int*tempx.row;for(j=0;jtempx.row;j+)tempi.pj=new intpt;tempi.row=tempx.row;tempi.cowl=pt;tempi.number=10*k+t;for(j=0;jtempx.row;j+)for(n=0;npt;n+)int sum=0;for(l=0;ltempx.cowl;l+)sum=sum+tempx.pjl*At-1.aln;tempi.pjn=sum;elsek=vi*4; /ks下标23、35类型 s=vi*4+1;/t=vi*4+2;/tm下标23、35类型m=vi*4+3; for(j=0;ji;j+) if(tempj.number=10*k+s) x=j;if(tempj.number=10*t+m) y=j;tempi.p=new int*tempx.row;for(j=0;jtempx.row;j+)tempi.pj=new inttempy.cowl; tempi.row=tempx.row;tempi.cowl=tempy.cowl;tempi.number=10*k+m;for(j=0;jtempx.row;j+)for(n=0;ntempy.cowl;n+)int sum=0;for(l=0;ltempx.cowl;l+)sum=sum+tempx.pjl*tempy.pln;tempi.pjn=sum; void outputselect(int c,int n,Arryt *temp)int i,j;int s=10+n;for(i=0;itempc-1.row;i+)for(j=0;jtempc-1.cowl;j+)couttempc-1.pij ;coutendl;void main() int n,i,j;/连乘的数组的个数coutn; int *p;/维数int *m; /保存最优值数组int*s;/分配空间p=new intn+1; /分配矩阵维数数组空间 cout请输入第一个矩阵的行列数以及其他矩阵的列数：endl; for (i=0;ipi; m=new int*n+1; /分配空间 for(i=0;i=n ; i+) mi=new intn+1; s=new int*n+1; /分配空间 for (i=0;i=n ; i+) si=new intn+1; s=new int*10; /分配空间 for (i=0;i=10 ; i+) si=new int10; for(i=0;in;i+) cout-矩阵Ai+1:pixpi+1endl; /给数组分配空间并且给数组随机赋值Arry *A=new Arryn; for(i=0;in;i+) Ai.a=new int*pi; for(j=0;jpi;j+) Ai.aj=new intpi+1; for(int k=0;kpi;k+) for(j=0;jpi+1;j+) /srand(time(0); Ai.akj=rand()%6; MartrixChain(p,n,m,s); coutn-动态规划的路径endl; Traceback(1,n,s); Arryt *temp=new Arrytn; selectMultiply(A,v,cou,p,temp); coutn-输出最后的矩阵endl; outputselect(cou,n,temp); for(i=0;in+1 ; i+) delete mi; delete m; /释放二维数组空间 delete p; /释放矩阵维数数组空间