最大k乘积问题 .cpp

/*最大k乘积问题 问题描述: 设I是一个n位十进制整数。如果将I划分为k段

/*最大k乘积问题 
问题描述:
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。
试设计一个算法，对于给定的I和k，求出I的最大k乘积（n<=10）。 
示例:输入为 ： 4  3
            结果:1234
*/


#include <iostream.h>
#include <iomanip.h>
#include <fstream.h>
#include <stdlib.h>
#include <math.h>

//求最大k乘积：参数1:待处理的整数，参数2:位数，参数3:段数，参数4:做为备忘录的动态二维数组，返回值为k乘积
double process(double,int,int,double**);

void main(){

	ifstream inputFile("input.txt");
	ofstream outputFile("output.txt");

	//1.读入要处理的数的位数和分割的段数以及目标
	int num = 0;//数的位数
	inputFile >> num;
    int cutNum = 0;//分割的段数
	inputFile >> cutNum;
	double target;//要处理的数
	inputFile >> target;

	//2.生成动态二维数组 
	double** recTab = new double*[num];
	for(int m=0;m<num;m++){
		recTab[m] = new double[cutNum];
	}
	for(int i=0;i<num;i++){
		for(int j=0;j<cutNum;j++){
			recTab[i][j] = -1;
		}
	}

	//3.进行处理
	double result = process(target,num,cutNum,recTab);

    //4.将结果保存
	//cout<<"The process is over,the result is "<<setiosflags(ios::fixed)<<setprecision(0)<<result<<endl;
	outputFile<<setiosflags(ios::fixed)<<setprecision(0)<<result;

	//5.删除动态二维数组
    for(int p=0;p<num;p++){
		delete[] recTab[p];
	}
	delete[] recTab;
	recTab = 0;

	return;
}

double process(double target,int num,int cutNum,double** recTab){
	if(cutNum == 1){
		return target;//若被分割的段数为1，就直接返回
	}
	if(recTab[num-1][cutNum-1] != -1){
		return recTab[num-1][cutNum-1];//若表中记录不为-1，就返回该值
	}
	double processResult = 0;
	for(int i=1;i<=num-cutNum+1;i++){
		double temp = pow(10,num-i);
		int firstInt = (int)(target/temp);//取出左边的整数
		double restTarget = fmod(target,temp);//取出余下的整数
		//对余下的数进行k-1段的划分
		double restMultiply = process(restTarget,num-i,cutNum-1,recTab);
	    double oneResult = firstInt*restMultiply;
		if(oneResult > processResult){
			processResult = oneResult;
		}
	}
	recTab[num-1][cutNum-1] = processResult;//将k乘积写入备忘录
	return processResult;
}