两个整数划分——一句话造成完全不同的算法

时间：2010-09-11 来源：Sephiroth Lee

首先我们来看两道题目：

将一个整数n分成若干个互不相同的数的和，使得这些数的乘积最大。其中1<=n<=1000。
若干个正整数之和为n，其中：n<2000，试求它们乘积的最大值以及该最大值的位数k。

很容易看出来，两道题目的区别就在于第一道题目要求各个数不同。我们来看看4～10这几个数分解的方法，这个可以手工进行计算得出：

4 2*2
5 2*3
6 2*4
7 3*4
8 3*5
9 2*3*4
20 2*3*5

大家在做中学的物理题的时候，应该都知道两个和相等的数，相差越小乘积越大。那么很容易想到这个也是相差越小，乘积越大。那么我们要做的就是将n分为互不相同的几分，要求相差最小。我们的做法就是，从2开始，每个数是前面的数+1。直到无法满足为止，然后在将剩下的数从后向前给每个数分1。比如说8，第一步我们分为2,3，剩下3，然后从后向前给每个数分1，变成3,4，剩下1，然后重复分1的过程，得到最终结果3,5。

整数分解1

#include <stdio.h>
#define maxn 10000

int a[maxn];
int n,tot;
long long ans;

int main()
{
    freopen("fen1.in","r",stdin);
    freopen("fen1.out","w",stdout);
    
    scanf("%d",&n);
    a[0]=1;
    while (n>a[tot])
    {
        ++tot;
        a[tot]=a[tot-1]+1;
        n-=a[tot];
    }
    while (n)
        for (int i=tot;i>0;--i)
        {
            if (!n) break;
            ++a[i];
            --n;
        }
    for (int i=1;i<tot;++i) printf("%d ",a[i]);
    printf("%d\n",a[tot]);
    ans=1;
    for (int i=1;i<=tot;++i) ans*=a[i];
    printf("%lld\n",ans);
    return 0;
}

然后看第二题。根据数学规律可知,若要使和固定的数的乘积最大，必须使这些数尽可能的多为3，于是可推得以下规律：当N mod 3＝1 时，N可分解为一个4和若干个3的和；当N mod 3＝2 时，N 可分解为一个2和若干个3的和；当N mod 3＝0 时，N 直接分解为若干个3的和。按照这一分解方法，所有因数的乘积必定最大。

整数分解2

#include <stdio.h>

long long ans;
int n;

int main()
{
    freopen("fen2.in","r",stdin);
    freopen("fen2.out","w",stdout);
    
    ans=1;
    scanf("%d",&n);
    if (n%3==0)
        while (n)
        {
            ans*=3;
            n-=3;
        }
    else if (n%3==1)
    {
        ans=4;
        n-=4;
        while (n)
        {
            ans*=3;
            n-=3;
        }
    }
    else
    {
        ans=2;
        n-=2;
        while (n)
        {
            ans*=3;
            n-=3;
        }
    }
    printf("%lld\n",ans);
    return 0;
}