矩阵连乘问题算式输出
对于矩阵连乘的最优方式，书上只给了最小乘法次数，也就是最终结果，而具体怎么乘要写成表达式，把括号加到矩阵之间还是要动动脑筋的#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
void addbrace(short* bracearr,int* posmatrix,int begin,int end,int size)
{
if(begin == end)
return;
//首尾括号
bracearr++;
bracearr++;
int mid=posmatrix;
addbrace(bracearr,posmatrix,begin,mid,size);
addbrace(bracearr,posmatrix,mid+1,end,size);
}
void func(int* arr,int size)
{
int* m=new int;
int* s=new int;
int i,j,k;
for(i=0;i<size*size;i++)
{
m=0;
s=0;
}
for(i=0;i<size-1;i++)
{
for(j=0;j<size-i-1;j++)
{//
k=j;
int minv,minpos=j;
minv=arr*arr*arr+m+m[(k+1)*size+i+j+1];
for(k++;k<i+j+1;k++)
{
int value=arr*arr*arr+m+m[(k+1)*size+i+j+1];
if(value<minv)
{
minv=value;
minpos=k;
}
}
m=minv;
s=minpos;
}
}
cout<<"m:"<<endl;
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
cout<<setw(8);
cout<<m<<" ";
}
cout<<endl;
}
cout<<endl<<"s:"<<endl;
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
cout<<s<<" ";
}
cout<<endl;
}
cout<<endl;
short* bracearr=new short;//left right
memset(bracearr,0,2*size*sizeof(short));
addbrace(bracearr,s,0,size-1,size);
for(i=0;i<size;i++)
{
while(bracearr--)
cout<<"(";
cout<<"A"<<i+1;
while(bracearr--)
cout<<")";
if(i != size-1)
cout<<"*";
}
cout<<endl;
delete []bracearr;
delete []m;
delete []s;
}
int main(int argc,char* argv[])
{
srand(time(NULL));
int size=rand()%20;
int* arr=new int;
for(int i=0;i<size;i++)
arr=rand()%50+1;
func(arr,size-1);
return 0;
} 终于不用喂B了...
页:
[1]