最优分解问题"/>
最优分解问题
问题描述:设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);
}
更多推荐
最优分解问题
发布评论