mathe
发表于 2008-5-18 15:53:13
我写的程序现在通过一天多的计算可以算出56个数的表达式数目为:
331438867654187568666691714839142080436263217191398553623966122591469197445161254712579495051631735277151309436670594
但是就是不知道是否正确,最好有人能够使用不完全相同的算法,计算出结果可以相互验证一些其正确性。
我现在的程序瞬间可以找出前30多个数的表达式数目,但是现在57个数的情况计算10个多小时还没有出结果。所以看来通过我的方法几乎不可能计算出60个以上数形成的表达式数目了。
这个题目我再给几天的时间吧,如果20号以后大家没有什么进展,我可以给一些提示。
mathe
发表于 2008-5-18 16:12:33
我的程序中有一处错误:L 修改后发现程序运行速度快了非常之多:L 一秒钟之内可以到50多个数字的组合:L
前38项结果如下:
C=6
C=68
C=1170
C=27142
C=793002
C=27914126
C=1150212810
C=54326011414
C=2894532443154
C=171800282010062
C=11243812043430330
C=804596872359480358
C=62506696942427106498
C=5239819196582605428254
C=471480120474696200252970
C=45328694990444455796547766
C=4637556923393331549190920306
C=503098625119690529483557341038
C=57686378236198249477754157470490
C=6971076297272400341250040669733062
C=885532316307786635170088752281089442
C=117967788401738463374881818100959070526
C=16445399559629861638995118751838615658890
C=2394388146526813205842199208197945159230294
C=363438535354347849255586863651265085155154514
C=57415967926043855441291779032310196605057642382
C=9426133524288191649975794541642416464221753634170
C=1605892470434336124753633462782718847462434977514598
C=283535788712160231397105773156572511726335202133211778
C=51817176403698682418934847330130140043434994142439728734
C=9790736620274385472653442409692136509369525602095223692010
C=1910583990188250741827659750712804487764565919318550449135606
C=384670158108961656997511016042204787933415584961170038346164786
C=79830961312702309813993715094792198382026119593801220671092226478
C=17061914622026292165278814157773471110883857517765408856471507824090
C=3752259201245219720369090616780123850883428122740057990604266598355462
C=848441543450744189593664555296640279897790455600254558031785316637171042
后面不能在贴了,不然上面几个擂台赛的数据就不要挑战了。
现在结果应该没有错误了,同百度贴吧上的KeyTo9Fans的结果相同。
mathe
发表于 2008-5-18 16:17:07
程序已经计算到
C=32200580197805631001137422292933819863079790730942867939132940508354175846936385955924380183596983323886061295160879308202402095523142616014105653815891846090
:L
无心人
发表于 2008-5-18 19:21:32
你不要计算了
因为再大没经过验证
也不能算正确的了
另外,即使你和别人的一致
也不能说明你就是正确的啊
需要双盲测试,即两个人互相独立的看到这个问题
而且没有受到相同的思路的影响
显然,你们两个都看过那个帖子
所以你们两个一致是可能的
并不能100%说明你们两个一致就是正确的
当然也不能说明你们两个是错误的
mathe
发表于 2008-5-18 20:04:25
我用的算法同他的方法不同的。不过100%可能性本来就很难确保,只是说这是很强的佐证而已。正确性主要还要靠算法本身来保证
无心人
发表于 2008-5-18 20:07:10
:)
是啊
这个问题的解太多了
天才如你也不能确定自己是否正确
mathe
发表于 2008-5-19 09:19:38
程序运行速度比我估计的快多了,第100项是449917517701763281317016679046006077977987086161265203561131799463636866125482192454546567903120426734284631438483334078738257721979009093443435909627076270897944886935144957288232557564081388424946360387439835357455680511571869059290
mathe
发表于 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:没有使用任何负号的表达式
mathe
发表于 2008-5-21 15:25:10
从我前面计算结果来看,如果能够算出n=40的,估计n=50也能很快算出来。
所以第一个计算出正确结果的应该能够拿走所有的900金币:lol
不过虽然我将一些可用的想法公布了,实现这个算法还是有难度的:lol
无心人
发表于 2008-5-21 19:52:42
还是迷糊