Chinaunix

标题: 小学数学题，你会吗？ [打印本页]

作者: pmerofc 时间: 2013-06-30 10:37
提示: 作者被禁止或删除内容自动屏蔽

作者: sqfasd 时间: 2013-06-30 11:00
本帖最后由 sqfasd 于 2013-06-30 11:02 编辑

我错了~~~~~

作者: pmerofc 时间: 2013-06-30 11:04
提示: 作者被禁止或删除内容自动屏蔽

作者: sqfasd 时间: 2013-06-30 11:16
回复 3# pmerofc

刚提交完答案就发现我错了

我只证明了分解到最小的素数，但分解为3还是2我没考虑，现在看来结果应改为优先把3分解出去，还不知道怎么证明

N除以3余几
1.正好除尽，结果为3^(N/3)
2.余2，结果为3^(N/3)*2
3.余1，结果为3^(N/3-1)*2*2

作者: sqfasd 时间: 2013-06-30 11:26
根据3^2> 2^3
有
3^(2x) > 2^(3x)
令N=6X
3^(N/3) > 2^(N/2)

还不是很严谨，有些细节要补充，但大概说明了为什么分解为3要比分解为2，积更大

作者: pmerofc 时间: 2013-06-30 11:30
提示: 作者被禁止或删除内容自动屏蔽

作者: sqfasd 时间: 2013-06-30 11:35
回复 6# pmerofc

首先，分解的素数里，不能有3和2以外的数，如果有3和2以外的数，那么继续分解，肯定积更大
然后就是证明是主要分解为3还是主要分解为2，5楼已经证明了

作者: daybreakcx 时间: 2013-06-30 13:27
动态规划应该行的吧

#include <stdio.h>
#define MAX(x,y) ((x)>(y)?(x):(y))
int bst[17], prime[7] = {6, 2, 3, 5, 7, 11, 13}, i, j;
int main()
{
for (bst[0] = 1, i = 1; i <= 16; ++i)
for (bst[i] = -1, j = 1; j <= 6 && i >= prime[j]; ++j)
bst[i] = MAX(bst[i], bst[i - prime[j]] * prime[j]);
printf("%d\n", bst[16]);
return 0;
}

复制代码

作者: pmerofc 时间: 2013-06-30 13:56
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-06-30 14:06
提示: 作者被禁止或删除内容自动屏蔽

作者: daybreakcx 时间: 2013-06-30 14:29
回复 10# pmerofc

只是随手打了个项数，16内有6个素数

作者: idi0t 时间: 2013-06-30 15:19
...我发现自己连小学数学的水平都没有了

作者: 一介村夫 时间: 2013-06-30 17:11
本帖最后由一介村夫于 2013-06-30 17:17 编辑

很好算。
3*2=2*3，3^2>2^3。
任何正整数都可以写成：3k、3k+1、3k+2之一，或者换个写法：3k、3k+2、3k+4。
16=3*4+4，最大值为：3^4*2^2=81*4=324。

至于证明，也不难，只考虑5以上的整数，5以下的很容易验证。
任何偶数都可以表示成2n，2^n>2*n，当n>2时可以用数学归纳法证明。
任何奇数都可以表示成2n+3，2^n*3>=2n*3>2n+3也很容易用数学归纳法证明。

作者: pmerofc 时间: 2013-06-30 17:46
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-06-30 17:52
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-06-30 17:54
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-06-30 19:32
提示: 作者被禁止或删除内容自动屏蔽

作者: smalloc 时间: 2013-06-30 19:51
本帖最后由 smalloc 于 2013-06-30 19:52 编辑

x*y>x+y
x*y-x-y+1>1
(x-1)*(y-1)>1

见到比4大的就拆.大于等于6的偶数可以拆成2素数和（哥猜）
大于4的奇数就素数+偶数
不断增长，到唯一的最大值:2+3*n,2+2+3*n

作者: daybreakcx 时间: 2013-06-30 20:38
回复 15# pmerofc

动态规划没说特别适用于什么，只不过是一个方法，可以用上好用就OK

作者: pmerofc 时间: 2013-06-30 21:55
提示: 作者被禁止或删除内容自动屏蔽

作者: 晓得飞天千秋雪 时间: 2013-06-30 22:01

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

