矩阵连乘问题算式输出

元始天尊

对于矩阵连乘的最优方式，书上只给了最小乘法次数，也就是最终结果，而具体怎么乘要写成表达式，把括号加到矩阵之间还是要动动脑筋的

1. #include <iostream>
   
2. #include <iomanip>
   
3. #include <time.h>
   
4. using namespace std;
   
5. void addbrace(short* bracearr,int* posmatrix,int begin,int end,int size)
   
6. {
   
7.         if(begin == end)
   
8.                 return;
   
9.         //首尾括号
   
10.         bracearr[2*begin]++;
    
11.         bracearr[2*end+1]++;
    
12.         int mid=posmatrix[begin*size+end];
    
13.         addbrace(bracearr,posmatrix,begin,mid,size);
    
14.         addbrace(bracearr,posmatrix,mid+1,end,size);
    
15. }
    
16. void func(int* arr,int size)
    
17. {
    
18.         int* m=new int[size*size];
    
19.         int* s=new int[size*size];
    
20.         int i,j,k;
    
21.         for(i=0;i<size*size;i++)
    
22.         {
    
23.                 m[i]=0;
    
24.                 s[i]=0;
    
25.         }
    
26.         for(i=0;i<size-1;i++)
    
27.         {
    
28.                 for(j=0;j<size-i-1;j++)
    
29.                 {//[j][i+j+1]
    
30.                         k=j;
    
31.                         int minv,minpos=j;
    
32.                         minv=arr[j]*arr[k+1]*arr[i+j+2]+m[j*size+k]+m[(k+1)*size+i+j+1];
    
33.                         for(k++;k<i+j+1;k++)
    
34.                         {
    
35.                                 int value=arr[j]*arr[k+1]*arr[i+j+2]+m[j*size+k]+m[(k+1)*size+i+j+1];
    
36.                                 if(value<minv)
    
37.                                 {
    
38.                                         minv=value;
    
39.                                         minpos=k;
    
40.                                 }
    
41.                         }
    
42.                         m[j*size+i+j+1]=minv;
    
43.                         s[j*size+i+j+1]=minpos;
    
44.                 }
    
45.         }
    
46.         cout<<"m:"<<endl;
    
47.         for(i=0;i<size;i++)
    
48.         {
    
49.                 for(j=0;j<size;j++)
    
50.                 {
    
51.                         cout<<setw(8);
    
52.                         cout<<m[i*size+j]<<" ";
    
53.                 }
    
54.                 cout<<endl;
    
55.         }
    
56.         cout<<endl<<"s:"<<endl;
    
57.        
    
58.         for(i=0;i<size;i++)
    
59.         {
    
60.                 for(j=0;j<size;j++)
    
61.                 {
    
62.                         cout<<s[i*size+j]<<" ";
    
63.                 }
    
64.                 cout<<endl;
    
65.         }
    
66.         cout<<endl;
    
67.         short* bracearr=new short[2*size];//left right
    
68.         memset(bracearr,0,2*size*sizeof(short));
    
69.         addbrace(bracearr,s,0,size-1,size);
    
70.         for(i=0;i<size;i++)
    
71.         {
    
72.                 while(bracearr[2*i]--)
    
73.                         cout<<"(";
    
74.                 cout<<"A"<<i+1;
    
75.                 while(bracearr[2*i+1]--)
    
76.                         cout<<")";
    
77.                 if(i != size-1)
    
78.                         cout<<"*";
    
79.         }
    
80.         cout<<endl;
    
81.         delete []bracearr;
    
82.         delete []m;
    
83.         delete []s;
    
84. }
    
85. int main(int argc,char* argv[])
    
86. {
    
87.         srand(time(NULL));
    
88.         int size=rand()%20;
    
89.         int* arr=new int[size];
    
90.         for(int i=0;i<size;i++)
    
91.                 arr[i]=rand()%50+1;
    
92.         func(arr,size-1);
    
93.         return 0;
    
94. }

复制代码

alwaysFindFood

终于不用喂B了...