数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

[擂台] n个数字通过加减乘除括号得到不相等的表达式数目

[复制链接]
 楼主| 发表于 2008-5-18 15:53:13 | 显示全部楼层
我写的程序现在通过一天多的计算可以算出56个数的表达式数目为:
331438867654187568666691714839142080436263217191398553623966122591469197445161254712579495051631735277151309436670594
但是就是不知道是否正确,最好有人能够使用不完全相同的算法,计算出结果可以相互验证一些其正确性。

我现在的程序瞬间可以找出前30多个数的表达式数目,但是现在57个数的情况计算10个多小时还没有出结果。所以看来通过我的方法几乎不可能计算出60个以上数形成的表达式数目了。

这个题目我再给几天的时间吧,如果20号以后大家没有什么进展,我可以给一些提示。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-18 16:12:33 | 显示全部楼层
我的程序中有一处错误 修改后发现程序运行速度快了非常之多 一秒钟之内可以到50多个数字的组合
前38项结果如下:
C[2]=6
C[3]=68
C[4]=1170
C[5]=27142
C[6]=793002
C[7]=27914126
C[8]=1150212810
C[9]=54326011414
C[10]=2894532443154
C[11]=171800282010062
C[12]=11243812043430330
C[13]=804596872359480358
C[14]=62506696942427106498
C[15]=5239819196582605428254
C[16]=471480120474696200252970
C[17]=45328694990444455796547766
C[18]=4637556923393331549190920306
C[19]=503098625119690529483557341038
C[20]=57686378236198249477754157470490
C[21]=6971076297272400341250040669733062
C[22]=885532316307786635170088752281089442
C[23]=117967788401738463374881818100959070526
C[24]=16445399559629861638995118751838615658890
C[25]=2394388146526813205842199208197945159230294
C[26]=363438535354347849255586863651265085155154514
C[27]=57415967926043855441291779032310196605057642382
C[28]=9426133524288191649975794541642416464221753634170
C[29]=1605892470434336124753633462782718847462434977514598
C[30]=283535788712160231397105773156572511726335202133211778
C[31]=51817176403698682418934847330130140043434994142439728734
C[32]=9790736620274385472653442409692136509369525602095223692010
C[33]=1910583990188250741827659750712804487764565919318550449135606
C[34]=384670158108961656997511016042204787933415584961170038346164786
C[35]=79830961312702309813993715094792198382026119593801220671092226478
C[36]=17061914622026292165278814157773471110883857517765408856471507824090
C[37]=3752259201245219720369090616780123850883428122740057990604266598355462
C[38]=848441543450744189593664555296640279897790455600254558031785316637171042

后面不能在贴了,不然上面几个擂台赛的数据就不要挑战了。
现在结果应该没有错误了,同百度贴吧上的KeyTo9Fans的结果相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-18 16:17:07 | 显示全部楼层
程序已经计算到
C[72]=32200580197805631001137422292933819863079790730942867939132940508354175846936385955924380183596983323886061295160879308202402095523142616014105653815891846090
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-18 19:21:32 | 显示全部楼层
你不要计算了
因为再大没经过验证
也不能算正确的了

另外,即使你和别人的一致
也不能说明你就是正确的啊

需要双盲测试,即两个人互相独立的看到这个问题
而且没有受到相同的思路的影响

显然,你们两个都看过那个帖子
所以你们两个一致是可能的
并不能100%说明你们两个一致就是正确的
当然也不能说明你们两个是错误的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-18 20:04:25 | 显示全部楼层
我用的算法同他的方法不同的。不过100%可能性本来就很难确保,只是说这是很强的佐证而已。正确性主要还要靠算法本身来保证
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-18 20:07:10 | 显示全部楼层


是啊
这个问题的解太多了
天才如你也不能确定自己是否正确
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-19 09:19:38 | 显示全部楼层
程序运行速度比我估计的快多了,第100项是449917517701763281317016679046006077977987086161265203561131799463636866125482192454546567903120426734284631438483334078738257721979009093443435909627076270897944886935144957288232557564081388424946360387439835357455680511571869059290
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-21 15:21:56 | 显示全部楼层
关于这个题目,用五个数字情况作为例子,比如现在有一个表达式
$a-(b*c-(d+e))$
这个表达时最外层计算是加减计算,而且,我们发现可以通过去掉部分括号将其他一些加减也提升到最外层,比如上面表达式可以写成:
$a-b*c+d+e$
在这些括号去除以后,我们可以发现,所有在最外层的加减计算都是可以交换计算顺序的,比如上面这个表达式同下面几个都等价:
$a+d+e-b*c$
$-b*c+a+d+e$
所以如果允许第一个数字前面也添加正负号,那么所有最外层计算中,我们只需要考虑每一项的符号,而不用管它们的顺序。
而如果需要考虑第一项不允许添加负号,由于各项之间顺序可以任意安排,所以只要至少有一项是正的,我们就可以表达出来。
所以像上面的表达式,我们可以看成分组
$(b*c, a, d, e)$
里面,每一组都添加正号或负号然后求和的所有可能,其中不允许所有的都选择负号。
所以上面分组用加减号连接最多有15种不同的可能$2^4-1$

同样,如果表达式最外层运算是乘除运算,我们考虑表达式
a/((b+c)/(d*e))
同样,我们可以把它改写成
a/(b+c)*d*e
类似前面,我们把这个表达式看成分组
$(a, b+c, d, e)$
通过乘除运算组合到一起中的一种,组合过程中,每个数可以选择用作乘数或除数,但是不能够所有的数都选择为除数。
所以上面的分组用乘除号连接最多有$2^4-1$种不同的连接方式.

现在我们来看第三种特殊的表达式
a/(b-c)+d*e
这个表达式同
d*e-a/(c-b)
也是等价的,但是这种等价关系前面的分析过程无法得出,主要原因在于对于某个连乘式:
$x_1x_2..x_t$和$y_1y_2...y_t$
如果两个连乘式中对应项绝对值都相同,那么最后乘积也必然相等或互为相反数。

所以我们需要对所有结果为互为相反数的项做特殊处理:
可以发现,对于一个分组的加减组合中我们允许第一项也添加负号,那么对于每个表达式,我们总可以找到和它互为相反数的一项。
所以我们可一将互为相反数的项看成等价的表达式,最后计算出总数目,然后在总数目上乘2就可以了(因为对于最后的表达式,也是每个表达式,其相反数必然可以构造出来)
而对于最终的表达式,如果它的相反数不能表示出来(不允许第一项添加负号的情况下),容易看出,只能表达式中没有用过减号。所以我们可以通过分别计数情况1:第一项允许添加负号;情况2:没有使用任何负号的表达式
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-5-21 15:25:10 | 显示全部楼层
从我前面计算结果来看,如果能够算出n=40的,估计n=50也能很快算出来。
所以第一个计算出正确结果的应该能够拿走所有的900金币
不过虽然我将一些可用的想法公布了,实现这个算法还是有难度的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-21 19:52:42 | 显示全部楼层
还是迷糊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-3-26 07:47 , Processed in 0.099607 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表