Matrix-Chain-Multiply Source-Code

January 26th, 2008

Filed under: Algorithms — Unggul_USA @ 2:12 pm — View blog reactions

#include
#define MAXArray 9
#define MAXMultiplication 4199999999
int num;
void printout(unsigned long s[][MAXArray],int i,int j)
{
if(i==j)
printf(”A%d”,num++);
else
{
printf(”(”);
printout (s,i,s[i][j]);
printf(” x “);
printout (s,s[i][j]+1,j);
printf(”)”);
}
}
void matrix_chain_order(int *p,int n)
{
unsigned long m[MAXArray][MAXArray] = {0};
unsigned long s[MAXArray][MAXArray] = {0};
unsigned int q;
int h,j,i,k;
for(h = 2; h <= n ;h++)
{
for(i = 1 ; i <= n - h +1 ; i++)
{
j = i + h -1;
m[i][j] = MAXMultiplication;
for(k=i ; k < j ; k++)
{
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(q < m[i][j])
{
m[i][j] = q;
s[i][j] = k;
}
}
}
}
num = 1;
printout (s,1,n);
}

main(void)
{
int n;
int p[MAXArray]={0};
int i;
while(scanf(”%d”,&n),n)
{
for(i=1;i<=n;i++)
scanf(”%d %d”,&p[i-1],&p[i]);
matrix_chain_order(p,n);
putchar(’\n’);
}
return 0;
}