n元四则混合运算本原表达式数目

mathe

我写的程序现在通过一天多的计算可以算出56个数的表达式数目为:
331438867654187568666691714839142080436263217191398553623966122591469197445161254712579495051631735277151309436670594
但是就是不知道是否正确，最好有人能够使用不完全相同的算法，计算出结果可以相互验证一些其正确性。

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

这个题目我再给几天的时间吧，如果20号以后大家没有什么进展，我可以给一些提示。

mathe

我的程序中有一处错误 修改后发现程序运行速度快了非常之多 一秒钟之内可以到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的结果相同。

mathe

程序已经计算到
C[72]=32200580197805631001137422292933819863079790730942867939132940508354175846936385955924380183596983323886061295160879308202402095523142616014105653815891846090

无心人

你不要计算了
因为再大没经过验证
也不能算正确的了

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

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

显然，你们两个都看过那个帖子
所以你们两个一致是可能的
并不能100%说明你们两个一致就是正确的
当然也不能说明你们两个是错误的

mathe

我用的算法同他的方法不同的。不过100%可能性本来就很难确保，只是说这是很强的佐证而已。正确性主要还要靠算法本身来保证

无心人

是啊
这个问题的解太多了
天才如你也不能确定自己是否正确

mathe

程序运行速度比我估计的快多了，第100项是449917517701763281317016679046006077977987086161265203561131799463636866125482192454546567903120426734284631438483334078738257721979009093443435909627076270897944886935144957288232557564081388424946360387439835357455680511571869059290

mathe

关于这个题目，用五个数字情况作为例子，比如现在有一个表达式
$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

从我前面计算结果来看，如果能够算出n=40的，估计n=50也能很快算出来。
所以第一个计算出正确结果的应该能够拿走所有的900金币
不过虽然我将一些可用的想法公布了，实现这个算法还是有难度的

无心人

还是迷糊