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金币 不过虽然我将一些可用的想法公布了，实现这个算法还是有难度的

无心人

还是迷糊