贪心算法----正整数分解问题 和相同，乘积最大

一、问题描述

设n是一个正整数。现在要求将n分解为若干个自然数之和，且使这些自然数的乘积最大。

本文将这个大问题分解为两个小问题：

（1）这些自然数是互不相同的

（2）这些自然数可以是相同的

二、解决思路

这其实是个数学问题，总体上的宗旨就是分解的数越接近，它们的乘积是最大的，而且不要分解出1，至少从2开始。

针对（1）这个问题，因为这些若干个自然数是不相同的，所以只能是从2开始分解，如2,3,4...这种顺序

在这里，我们把这个分解问题具体化：

9=2+3+4，刚好可以分解这三个连续的数；

10=2+3+4+1，因为1不会增大乘积，反而会占据和，所以应该将其加到前面三个数上，为了保证最大而且互不相同，加到4上，则分解为10=2+3+5；

11=2+3+4+2，如果把2直接加到4上，乘积是2*3*6=36；如果分别加到连续的数上，如3,4，保证这些数之间的差距是最小的，那么乘积是2*4*5=40；

12=2+3+4+3；则这个三分成三个一，加到前面三个数上，保证了连续性；

13=2+3+4+4；因为是四个一，所以我们采取的方法是最后一个数加2，其他加1，那么乘积是：3*4*6=72；

因此总体的策略就是先分解成连续的自然数，将剩余的数按照从后往前的次序一次均匀分配。

针对（2）问题，因为分解的数是可以相同的，所以先比较一下分解成相同的数和不同的数哪种的乘积大。如

6=3+3；6=2+4;

3*3=9；

2*4=8；

所以分解为相同的数保证之间的差距最小，从而乘积也是最大的。自然知道了分解成相同的数的优势后，对于一个整数，我们应该尽可能多得分解成哪种数呢？

对于4来说，只能拆成2+2，因为要避免拆1；且2*2的效果与本身大小是一致的；

对于5来说，只能拆成2+3，因为要避免拆1；且2*3的效果大于5本身；

对于6来说，拆成3+3的效果（9）要好于2+2+2的效果（8）；

对于7而言，拆成3+4的效果是最好的；

对于8而言，我们可能第一反应是4+4，效果是16；但是实际上最优的分解式3+3+2,效果是18；

对于10来说，理论上是10=5+5；

但是鉴于5本身还有更好的分解，所以10=（2+3）+（2+3）；

所以分解拆数的策略是：先分解成尽可能多得3，然后再分解成2，不要分出1！

考虑任意的一个数，它除以3后的情况只有3种：

（1）整除，余数是0，如9，分解成3+3+3就是最优的；

（2）不整除，余数是1，如10，分解成3+3+4或者3+3+2+2；除了三之外其余的就用2或者4；

（3）不整除，余数是2，如11，分解成3+3+3+2；

三、程序设计

（1）自然数不相同：

（2）分解成可以相同的自然数

四、程序结果

（1）不相同整数的情况：

2*3*5=30；

（2）可以相同整数的情况

3*3*2*2=36；