整数分解数学问题

yaozhan189

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

hotiice

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

weijunoo9

f

DragonBill

看一遍, 受益

redkissme

为什么要应先满足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了

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

xxzh_xxzh

原帖由 palen 于 2006-8-2 10:11 发表
呵呵！为了看规律只好先笨一些，人工列一下了：
原数：分解数（积）
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）
。。。。。。
哇！出汗了！ 还好不用太多，规律已可见一斑了！
总结一下：
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尽量最多”这个条件，呵呵，我的功力可不行了！
5、例：8－>4＋4－>2＋2＋2＋2－>2＋3＋3
              10－>5＋5－>2＋3＋2＋3－>4＋3＋3

zmjeffwc

小弟发下言：

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中那个数最大？

zmjeffwc

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

albert_deng

很精辟的讨论