矩阵链乘法实现（算法导论 P197）
#include<stdio.h>
#include<stdlib.h>
#define MAX 65536
void printMatrix(int *s,int len,int i,int j)
{
if(i==j)
printf("A%d",i+1);
else{
printf("(");
printMatrix(s,len,i,s[i*len+j]);
printMatrix(s,len,s[i*len+j]+1,j);
printf(")");
}
}
void matrixOrder(int p[][2],int len)
{
int *m,*s;
int i,j,k;
if((m=malloc(len*len*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
if((s=malloc(len*len*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
for(i=0;i<len;i++)
m[i*len+i]=0;
for(i=1;i<len;i++)
{
for(j=0;j+i<len;j++)
{
m[j*len+j+i]=MAX;
for(k=j;k<j+i;k++)
{
if((p[j][0]*p[k][1]*p[i+j][1]+m[j*len+k]+m[(k+1)*len+i+j])<m[j*len+j+i])
{
m[j*len+j+i]=p[j][0]*p[k][1]*p[i+j][1]+m[j*len+k]+m[(k+1)*len+i+j];
s[j*len+j+i]=k;
}
}
}
}
printf("##### then matrix m\n");
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
printf("%d ",m[i*len+j]);
}
printf("\n");
}
printf("##### the matrix s\n");
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
printf("%d ",s[i*len+j]);
}
printf("\n");
}
printMatrix(s,len,0,5);
printf("\n");
}
int main()
{
int p[6][2]={{30,35},{35,15},{15,5},{5,10},{10,20},{20,25}};
matrixOrder(p,6);
}