shengjizuida.cpp

算法分析

#include<iostream>

using namespace std;
int *p;			//to store the digit
int **a;		//a[i][j] is the number combined digits from p[i] to p[j];
int **f;		//f is to store the max multi result
int **s;		//s is to store the partion place
int n;			//the number of digit


//traceBack is to show how the digits is pationed
void traceBack(int i,int j)
{
	int t;
	t=s[i][j];			//t is the partion place
	if(t==-1)			//condition of mission completed
	{
		cout<<a[0][i];
		return;
	}
	traceBack(t,j-1);
	cout<<'*'<<a[t+1][i];
	
}

int main()
{
	
	int i,j,k,t;	//temporary variables
	
	//the fllowing is to initiate array p
	cout<<"Please input the number of digits:"<<endl;
	cin>>n;
	if((p=new int[n])==NULL)
	{
		cout<<"获取内存失败"<<endl;
		return 0;
	}
	cout<<"Please input the digits:"<<endl;
	for(i=0;i<n;i++)
	{
		cin>>p[i];
	}
	
	//the floowing code is to initiate array a
	if((a=new int*[n])==NULL)
	{
		cout<<"获取内存失败"<<endl;
		return 0;
		
	}
	for(i=0;i<n;i++)
	{
		if((a[i]=new int[n])==NULL)
		{
			cout<<"获取内存失败"<<endl;
			return 0;
		}
	}
	for(i=0;i<n;i++)
	{
		a[i][i]=p[i];
		for(j=i+1;j<n;j++)
		{
			a[i][j]=a[i][j-1]*10+p[j];
		}
	}
	
	
	//the flowing is to get memory for array f  and array s
	if((f=new int*[n])==NULL)
	{
		cout<<"获取内存失败"<<endl;
		return 0;
		
	}
	for(i=0;i<n;i++)
	{
		if((f[i]=new int[n])==NULL)
		{
			cout<<"获取内存失败"<<endl;
			return 0;
		}
	}
	if((s=new int*[n])==NULL)
	{
		cout<<"获取内存失败"<<endl;
		return 0;
		
	}
	for(i=0;i<n;i++)
	{
		if((s[i]=new int[n])==NULL)
		{
			cout<<"获取内存失败"<<endl;
			return 0;
		}
	}
	
	//the flowing is to execute the algorithm
	for(i=0;i<n;i++)
	{
		f[i][0]=a[0][i];
		s[i][0]=-1;			
		for(k=1;k<=i;k++)
		{
			f[i][k]=f[k-1][k-1]*a[k][i];
			s[i][k]=k-1;
			for(j=k;j<i;j++)
			{
				t=f[j][k-1]*a[j+1][i];
				if(t>f[i][k])
				{
					f[i][k]=t;
					s[i][k]=j;
				}
			}
		}
	}
	
	
	
	
	
	
	
	
	//the flowing is to output the result
	for(i=0;i<n;i++)
	{	
		cout<<"当含有 "<<i<<" 个 * 时：";
		traceBack(n-1,i);
		cout<<'='<<f[n-1][i]<<endl;
		
	}
	
	
	
	
	//the flowing code is to free resources 
	delete p;
	p=NULL;
	for(i=0;i<n;i++)
	{
		delete a[i];
		delete f[i];
		delete s[i];
	}
	delete a;
	delete f;
	delete s;
	getchar();
	return 0;
}