题目描述：
问题描述：
设n 是一个正整数。现在要求将n 分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。
编程任务：
对于给定的正整数n，编程计算最优分解方案。
数据输入：
（由文件input.txt 提供输入数据。）文件的第1 行是正整数n。
结果输出:
程序运行结束时，将计算出的最大乘积输出（到文件output.txt 中）。
输入文件示例 输出文件示例
input.txt output.txt
10 30
注：若上述题目要求有括号中橙色字体，即将代码中第7，8行注释解除，令其执行即可。
算法思路：
一、主体思路须知：
（1）、两数和一定时，两数相差越小，两数乘积越大。
（2）、将数分解时，应尽可能使分解的因子没有1。因为1*2*3<2*4。（两者和为6）
由于此条，所以n要分类讨论。n<=4时,除了n=2（不能分解），其余分解必须含因子1。
二、分类讨论：
1、n=1,输出1
2、n=2，输出2
3、n=3，输出1*2=2
4、n=4，输出1*3=3
5、n>=5，执行主体代码部分
三、对n>=5,主题代码部分解释：
由于两数和一定时，两数相差越小，两数乘积越大。
（1）因此从因子2开始分解，即分解为因子2、3、4……
（2）直至n减去“已分解的因子和”的结果（即代码中的OneSum）小于已分解的最大因子。
（3）然后在n已分解的因子中，从最大到小，依次+1（执行OneSum次）。
（4）OneSum恰巧等于分解的最后一个因子时，因为此分解法为2、3……,会导致数组存储的因子全加1后，还剩余1，所有需要用“if(i==-1) {i=flag;}”来将i赋值到数组存储数据的末尾，继续+1，下方示例中注释有详细解释。
例n=11：
第一波分解结果：2，3，4。余2（余数OneSum=2小于已分解的最大因子4）。
第二波操作：将4(最大因子)+1，3（第二大因子）+1
结果:2，4，5。(即从最大因子到小因子，依次+1（执行OneSum=2次）)
第三波操作：计算2*4*5=40，40即n=11分解的不同自然数因子取得的最大乘积。
代码如下：
#include <iostream> #include <fstream> //文件操作头文件 using namespace std; #define N 10000 int main(){ //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int n;cin>>n; int a[N]; if(n==1) cout<<1<<endl; else if(n==2) cout<<2<<endl; else if(n==3) cout<<2<<endl; else if(n==4) cout<<3<<endl; else{//n>=5时 int num=2; n=n-num;//首先存入2 (1计入因子中，乘积较小，例如1*2*3<2*4) int i=0; a[i]=num; int OneSum=0;//记录n减去数组中存储的不同自然数总和的结果 while(n>a[i]){//注：while是先判断，再执行 num++;i++;//已经存了2，所以先各+1 a[i]=num; OneSum=n=n-num; } int flag=i; int OutNum=1;//存储因子乘积，输出是乘积结果，初始值为1 while(OneSum>0){//将因子数组从后往前 OneSum个数皆+1 a[i]=a[i]+1; OneSum=OneSum-1; i--; if(i==-1) {i=flag;} //新补加条件， 例如n=8,分解为2、3余3,2+1,3+1，OneSum还余1，所以需要重新从数组末尾再遍历 //例n=13，分解为2,3,4余4，此操作是三个数皆加一后，将i赋值到flag即数组存储的末尾 //即 2+1,3+1,4+2 } for(int i=0;i<=flag;i++){//计算乘积 //cout<<a[i]<<endl;执行此操作方便理解 OutNum=OutNum*a[i]; } cout<<OutNum<<endl; return 0; } }
