矩阵连乘.cpp

算法设计与分析的经典程序

#include <iostream.h>
#include <stdio.h>
#define max  10
void Matrix(int *p,int n,int m[max][max],int s[max][max])
{int i,j,k,r,t;
for ( i=1;i<=n;i++) m[i][i]=0;
    for ( r=2;r<=n;r++)
	for( i=1;i<=n-r+1;i++)
	{ j=i+r-1;
	m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//p[i-1]*p[i]*p[j]
	s[i][j] = i;
	for ( k=i+1;k<j;k++){			                  
	 t=m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j];
	if(t<m[i][j]) 
	{m[i][j]=t;s[i][j]=k;}
		}}
	for ( i=1;i<=n;i++) 
	{printf("\n");
     for ( r=1;r<=n;r++)
		printf("%5d",s[i][r]);
	 }
}
void Trace(int i,int j,int s[max][max])
{
 if (i==j) return;  Trace(i,s[i][j],s);
 Trace(s[i][j]+1,j,s);
 printf("Multiply A%d,%d",i,s[i][j]);
 printf("and A%d,%d\n",s[i][j]+1,j);
}

main()
{int m[max][max],s[max][max],n=6,i,r,p[max]={30,35,15,5,10,20,25};
for ( i=1;i<=n;i++) 
     for ( r=1;r<=n;r++)
	 s[i][r] = 0;
Matrix(p,n,m,s);
Trace(1,n,s);   
}