矩陣鍊乘法C++實作

#include<iostream>

#define MAX_SIZE 100

using namespace std;

int num;

int size[MAX_SIZE],s[MAX_SIZE][MAX_SIZE];

int ji[MAX_SIZE][MAX_SIZE];

void opt_matrix_muln(int size[])

{

int n=num;

int i,j,k,w,q;

for(i=1;i<=n;i++)

s[i][i]=0;

for(w=1;w<=n-1;w++)//j-i=w

{

for(i=1;i<=n-w;i++)

{

j=w+i;

s[i][j]=100000000;//對于不同的矩陣數可以自行設定大小

for(k=i;k<=j-1;k++)

{

q=s[i][k]+s[k+1][j]+size[i-1]*size[k]*size[j];

if(q<s[i][j])

{

s[i][j]=q;

ji[i][j]=k;//記錄k的值

}

}

}

}

}

void display(int k,int i,int j)//k代表最優的中間值

{

if(i==j)

{

printf("M%d",i);

}

else

{

printf("(");

display(ji[i][k],i,k);

printf("*");

display(ji[k+1][j],k+1,j);

printf(")");

}

}

int main()

{

int i;

printf("請輸入相乘矩陣的個數( < 100):");

cin>>num;

printf("請輸入矩陣的行數與列數:/n");

for(i=0;i<=num;i++)

cin>>size[i];

opt_matrix_muln(size);

printf("實作矩陣相乘最少的标量積為: %d",s[1][num]);

printf("/n矩陣相乘順序為:/n");

display(ji[1][num],1,num);

printf("/n");

getchar();

return 0;

}