矩阵.cpp

矩阵连成的算法经过本人测试通过上课的作业学算法的同学可以借鉴一下

#include "iostream.h"

void 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;
				}
			}
		}
	
}

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];
	cout<<"和 A"<<(s[i][j]+1)<<"相乘"<<endl;//<<","<<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<<p[1]<<endl;
	 cout<<endl;
	 for(int i=2;i<n+1;i++)
	 {

		cout<<"第"<<i<<"个矩阵是:";
		 cout<<p[i-1]<<"*";
		 cin>>p[i];
	 }
//	int p[]={30,35,15,5,10,20,25};
//	int m[6][6],s[6][6];
	 
	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];
	
	MatrixChain(p,n,m,s);
     Traceback(1,n,s);
	
}