kmul.cpp

设I是一个n位十进制整数。如果将I划分为k段

#include <fstream.h>
#include <math.h>

class CKuml
{
public: 
	CKuml();
	virtual	~CKuml();
private:
	ifstream m_InFile;
	ofstream m_OutFile;
	const char * m_InFileName;
	const char * m_OutFileName;

protected:
    double Divide_up(double I,int n,int k,double **recTab);
public:
	void Begin_Kuml();
};

CKuml::CKuml():m_InFileName("input.txt"),m_OutFileName("output.txt")
{

    m_InFile.open(m_InFileName,ios::in);
    m_OutFile.open(m_OutFileName,ios::out);
}

CKuml::~CKuml()
{
    m_OutFile.close();
}

///////////////////////////////////////////////////////////////////

inline double CKuml::Divide_up(double I,int n,int k,double **recTab)
{
	double temp,rest,result;
	double bestResult = 0;
	//若被分割的段数为1，就直接返回
	if(k == 1)
	{
		return I;
	}
	//若表中记录不为-1，就返回该值
	if(recTab[n-1][k-1] != -1)
	{
		return recTab[n-1][k-1];
	}

	for(int i=1;i<=n-k+1;i++)
	{
		temp = pow(10,n-i);
		//取出余下的整数
		rest = fmod(I,temp);
		//求出余下整数的最大k-1乘积
		result=(int)(I/temp) * Divide_up(rest,n-i,k-1,recTab);

		if(result > bestResult)
		{
			bestResult = result;
		}
	}
	recTab[n-1][k-1] = bestResult;//将k乘积写入备忘录
	return bestResult;
}


void CKuml::Begin_Kuml()
{
	double I,t;//I为要处理的数

	int k,n;

	m_InFile>>n;
	m_InFile>>k;
	m_InFile>>I;
	
	if (n<=0||n>100)
	{
		m_OutFile<<"输入的n的范围不在1--100之内!";
		return;
	}
	
    
	//生成动态二维数组 
	double** recTab = new double*[n];
	for(int m=0;m<n;m++){
		recTab[m] = new double[k];
	}

	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			recTab[i][j] = -1;
		}
	}

	//进行处理
	double resuIt = Divide_up(I,n,k,recTab);

	m_OutFile<<(int)resuIt<<endl;

	for(int p=0;p<n;p++)
	{
		delete[] recTab[p];
	}
	delete[] recTab;
	recTab = 0;
	return;
}

/////////////////////////////////////////////////////////////////////

void main()
{
	CKuml kuml;
	kuml.Begin_Kuml();
}