最优分解问题

最优分解问题"/>

最优分解问题

问题描述：设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，且使这些自然数的乘积最大。

算法设计：给定的正整数n（n>=2)从2开始分解，分解为2,3,4，........相加等于n,若不相等则把剩余的数分解到从后往前的数组中，最后把这些自然数组相乘。

举个例子

n=13

第一次分解 2,3,4。剩余4，把4分解成4个1，分配给前面的数组，得到分配的数就+1，即变成3,4,5，还剩余1，继续从后往前分配，得到3,4,6。分解完成！

代码如下：

#include <iostream.h>#define Max 100void ContinueDiv(int b[],int N,int i)
{int j=i;    while(N>0&&j>=2){b[j]++;   //把剩余的数继续分解到从后往前的数组上N--;	  //每分解一次，剩余的数字-1;j--;      }if(N>0)ContinueDiv(b,N,i);  //N>0,还未分解完，继续分解
}
void Div(int num)
{int a[Max],n=num,i=2;  //n为剩余数,a[Max]存放数字的数组，分解的数字从2开始，因为分解为1和n-1无意义while(n>a[i-1])   //分解初始数组{a[i]=i;n=n-a[i];   i++;}if(n<=a[i-1]) //数组之和还未达到num，继续再原来的数组中分解{ContinueDiv(a,n,i-1);}int Multi=1,j;   //Multi表示相乘的积cout<<"分解的数组为:";for(j=2;j<=i-1;j++)  {Multi*=a[j];cout<<a[j]<<" ";}cout<<endl<<"积为"<<Multi<<endl;}void main()
{int x;cout<<"请输入一个正整数:";cin>>x;if(x==1){cout<<"分解的数组为:1";cout<<endl<<"积为1"<<endl;}else Div(x);
}