3

我正在编写矩阵链乘法代码。首先,我从用户那里获取矩阵的数量及其维度,然后计算其顺序乘积,然后计算矩阵链顺序。
之后,矩阵根据矩阵链顺序相乘。
但是在改变矩阵尺寸时会发生以下错误。例如: 2 个 10*13 13*10 13*10 阶矩阵 2*3 3*2 2*2 3 个 10*13 13*10 10*13 7 个矩阵的矩阵订购12*12

矩阵不能只按 MCM 顺序执行产品的最后一步 5 个顺序矩阵 12*4 4*16 16*9 9*12 12*15 6 个顺序矩阵 19*19 和第 7 个矩阵 19*20 15 个顺序矩阵12*12

对于 3*3 3*4 4*11 11*13 13*7 7*12 的 6 个矩阵,没有完成顺序

    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    #include<time.h>
    int n,count;
    int **a;
    double ***b,***bz;
    struct stack
    {
         int *s;
         int top;
    };
    struct stack st,ss;
   void push(struct stack *stk,int item)
   {
         if(stk->top==(3*n-2)-1)
         printf("stack overflow");
         stk->top++;
         stk->s[stk->top]=item;
   }
   int pop(struct stack *stk)
   {
         stk->top--;
         return(stk->s[(stk->top)+1]);
   }
   void init_stack(struct stack *stk)
   {
         stk->top=-1;
         stk->s=(int *) malloc((3*n-2)*sizeof(int));
   }

   void print_opt_parens(int **s,int i,int j);    
   void matrix_chain_order(int p[],int length)
   {
         int n=length-1;
         int i,j,k,l,q,**mal,**sal;
         mal=(int **) malloc((n)*sizeof(int *));
         sal=(int **) malloc((n)*sizeof(int *));
         for(i=0;i<=n;i++)
                 mal[i]=(int *) malloc((n)*sizeof(int));
         for(i=0;i<=n;i++)
                 sal[i]=(int *) malloc(n*sizeof(int));
         for(i=0;i<=n;i++)
                 mal[i][i]=0;
         for(l=2;l<=n;l++)
         {
                 for(i=1;i<=n-l+1;i++)
                 {
                       j=i+l-1;
                       mal[i][j]=9999999;
                       for(k=i;k<=j-1;k++)
                       {
                              q=mal[i][k]+mal[k+1][j]+p[i-1]*p[k]*p[j];
                              if(q < mal[i][j])
                              {
                                    mal[i][j]=q;
                                    sal[i][j]=k;
                              }
                       }        
                 }
          }
          printf("\n Optimal Number of Operations = %d",mal[1][n]);
          printf("\nprinting optimal parenthesis : \n");
          print_opt_parens(sal,1,n);
          return;
     }
     void mul(int x,int y);
     void print_opt_parens(int **s,int i,int j)
     {    int x,y,zz;

          if(i==j){
          printf(" A%d ",i);
          push(&st,i);
     } 
     else
     {
          printf(" ( ");
          push(&st,-1);
          print_opt_parens(s,i,s[i][j]);
      print_opt_parens(s,s[i][j]+1,j);
      printf(" ) ");
      x=pop(&st);
      y=pop(&st);
    mul(x,y);
    zz=pop(&st);
    if(x<0&&y<0)
                push(&st,(x+y));
    else if(x>0&&y>0)
                push(&st,-(x+y));
             else        
                push(&st,(x*y));     
     }
    }
     void init_b(double ***b)
      {
         int i,j,k;
           bz=(double ***) malloc((2*n)*sizeof(double **));
           for(i=0;i<n;i++)
                bz[i]=(double **) malloc(n*sizeof(double *));
            for(i=0;i<n;i++)
                 for(j=0;j<n;j++)
                                 bz[i][j]=(double *) malloc(n*sizeof(double));
           for(i=0;i<n;i++)
                 for(j=0;j<n;j++)
                                 for(k=0;k<n;k++)
                           bz[i][j]k]=0.0;                                             
                   count=-1;
              }
          void mul(int x,int y)
          {
              FILE *fp4,*fp5,*fp6;
             double **z,**tx,**ty;
             int m,l,i,j,k,mm,ll,kk,nn;
              if(x<0)
                 {
             mm=pop(&ss);
             nn=pop(&ss);
             tx=(double **) malloc(nn*sizeof(double));
             for(i=0;i<nn;i++)
                              tx[i]=(double *) malloc(mm*sizeof(double));

             for(i=0;i<nn;i++)
                              for(j=0;j<mm;j++){
                                               tx[i][j]=bz[count][i][j];
                                               }
             count--;
              }
               else
              {           
             mm=a[0][x-1];
             nn=a[1][x-1];
             tx=(double **) malloc(mm*sizeof(double));
             for(i=0;i<mm;i++)
                              tx[i]=(double *) malloc(nn*sizeof(double));
             for(i=0;i<mm;i++)
                              for(j=0;j<nn;j++){
                                               tx[i][j]=b[x-1][i][j];
                                               }
             } 
              if(y<0) 
           {
             kk=pop(&ss);
             ll=pop(&ss);
             ty=(double **) malloc(kk*sizeof(double));
             for(i=0;i<kk;i++)
                              ty[i]=(double *) malloc(ll*sizeof(double));

             for(i=0;i<kk;i++)
                              for(j=0;j<ll;j++){
                                               ty[i][j]=bz[count][i][j];
                                              }

             count--;
             }
              else
               {
             kk=a[0][y-1];
             ll=a[1][y-1];
             ty=(double **) malloc(kk*sizeof(double));
             for(i=0;i<kk;i++)
                              ty[i]=(double *) malloc(ll*sizeof(double));
             for(i=0;i<kk;i++)
                              for(j=0;j<ll;j++){
                                               ty[i][j]=b[y-1][i][j];

                                               }

                      }
           count++;
             bz[count]=(double **) realloc(bz[count],mm*sizeof(double *));
             for(i=0;i<mm;i++)
             bz[count][i]=(double *) realloc(bz[count][i],ll*sizeof(double));    

            for(i=0;i<kk;i++)
               {
             for(j=0;j<nn;j++)
             {                  
                              bz[count][i][j]=0;
                              for(k=0;k<mm;k++)
                              {
                                                bz[count][i][j]+=ty[i][k]*tx[k][j];
                              }
             }
            }

              fp6=fopen("g.txt","w+");

           for(i=0;i<kk;i++)
             {
                  for(j=0;j<nn;j++)
                  {

                                   fprintf(fp6,"%lf\t",bz[0][i][j]);
                  }
                  fprintf(fp6,"\n");

            }
          push(&ss,nn);
           push(&ss,kk);

           }   

         int main()
         {
              FILE *fp1,*fp2,*fp3;
              int i,j,k,l,m,p,q;
              double **c,**t;
               int *pa;
               time_t ts;
             srand(time(&ts));
            // getting no of matrcies
            printf("\n Enter the Number or matrices :");
             scanf("%d",&n);
               // allocation of space to store matrices of varying rows and columns
             a=(int **) malloc(2*sizeof(int));
            init_b(bz);
           init_stack(&st);
           init_stack(&ss);
             for(i=0;i<2;i++)
                a[i]=(int *) malloc(n*sizeof(int));

              printf("\n Enter the rows and columns \n");
             for(j=0;j<n;j++)
                 for(i=0;i<2;i++)
                                scanf("%d",&a[i][j]);

            // verifying the multiplicability of the matrices
           for(i=0;i<n-1;i++)
                if(a[1][i]!=a[0][i+1])
                {               

                                printf("The matrices %d and %d cannot be multiplied",i,i+1);
                                getch();
                                exit(0);
                }
          // actual matrix allocation                                       
b=(double ***) malloc(n*sizeof(double **));
for(i=0;i<n;i++)
                b[i]=(double **) malloc(a[0][i]*sizeof(double *));
for(i=0;i<n;i<i++)
                  for(j=0;j<a[0][i];j++)
                                        b[i][j]=(double *) malloc(a[1][i]*sizeof(double));
// data entry
for(i=0;i<n;i++)
                for(j=0;j<a[0][i];j++)
                                      for(k=0;k<a[1][i];k++)
                                                            b[i][j][k]=(double)rand()/(double)RAND_MAX;
//file opening
fp1=fopen("b.txt","w");
fp2=fopen("c.txt","w");
//print data
for(i=0;i<n;i++)
{
                for(j=0;j<a[0][i];j++)
                {
                                      for(k=0;k<a[1][i];k++){
                                                            if(fp1!=NULL)
                                                                         fprintf(fp1,"%lf\t",b[i][j][k]);
                                                            printf("%lf\t",b[i][j][k]);
                                      }
                                      printf("\n");
                                      fprintf(fp1,"\n");
                }
                printf("\n");
                fprintf(fp1,"\n");
}

// allocating space for temp, and result variable
c=(double **) malloc(a[0][0]*sizeof(double));
for(i=0;i<a[0][0];i++)
                c[i]=(double *) malloc(a[1][1]*sizeof(double));
t=(double **) malloc(a[0][0]*sizeof(double));
for(i=0;i<a[0][0];i++)
                t[i]=(double *) malloc(a[1][0]*sizeof(double));
// assigning initial value of t
for(i=0;i<a[0][0];i++)
                for(j=0;j<a[1][0];j++)
                                      t[i][j]=(double)b[0][i][j];
// sequential matrix multiplication      
for(i=1;i<n;i++)
{
                 c=(double **) realloc(c,a[0][0]*sizeof(double));
                 for(m=0;m<a[0][0];m++)
                 {
                                       c[m]=(double *) realloc(c[m],a[1][i]*sizeof(double));}
                for(j=0;j<a[0][0];j++)
                {
                                      for(k=0;k<a[1][i];k++)
                                      {
                                                            c[j][k]=0.0;
                                                            for(l=0;l<a[0][i];l++)
                                                            {                     
                                                                                  c[j][k]+=(double)t[j][l]*(double)b[i][l][k];
                                                            }
                                      }
                }
                t=(double **) realloc(t, a[0][0]*sizeof(double));
                for(m=0;m<a[0][i-1];m++)
                                       t[m]=(double *) realloc(t[m],a[1][i]*sizeof(double));
                for(m=0;m<a[0][0];m++)
                                        for(p=0;p<a[1][i];p++)
                                                              t[m][p]=c[m][p];
}
free(c);
free(t);
// print the result
for(i=0;i<a[0][0];i++)
{
                      for(j=0;j<a[1][n-1];j++){
                                              if(fp2!=NULL)
                                                           fprintf(fp2,"%lf\t",c[i][j]); 
                                              printf("%lf\t",c[i][j]);
                      }
                      printf("\n");
                      fprintf(fp2,"\n");
}
// extract the no of rows and columns
pa=(int *) malloc((n+1)*sizeof(int));
pa[0]=a[0][0];
for(i=1;i<n+1;i++)
                  pa[i]=a[1][i-1];
//Matrix Chain OPerations and Order
matrix_chain_order(pa,n+1);
fclose(fp1);
fclose(fp2);         
getch();
return 0;
 }                
4

0 回答 0