chain.cpp

动态规划算法实现矩阵相乘

// Chain.cpp: implementation of the CChain class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "Chain.h"
#include "iostream.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CChain::CChain()
{
	length=0;
}

CChain::~CChain()
{
	int i;
	for(i=0;i<length+1;i++)
	{
		delete m[i];
		delete s[i];
	}
	delete m;
	delete s;
	delete c;
}

void CChain::ChainInit()
{
	int i;
	cout<<"请输入矩阵个数:";
	cin>>length;
	m=new int*[length+1];
	for(i=0;i<length+1;i++)
		m[i]=new int[length+1];
	s=new int*[length+1];
	for(i=0;i<length+1;i++)
		s[i]=new int[length+1];
	c=new int[length+1];
	for(i=1;i<=length;i++)
	{
		m[i][i]=0;
	}
	cout<<"请输入各矩阵参数:"<<endl;
	cout<<"矩阵1列数:";
	cin>>c[0];
	for(i=1;i<=length;i++)
	{
		cout<<"矩阵"<<i<<"行数:";
		cin>>c[i];
	}
}

void CChain::Matrix_Chain_Order()
{
	int l,i,j,k,q;
	for(l=2;l<=length;l++)
		for(i=1;i<=length-l+1;i++)
		{
			j=i+l-1;
			m[i][j]=60000;
			for(k=i;k<=j-1;k++)
			{
				q=m[i][k]+m[k+1][j]+c[i-1]*c[k]*c[j];
				if(q<m[i][j])
				{
					m[i][j]=q;
					s[i][j]=k;
				}
			}
		}
	cout<<m[1][length]<<endl;
}

void CChain::Print_Optimal_Parent(int **s,int i,int j)
{
	if(i==j)
		cout<<"A"<<i;
	else{
		cout<<"(";
		Print_Optimal_Parent(s,i,s[i][j]);
		Print_Optimal_Parent(s,s[i][j]+1,j);
		cout<<")";
	}
}

void CChain::ToPrint()
{
	Print_Optimal_Parent(s,1,length);
}