matrix_mul.cpp

本程序对输入的矩阵选择最优相乘次序

#include "iostream.h"
#include "stdio.h"
#define M 10
int count=0;//count记录最少连乘次数

//对矩阵的规格p[n],判断最优相乘次序m[][],同时记录其最佳断开位置s[][]
void matrixChain (int *p,int n,int m[M][M],int s[M][M])
{
    for(int i=1;i<=n;i++)//初始化表示各个单一矩阵的m[i][i]
        m[i][i]=0;
    for(int r=2;r<=n;r++)//链长度控制
	{
		for(int i=1;i<=n-r+1;i++)//链起始位置控制
        {
            int j=i+r-1; //链终止位置
			//下面根据递归式按矩阵链长的递增方式依此计算出各个m[i][j]
            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;
                }
            }
        }
	}
}

int traceback(int s[M][M],int i,int j,int *p)
{
	if(i==j) return 0;
	traceback(s,i,s[i][j],p);
	traceback(s,s[i][j]+1,j,p);
	cout<<"Multiply A["<<i<<","<<s[i][j]<<"] and A["<<s[i][j]+1<<","<<j<<"]"<<endl;
	count+=p[i-1]*p[j];//记录各矩阵相乘时进行的向量相乘次数
	return count;
}

void main()
{
	int n,p[M],s[M][M],m[M][M];
	cout<<"请输入矩阵的数目:";
	cin>>n;
	cout<<"请输入各矩阵的规格:(如A[2][3]*B[3][5]即输入2 3 5)\n";
	for(int i=0;i<=n;i++) cin>>p[i];
	matrixChain(p,n,m,s);
	cout<<"下面输出最优连乘次序,其中A[i,j]表示Ai到Aj的连乘:\n";
	int a=traceback(s,1,n,p);
	cout<<"在该连乘次序下,仅需做"<<a<<"次向量相乘.\n";
}