完全没头绪

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

作者: pmerofc 时间: 2013-06-30 22:32
提示: 作者被禁止或删除内容自动屏蔽

作者: selfrun 时间: 2013-07-01 00:06
尽量取最接近e值的整数，3最接近，就一直取3.
直接公式计算
a = (n-2)/3;
b = n - 3 * a;
ret = b * (3)^a

作者: 346196247 时间: 2013-07-01 08:30
我记得我明明是初中农民工啊，发现不懂

作者: cttnbcj 时间: 2013-07-01 13:01
即假设可将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-07-01 17:06
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-07-01 17:09
提示: 作者被禁止或删除内容自动屏蔽

作者: 晓得飞天千秋雪 时间: 2013-07-01 21:05

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

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

作者: cjaizss 时间: 2013-07-01 21:38

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 时间: 2013-07-01 22:40
回复 20# pmerofc

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

作者: shyixiu 时间: 2013-07-01 23:30
如果把这道题延伸一下,对于任意一个数将其分为n个数相加，那这n个数的乘积最大为多少（可以考虑分数）

作者: pmerofc 时间: 2013-07-02 07:18
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-07-02 07:20
提示: 作者被禁止或删除内容自动屏蔽

作者: selfrun 时间: 2013-07-02 08:45
1、
任意大于4的自然数n
恒有 (n - 3 ) * 3 > n;
所以，一旦连乘中某个因子n大于4，皆可化为 3 * (n - 3);
化解之后，因子只剩2 和 3;
2、
若因子2的个数大于2, 则 2 * 2 * 2 < 3 * 3;
故因子2的个数为0、1、2;

作者: cjaizss 时间: 2013-07-02 08:57
本帖最后由 cjaizss 于 2013-07-02 09:00 编辑

pmerofc 发表于 2013-07-02 07:18
回复 29# cjaizss

如果a是大于3的质数，那么分解成3和一堆2的和
则
a < 3*2*..2

作者: pitonas 时间: 2013-07-02 09:26
发现我自己没有小学数学的水平了。只是不知道这理解是否过于偏狭。

作者: pmerofc 时间: 2013-07-02 18:40
提示: 作者被禁止或删除内容自动屏蔽

作者: 晓得飞天千秋雪 时间: 2013-07-02 20:20
至于分解为多少个2呀、3呀的，参见 http://kan.weibo.com/con/3595708477867775

作者: pmerofc 时间: 2013-07-02 21:41
提示: 作者被禁止或删除内容自动屏蔽

作者: 晓得飞天千秋雪 时间: 2013-07-02 22:10

pmerofc 发表于 2013-07-02 21:41
回复 39# 晓得飞天千秋雪

以6为周期？不太理解什么意思。从 http://kan.weibo.com/con/3595708477867775 中的结果没看出什么周期呀。

作者: leejqy 时间: 2013-07-02 23:28
令F(n, m)表示数n被分解成最小素数为m时的若干素数之和的最大乘积，DP暴力过一遍素数。不过还是楼上提出的公式更简洁。

作者: pmerofc 时间: 2013-07-03 07:17
提示: 作者被禁止或删除内容自动屏蔽

作者: pmerofc 时间: 2013-07-03 09:34
提示: 作者被禁止或删除内容自动屏蔽

作者: 晓得飞天千秋雪 时间: 2013-07-03 19:16

pmerofc 发表于 2013-07-03 09:34
回复 41# 晓得飞天千秋雪

如果可以充分应用数学结论的话

(1) 如果是不利用数学推导结果，纯考程序员的水平，参见
http://kan.weibo.com/con/3595009719679031?_from=title

(2) 如果是利用一点数学推导结果，确实可简化程序，参见
http://kan.weibo.com/con/3595357355981754?_from=title
http://kan.weibo.com/con/3595708477867775?_from=title

(3) 如果是考数学推导水平，那程序就没什么可编的了，程序简单得可参见
http://kan.weibo.com/con/3596055519075881?_from=title

作者: 晓得飞天千秋雪 时间: 2013-07-03 20:20
数学证明结果

b45.png (12.97 KB, 下载次数: 23)

作者: pmerofc 时间: 2013-07-03 22:58
提示: 作者被禁止或删除内容自动屏蔽

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)