最优分解问题

问题

将正整数 n 分解为若干互不相同的自然数的和，使这些自然数的乘积最大

思路

以下内容摘自老师给的 PPT：

对整数分析可有结论： 若 a + b = const, 则 | a – b | 越⼩，a * b 越⼤。 根据原问题的描述，需要将正整数 n 分解为若干互不相同的自然数的和，同时又要使⾃然数的乘积最⼤。 当 n < 4 时对 n 的分解的乘积是小于 n 的； 当 n ⼤于或等于 4 时，n = 1 + ( n – 1 ) 因⼦的乘积也是⼩于 n 的， 所以 n = a + ( n – a ), 2 ≤ a ≤ n - 2, 可以保证乘积⼤于 n, 即越分解乘积越⼤。 因此可以采用如下贪⼼策略： 将 n 分成从 2 开始的连续⾃然数的和，如果最后剩下⼀个数，将此数在后项优先的⽅式下均匀地分给前⾯面各项。 该贪⼼策略⾸先保证了正整数所分解出的因⼦之差的绝对值最⼩，即 | a – b | 最⼩； 同时又可以将其分解成尽可能多的因子，且因⼦的值较⼤，确保最终所分解的⾃然数的乘积可以取得最⼤值。

代码

使用了这个库：The GNU Multiple Precision Arithmetic Library

#include <gmp.h>

/*
 * 假设 n = 13
 * sum = 2 + 3 + 4 (last = 4), 13 - sum = 4 (left = 4)
 *
 * 假设 n = 9
 * sum = 2 + 3 + 4 (last = 4), 9 - sum = 0 (left = 0)
 */
void get_last_left(long *last, long *left, long n)
{
    long i, sum = 0;
    for (i = 2; sum <= n; i++) {
        sum = sum + i;
    }
    i--;

    *last = i - 1;
    *left = n - (sum - i);
}

/*
 * 计算累积，从 start 到 end, 步长为 1
 *
 * 如果 start > end, 返回 1
 */
void cumulate(mpz_t rnt, long start, long end)
{
    mpz_set_si(rnt, 1);
    for (long i = start; i <= end; i++) {
        /*pro = pro * i;*/
        mpz_mul_si(rnt, rnt, i);
    }
}

/*
 * 计算一个正整数的最优分解问题
 *
 * n 必须为正整数，且小于或等于 LONG_MAX
 */
void optimal_decomposition(mpz_t rnt, long n)
{
    switch (n) {
    case 1: mpz_set_si(rnt, 0); return;     /*  0 * 1  */
    case 2: mpz_set_si(rnt, 0); return;     /*  0 * 2  */
    case 3: mpz_set_si(rnt, 2); return;     /*  1 * 2  */
    case 4: mpz_set_si(rnt, 3); return;     /*  1 * 3  */
    }

    long last, left;
    get_last_left(&last, &left, n);

    mpz_t pro;
    mpz_init(pro);
    if (last == left) {             /* example, n = 13, 3 * 4 * 6  */
        cumulate(rnt, 3, last);
        mpz_mul_si(rnt, rnt, last + 2);
    } else {                        /* example, n = 11, 2 * 4 * 5  */
        /* (last - 1 - left) 表示未分配到 1 的个数 */
        cumulate(pro, 2, 2 + (last - 1 -left) - 1);
        mpz_set(rnt, pro);
        cumulate(pro, 2 + (last - 1 - left) + 1, last + 1);
        mpz_mul(rnt, rnt, pro);
    }

    mpz_clear(pro);
}