matrix chain.cpp

算法导论例题的实现

#include "Matrix chain.h"


int num;//num =matrix num-2;
int  *arr;
//int *matrixArr;
int **lest;//lest[i][j] = minimum multiply times from i to j; 
int **partition;
int *parenthesisL,*parenthesisR;


template <class T> T** allocH(int row,int col, T){
	
	T* p= new T [row*col];
	T (**pp) = new T* [row];
	for(int i=0;i<row;i++)
		pp[i]= p+i*col;
	return pp;
}


template <class T> void dellocH(T** pp){
	
	delete []pp[0];
	delete []pp;
	pp=0;

}

int OptMult(int start,int end){//start & end is the number of matrixes

	if(end ==start){
		return 0;
	}
	else if (lest[start][end]>0){
			return lest[start][end];
	}
	/*else if(end -start==1){
		return lest[start][end] = arr[2*start]*arr[2*end]*arr[2*end+1];
	}*/


	else {
		unsigned min=(unsigned)(-1);
		int left=0,right=0;
		int index;
		for(int i=start;i<end;i++){

			left = OptMult(start,i);
			right = OptMult(i+1,end);
	
			
			int temp = left+right+arr[start]*arr[i+1]*arr[end+1];

			if (temp<min){
				min =temp;
				index = i;

			}
		}

		partition[start][end] = index;
		return  lest[start][end] = min;
		//parenthesisL[start]+=1;

	}
}

void GetParthe(int start,int end){
			
	if(end-start<=1){
	
		return;
	}
		
	else {
		int par =partition[start][end];
		parenthesisL[start]++;
		parenthesisL[par+1]++;
		parenthesisR[par]++;
		parenthesisR[end]++;
		GetParthe(start,par);
		GetParthe(par+1,end);
	}		
		
}

int main(){


	ifstream arg("input.txt");
	ofstream result("output.txt");
	
	if ( !arg ) { // opened failed
     cerr << "cannot open file for input"<<endl;
     exit( -1 );
	}

	if ( !result ) { // opened failed
     cerr << "cannot open file for output"<<endl;
     exit( -1 );
	}

	arg>>num;

	//arr = new int[num];
	parenthesisL= new int [num-1];
	parenthesisR= new int [num-1];
	arr = new int [num];

	//arg>>arr[0];
	for(int i=0;i<num;i++){
		arg>>arr[i];
		
	}
//	arg>> arr[2*num-3];9+


	for(int i=0;i<num-1;i++){
		parenthesisL[i]=0;
		parenthesisR[i]=0;
	}

	lest = allocH(num-1,num-1,num);
	partition = allocH(num-1,num-1,num);

	for(int i=0;i<num-1;i++)
		for(int j=0;j<num-1;j++){
			lest[i][j]=0;
			partition[i][j]=-1;
		}
	arg.close();

//body
	/*int kk=5;
	int pp=1;
	if(kk- pp >0)
		cout<<"good"<<endl;*/

	for(int i=0;i<num;i++){
		result <<arr[i]<<" ";
	}
	
	result<<endl;
	
	int k= OptMult(0,num-2);

	result <<"The result is "<<k<<endl; 

	GetParthe(0,num-2);

	result<<"The equation is: "<<endl;

	char mn='A';

	for(int i=0;i<num-1;i++){
	
		for(int j=parenthesisL[i];j>0;j--){
			result<<"(";
	
		}

		
		result<<" "<<mn<<" ";

		mn++;

		for(int j=parenthesisR[i];j>0;j--){
		result<<")";
	
		}
	}
/*	for(int i=parenthesisL[0];i>0;i--){
		result<<"(";
	
	}

	result<<" "<<mn<<" ";
	for(int i=1;i<num-1;i++){

		for(int j=parenthesisR[i-1];j>0;j--){
			result<<")";
		
		}

		for(int j=parenthesisL[i];j>0;j--){
			result<<"(";
		
		}
		
		mn++;

		result<<" "<<mn<<" ";

	}
	
	//cout<<endl<< parenthesisR[num-2]<<endl;

	for(int i=parenthesisR[num-2];i>0;i--){
		result<<")";
	
	}*/

	//result<<endl;
	
}