整数分解数学问题

一个正整数n可以分解为1-n个正整数的和，如何分解能使
分解的各个数的乘积最大？最大乘积等于几，并证明。
如果能给出数学表达式也可。
比如3可以分解为1+1+1，乘积=1，也可以分解为1+2，乘积=2
所以最大值=2

提示：
这么多整数如果相等，积比不相等的要大
例如：n=2x x*x=x^2, (x-1)(x+1)=x^2-1
假定分为m个整数，积=(n/m)^m
当n/m=e=2.7...时最大，但本题要求整数，所以还要再讨论

这个题目以前其他地方有过的吧。
我也只证明到非整数的。
是整数的没想到怎么证。

取半数是不是可以？

初步想法，没论证过，呵呵

全变成2是不是最大的？

N = 3k，拆成k个3
N = 3k+1，拆成k-1个3和2个2
N = 3k+2，拆成k个3和1个2

奇数的话，也应该是除了1之外的最小约数的某次方。
如：15＝3×5＝3+3+3+3+3      （3是除了1之外15的最小约数）
3×3×3×3×3最大。
如果是奇质数，那么就是：（一半－0.5）×（一半＋0.5）
如：7=3＋4  3×4＝12

呵呵！为了看规律只好先笨一些，人工列一下了：
原数：分解数（积）
1：1（1）
2：1、1（1）
3：1、2（2）
4：2、2（4）
5：2、3（6）
6：3、3（9）
7：2、2、3；3、4（12）
8：2、3、3（18）
9：3、3、3（27）
10：2、2、3、3；3、3、4（36）
11：2、3、3、3（54）
12：3、3、3、3（81）
13：2、2、3、3、3；3、3、3、4（108）
14：2、3、3、3、3（162）
15：3、3、3、3、3（243）
16：2、2、3、3、3、3；3、3、3、3、4（324）
17：2、3、3、3、3、3、3（546）
。。。。。。
哇！出汗了！:sweat2: 还好不用太多，规律已可见一斑了！
总结一下：
1、2和3是最小分解数，因为将其分解只能得到比其本身还小的最大积数。
2、将原数分解到由最小分解数构成，3尽量最多，即可获得最大乘积。
3、算法应该就很简单啦！将原数除以3得到整数商和余数，如果余数为0，则最大积为3的商次方；如果余数为2，则最大积为3的商次方乘以2；如果余数为1，则最大积为3的商－1次方乘以4。
4、证明：我们知道整数的表示方式为：2n或2n＋1，则由于n×n>（n+1）×（n－1）或n×（n＋1）>（n－1）×（n＋2），因此将原数分解成2n或2n＋1，再对n进行以上分解直到分解为由最小分解数构成，3尽量最多，即可获得最大乘积。可惜要证明“3尽量最多”这个条件，呵呵，我的功力可不行了！:sweat:
5、例：8－>4＋4－>2＋2＋2＋2－>2＋3＋3
              10－>5＋5－>2＋3＋2＋3－>4＋3＋3

同意fdpay的方法。
当n>4，floor(n/2)*ceiling(n/2)>n
当n=4，2*2=4
当n=3, 1*2<3
当n=2, 1*1<2
当n=1, 0*1<1
因此，要获得最大的乘积，应将n分解为3,2的组合，而且应先满足分解为3的情况。

看过  觉得要证明N-1 才能递归到N啊

很好的讨论，怎么严格证明呢

f

f

看一遍, 受益:)

回复 #1 hotiice 的帖子

为什么要应先满足3呢，如果是2*2*2，那可以看到，因为2*2=2+2，不会变大，也不会减少，这样换成3，就可以加大2*2*2<3*3,故要把2尽量换成3，
X+Y=N, 求XY的最大值。
Z=XY,
X=N-Y,
Z=Y(N-Y)
Y=N/2时,
Z有最大值，当然Y可以是N/2的上界也可是其下界，
这样一直分下去就会得到2和3组成的数，
因为2*2=2+2，不会变大，也不会减少，这样换成3，就可以加大2*2*2<3*3,故要把3个2尽量换成2个3
可以看到，在这样的分组中，最多两个2，有3个2就换成2个3了

[[i] 本帖最后由 redkissme 于 2008-5-18 15:53 编辑 [/i]]

[quote]原帖由 [i]palen[/i] 于 2006-8-2 10:11 发表 [url=http://www.itpub.net/redirect.php?goto=findpost&pid=5013299&ptid=582225][img]http://www.itpub.net/images/common/back.gif[/img][/url]
呵呵！为了看规律只好先笨一些，人工列一下了：
原数：分解数（积）
1：1（1）
2：1、1（1）-------应该是2：2（2）
3：1、2（2）-------应该是3：3（3）
4：2、2（4）
5：2、3（6）
6：3、3（9）
7：2、2、3；3、4（12）
8：2、3、3（18）
9：3、3、3（27）
10：2、2、3、3；3、3、4（36）
11：2、3、3、3（54）
12：3、3、3、3（81）
13：2、2、3、3、3；3、3、3、4（108）
14：2、3、3、3、3（162）
15：3、3、3、3、3（243）
16：2、2、3、3、3、3；3、3、3、3、4（324）
17：2、3、3、3、3、3、3（546）
。。。。。。
哇！出汗了！:sweat2: 还好不用太多，规律已可见一斑了！
总结一下：
1、2和3是最小分解数，因为将其分解只能得到比其本身还小的最大积数。
2、将原数分解到由最小分解数构成，3尽量最多，即可获得最大乘积。
3、算法应该就很简单啦！将原数除以3得到整数商和余数，如果余数为0，则最大积为3的商次方；如果余数为2，则最大积为3的商次方乘以2；如果余数为1，则最大积为3的商－1次方乘以4。
4、证明：我们知道整数的表示方式为：2n或2n＋1，则由于n×n>（n+1）×（n－1）或n×（n＋1）>（n－1）×（n＋2），因此将原数分解成2n或2n＋1，再对n进行以上分解直到分解为由最小分解数构成，3尽量最多，即可获得最大乘积。可惜要证明“3尽量最多”这个条件，呵呵，我的功力可不行了！:sweat:
5、例：8－>4＋4－>2＋2＋2＋2－>2＋3＋3
              10－>5＋5－>2＋3＋2＋3－>4＋3＋3 [/quote]

小弟发下言：

1 n分解为2个数时 最大为[n/2]*[(n+1)/2]  Eg:max(6,2)=9 max(9,2)=20,max(10,2)=25
2 n分解为3个数时 最大为[n/3]*[(n+1)/3]*[(n+2)/3]  Eg:max(6,3)=8 max(9,3)=27,max(10,3)=36
.......
k n分解为k个数时 最大为[n/k]*[(n+1)/k]*[(n+2)/k]...[(n+k-1)/k]
关键是要求出 1..k中那个数最大？

当然，分解的终止应该是[n/k]*[(n+1)/k]*[(n+2)/k]...[(n+k-1)/k]中有1出现为止

很精辟的讨论