cpp1.cpp

矩阵连乘的括号画分

#include<iostream.h>
void chain(int n,int p[],int **m,int **s)
//p[n-1]*p[n]为An的下标
//s[i][j],m[i][j]分别为Ai到Aj最小运算分法的点和值
//n为总运算的元素个数
{
	for(int i=1;i<=n;i++) m[i][i]=0;//只有1个元素则不做任何操作
	for(int num=2;num<=n;num++)//num表示元素个数
	{
		for(int i=1;i<=n-num+1;i++)//按所含元素个数从小往大算
		{
			int j=i+num-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 min=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(min<m[i][j])//比较，如有更小分法则记录
				{
					m[i][j]=min;
					s[i][j]=k;
				}
			}
		}
	}
}
void kuohao(int i,int j,int khl[],int khr[],int **s)
{
	if(j-i>=2)
	{
		if(s[i][j]==i)//形如Ai(┈Aj)的情况
		{
			khl[i]++;
			khr[j]++;
		}
		else if(s[i][j]==j-1)//形如(Ai┈)的Aj情况
		{
			khl[i-1]++;
			khr[j-1]++;
		}
		else//形如(Ai┈Ak)(┈Aj)的情况
		{
			khl[i-1]++;
			khl[s[i][j]]++;
			khr[s[i][j]]++;
			khr[j]++;
		}
		kuohao(i,s[i][j],khl,khr,s);
		kuohao(s[i][j]+1,j,khl,khr,s);
	}
}
void main()
{
	int n;
	cout<<"输入数据的个数:  ";
	cin>>n;
	int *p=new int[n+1];//p[n-1]*p[n]为An的下标
	int *khl=new int[n+1];//khl[i]记录Ai右边的左括号数目
	int *khr=new int[n+1];//khr[i]记录Ai右边的右括号数目
	cout<<endl<<"输入p[0]至p["<<n<<"]的值(p[n-1]*p[n]为An的下标):  "<<endl;
	for(int i=0;i<=n;i++)
	{
		cin>>p[i];
		khl[i]=0;
		khr[i]=0;
	}
	khl[0]=1;
	khr[n]=1;
	int **m=new int*[n+1];
	int **s=new int*[n+1];//s[i][j],m[i][j]分别为Ai到Aj最小运算分法的点和值
	for(int j=1;j<=n;j++)
	{
		m[j]=new int[n+1];
		s[j]=new int[n+1];
	}
	chain(n,p,m,s);
	kuohao(1,n,khl,khr,s);
	cout<<endl<<"最优计算次序"<<endl;
	for(int k=0;k<=n;k++)
	{		
		if(k>0)
		{
			cout<<"A"<<k;
		}
		for(int num=khr[k];num>0;num--)
		{
			cout<<")";
		}
		for(num=khl[k];num>0;num--)
		{
			cout<<"(";
		}
	}
	cout<<endl;
}