今天在学校群里有人问到这个问题：
输入任意一个正整数N,将其分成多个互不相同的整数,和为N,乘积最大。写出C/C++代码。
贪心策略：要使乘积做大，尽可能地将指定的n(n>4)拆分成从2开始的连续的自然数的和，如果最后有剩余的数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。
例：n=10,先拆分为：10=2+3+4+1，最后一项为1，比4小，将其分配给前面的一项，得到10=2+3+5，所以最大的乘积为2*3*5=30.
n=20,拆分为：20=2+3+4+5+6，刚刚好，最大乘积为2*3*4*5*6=720.
n=26，拆分为：26=2+3+4+5+6+6，因为最后一项为6，不比最后的第二项大，所以将其平均分给前面的项，优先考虑后面的项，即前面的4项各分到1，第5项，分到2，最后是26=3+4+5+6+8，所以最大的乘积为3*4*5*6*8=2880.
基本算法描述如下：
1． 拆分过程
拆分的数a先取2;
当n>a 时做
begin
选择a作为一项；
a增加1；
n减少a;
end;
如果n>0，那么将n从最后一项开始平均分给各项；
如果n还大于0，再从最后一项开始分一次；
2． 求乘积
设置一个数组来存放乘积，初始状态位数为1，结果为1；
将上面拆分的各项依次跟数组各项相乘并考虑进位；
下面是在网上找到的代码
代码如下：
#include<iostream.h>
int d[1000],num;
long number;
void divide(int k,int n)
{
int i,j;
for(i=d[k-1]+1;i*2<n;i++)
{
d[k]=i;
if((n-i)>d[k]*2)
divide(k+1,n-i);
d[k+1]=n-i;
number++;
cout<<endl<<"NO."<<number<<"=";
for(j=1;j<=k;j++)
cout<<d[j]<<"+";
cout<<d[j];
}
}
void main()
{
int i,j;
cout<<"Input the number to divide:";
cin>>num;
d[0]=0;
divide(1,num);
}
第二种算法：
#include <iostream>
#include <ctime>
using namespace std;
int count1=0;
void print(int b[],int n)
{
int j;
count1++;
cout<<n+1<<"=";
for(j=0;j<n-1;j++)
if(b[j]!=0)
{ cout<<b[j];break;}
for(j=j+1;j<n;j++)
if(b[j]!=0)
cout<<"+"<<b[j];
cout<<endl;
}
void GetPowerSet(int i,int a[],int b[],int n)
{
//功能：求以数组a[i,..,n-1]中元素为集合中元素的集合的冥集
//在对字符串中元素进行运算时要注意字符串的结束符'\0'也算是集合中的元素
//具体处理的方法见上例
int j,sum=0;
if(i==n)
{
for(j=0;j<n;j++)
sum+=b[j];
if(sum==n+1) print(b,n);
}
else
{
for(j=0;j<n;j++)
sum+=b[j];
if(sum==n+1)
print(b,n);
if(sum<n+1)
{
b[i]=a[i]; GetPowerSet(i+1,a,b,n);
b[i]=0; //b[i]所重新赋的值必须是a中不曾出现的元素
GetPowerSet(i+1,a,b,n);
}
}
}
int main()
{
int N;
time_t time1,time2;
cout<<"输入你要分解的数字:";
cin>>N;
time1=time(NULL);
int *a=new int[N-1];
int *b=new int[N-1];
for(int i=0;i<N-1;i++)
{ a[i]=i+1; b[i]=0;
}
GetPowerSet(0,a,b,N-1);
cout<<"有"<<count1<<"种分解方法"<<endl;
time2=time(NULL);
cout<<difftime(time2,time1)<<"花费";
system("pause");
return 0;
}
这个题目的一个变种是：一个正整数N，拆成任意的正整数之和，怎样使这些数的乘积最大？
1 先看一个原则，相等的数相乘最大
n*n > (n-1)*(n+1)=n*n-1
所以相等的2个数相乘，乘积最大
2 看看前面的几个数字
对于和为6
2*2*2 = 8
3*3 = 9 所以3的大
4 我们不考虑了，因为2*2=4 他是平衡点
5 本身就没有 2×3 大，
5以上的就更不用考虑了，因为随便拆开都比他大
所以3是拐点。
也就是尽可能拆分成3，乘积最大
首先，不要拆出1来了，拆出1来就是浪费
其次，不要拆出5以上的数来，不然还不如继续拆分，比如5拆成2*3就比原来的5要大
再次，如果拆出4来，干脆拆成两个2好了，反正都一样
所以，只要考虑拆出多少个2和3来就可以了。
再来，每三个2可以换成两个3，这样3*3 > 2*2*2，所以，尽量拆成3最好了，这样100最后就拆成了32个3和2个2
有关数学分析：
容易说明，拆成n个数时候，变成(N/n)^n最大,那么就是求x使得f=(N/x)^x最大,f'=(N/x)^x(-1+ln(N/x))就是说N/x=e时候最大.
用多元函数求边际极值方法做的，就是用拉格朗日乘数法，设被分解的正整数是N，分的个数为n，并且n＜N，n、N为正整数，可以设N=n+t，t可以认为N与n相差的数，对最大值（N/n）^n=(1+t/n)^n求极限，可以得到e^t，所以t越大，e^t越大，因为t是N与n的差，正整数N与分的分数n差越多，最大值越大，如果t=0，即N分成N个1，乘积就是1.