小学数学题，你会吗？

晓得飞天千秋雪

pmerofc 发表于 2013-06-30 10:37
【题目：将16分解为若干素数的和，求这些素数积的最大值】

完全没头绪

很简单的事呀，我的结果在 http://kan.weibo.com/con/3595009719679031?_from=title

selfrun

尽量取最接近e值的整数，3最接近，就一直取3.
直接公式计算
a = (n-2)/3;
b = n - 3 * a;
ret = b * (3)^a

346196247

我记得我明明是初中农民工啊，发现不懂

cttnbcj

即假设可将16拆分成多个任意实数的和。然后可以证明，只有当16拆分出来的数都相等时，才可能使得它们的乘积最大，这一点可以根据“平方和不等式”得出，即若x+y=a,则xy≤（x2+y2）/2，当且仅当x=y=a/2时等号成立，同样的结论也适合于把a分为三个数、四个数.....、乃至n个数的情况，意思就是：“如果把一个数分成几个数的和，那么当这几个数相等时，它们的乘积最大”。因此，16拆分出来的数必须相等才行。
这一步之后，问题实际上转化为：“将16拆分为N个相等的实数x，求x取何值时x^N最大”
由题意，N=16/x
令y=x^(16/x)，要求的就是x为何值时，y最大
两边取对数，得到：lny=（16/x）lnx
两边求导数，得到：
y’=（16/x2）（1-lnx）·y【其中y=x^(16/x)】
当y’=0的时候，y取得最大值，此时1-lnx=0，即x=e≈2.7182818283....
但是题目要求的是自然数，容易看到，与e最接近的自然数就是3

晓得飞天千秋雪

pmerofc 发表于 2013-06-30 22:32
回复 21# 晓得飞天千秋雪

如果认为我的算法用到了特殊处理了，那么我索性再利用数学推导结果处理一下，这回我的算法可是带有普遍性的算法了 http://kan.weibo.com/con/3595357355981754?_from=title

cjaizss

pmerofc 发表于 2013-06-30 10:37
【题目：将16分解为若干素数的和，求这些素数积的最大值】

完全没头绪

首先证明产生最大积的每个乘数不超过3
反证法:假设最大积中存在大于3的数,
F=F'*a,其中a为大于3的质数,
那么
G=F'*3*2^((a-3)/2) >  F'*a = F
显然F不是最大积,排除.
于是,最大积只有2和3组成
再证明:最大积中2的个数不超过2个
依然假设某个最大积
F=F'*2*2*2
那么
F<F'*3*3
矛盾
所以,我们得到最大积最多2个2的结果
于是
程序就很简单了

daybreakcx

回复 20# pmerofc


    根据我目前认识，动规在某些情况下可以用递归实现，但是这俩还是算俩路子，动规的关键还是空间换时间的思想，而且有最优子结构性质的约束。