利用动态规划算法实现矩阵连乘

#include<iostream> using namespace std; void matrixChain(int *p,int n,int **m,int **s); void traceback(int i,int j,int **s); void print_matrix(int m,int n,int **matrix); void init_matrix(int **m,int size); void del_matrix(int **m,int size); int main(){ int row[10]; int n; memset(row,0,sizeof(row)); int **mulitp,**pos; int i,j; cout<<"input the amount of matrixes:"; cin>>n; for(i=0;i<n;i++){ cout<<"input row of matrixe "<<i<<":"; cin>>row[i]; cout<<endl; } int size=n+1; /*-----------指针初始化------------------*/ mulitp=(int **)malloc((size)*sizeof(int *)); pos=(int **)malloc((size)*sizeof(int *)); for(i=0;i<size;i++){ mulitp[i]=(int *)malloc((size)*sizeof(int)); pos[i]=(int *)malloc((size)*sizeof(int)); } for(i=0;i<size;i++){ for(j=0;j<size;j++){ mulitp[i][j]=0; pos[i][j]=0; } cout<<endl; } cout<<endl; print_matrix(n,n,mulitp); // init_matrix(pos,n+1); //!!!二维指针传参函数返回时，指针pos并没有改变?无法指针初始化 matrixChain(row,n,mulitp,pos); // print_matrix(n,n,pos); cout<<endl; //del_matrix(mulitp,n+1); // del_matrix(pos,n+1); /*---------------释放空间-----------------*/ int d; for(d=0;d<size;d++){ free(mulitp[d]); free(pos[d]); } free(mulitp); free(pos); } void init_matrix(int **m,int size){ int i,j; m=(int **)malloc((size)*sizeof(int *)); for(i=0;i<size;i++) m[i]=(int *)malloc((size)*sizeof(int)); for(i=0;i<size;i++){ for(j=0;j<size;j++){ m[i][j]=0; cout<<m[i][j]<<" "; } cout<<endl; } } void del_matrix(int **m,int size){ int d; for(d=0;d<size;d++) free(m[d]); free(m); } void print_matrix(int m,int n,int **matrix){ for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++) cout<<matrix[i][j]<<" "; cout<<endl; } } void traceback(int i,int j,int **s){ /* if(i==j) return; traceback(i,s[i][j],s); traceback(s[i][j]+1,j,s); cout<<"M"<<i<<","<<s[i][j]; cout<<"and M"<<s[i][j]+1<<","<<j<<endl; */ if(i==j) cout<<"a"<<i; else{ cout<<"("; traceback(i,s[i][j],s); traceback(s[i][j]+1,j,s); cout<<")"; } } void matrixChain(int *p,int n,int **m,int **s){//p为行数n为矩阵的个数 n--;//!!!!!!!!!!!!!!!!!!!!!!!!!!! for(int q=1;q<=n;q++) m[q][q]=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; } } } cout<<"m:"<<endl; print_matrix(n,n,m); cout<<"s:"<<endl; print_matrix(n,n,s); traceback(1,n,s); } /*-------example-------- n=7; row:6 col:1 */