贪心算法:最优分解问题

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

代码如下:

int BestMul(int n)
{
    int i,j,mul=1;
    int num;
    //初始化一个数组，用来存放分解后的每个数
    int a[MAX] = {0};
    a[0]=2;
    num=n-2;
    //利用for循环来从2开始递增,每次后一个数比前一个数大1
    //当最后剩下的数小于前一个数时跳出循环
    for(i=0;num>a[i];i++){
        a[i+1]=a[i]+1;
        num-=a[i+1];
        printf("%d\t",a[i]);
    }
    printf("\nnum为%d\n",num);
    //得到当前数的个数
    j=i+1;
    //当剩下的数不为0时，均匀分配给前面的数
    while(num!=0)
    {
        a[i]++;
        num-=1;
        //循环分配
        i=(i-1+j)%j;
        printf("%d",a[i]);
    }
    printf("\n");
    for(i=0;i<j;i++){
         mul*=a[i];
         printf("%d ",a[i]);
    }
    printf("\n最大乘积为%d\n",mul);
}

void main()
{
    int n;
    printf("请输入自然数n:\n");
    scanf("%d",&n);
    BestMul(n);
}