matrix.cpp

矩阵连乘的源码

#include "iostream.h"
#include<conio.h>
int MatrixChain(int *p,int n,int **m,int **s)
{
   for(int i=1;i<=n;i++)
   m[i][i]=0;
   for(int r=2;r<=n;r++)
   for( i=1;i<=n-r+1;i++)
  {
   int j=i+r-1;
   m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
   s[i][j]=i;
   for(int k=i+1;k<j;k++)
  {
   int 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;
   }
  }
 }
return m[1][n];
}

void Traceback(int i,int j,int **s)// 递归
{ 
	
	if(i==j)return;
	Traceback(i,s[i][j],s);
	Traceback(s[i][j]+1,j,s);
	cout<<"A["<<i<<","<<s[i][j]<<"]"<<"*A["<<s[i][j]+1<<","<<j<<"]"<<endl;
	
}

void main()
{

    int n,*p;
	int j=1;
	cout<<"请输入矩阵的个数:"<<endl;
	cin>>n;
	p=new int[n+1];
	cout<<"请输入第一个矩阵的行数:"<<endl;
     cin>>p[0];
	 cout<<"第"<<j<<"个矩阵是"<<endl;
	 cout<<p[0]<<"*";
	 cin>>p[1];
	 //cout<<endl;
	 for(int i=2;i<n+1;i++)
	 {
		cout<<"第"<<i<<"个矩阵是:";
		 cout<<p[i-1]<<"*";
		 cin>>p[i];
	 }	 
	int **m,**s;
	m=new int*[n];
	for( i=1;i<=n;i++)
		m[i]=new int[n];

	s=new int*[n];
	for( i=1;i<=n;i++)
		s[i]=new int[n];	
     int x= MatrixChain(p,n,m,s);
     Traceback(1,n,s);
	 cout<<"最小乘积是："<<x<<endl;
	 getch();
}