杭州网站维护,搜狗竞价,社交模板网站建设,辽宁建设工程信息网投标制作软件4月12日更新 先给结论吧 花了近一周时间用JavaScript完成了24点去重算法#xff0c;源码提交到了github上#xff1a;auntyellow/24 #xff0c;可以在线试#xff1a;gives you all dissimilar solutions.在1到13范围内的四数组合中#xff0c;不重复解最多的组合是2、4… 4月12日更新 先给结论吧 花了近一周时间用JavaScript完成了24点去重算法源码提交到了github上auntyellow/24 可以在线试gives you all dissimilar solutions.在1到13范围内的四数组合中不重复解最多的组合是2、4、8、1010 8 4 2 24(10 - 4) × 8 ÷ 2 24(10 × 4 8) ÷ 2 24((10 2) × 8 ÷ 4 2410 × 2 8 - 4 24(10 - 2) × 4 - 8 248 × 4 - 10 2 24(8 ÷ 4 10) × 2 24(8 × 2 - 10) × 4 24(10 - 8 ÷ 2)) × 4 2410 × 4 - 8 × 2 24只能用分数来解的(16个这里不给答案了有兴趣可以自己练练)1, 3, 4, 61, 4, 5, 6 (这题居然有两解都必须用分数的)1, 5, 5, 51, 6, 6, 81, 8, 12, 122, 2, 11, 112, 2, 13, 132, 3, 5, 122, 4, 10, 102, 5, 5, 102, 7, 7, 103, 3, 7, 73, 3, 8, 84, 4, 7, 75, 5, 7, 115, 7, 7, 11其他有难度的就是中间过程必须有大数的(大于36就很难一下子想到了)(像a × b - a × c 24这种形式比如10、12、12、12其实并没有太大难度就没有列进去)1, 7, 13, 136, 12, 12, 131, 6, 11, 136, 11, 12, 125, 10, 10, 131, 5, 11, 115, 10, 10, 114, 8, 8, 134, 4, 10, 104, 8, 8, 116, 9, 9, 103, 8, 8, 103, 5, 7, 133, 6, 6, 111, 2, 7, 75, 8, 9, 135, 9, 10, 114, 7, 11, 134, 9, 11, 114, 10, 10, 116, 7, 7, 113, 5, 8, 135, 5, 8, 112, 3, 13, 13还找到一个难的3、7、9、13它有两种解法一种用到了分数一种有大数。为了验证这些结论还是查到了 常成 那边包括 理论 - 24理论 解决二十四点 (我的算法跟这里相当接近了)、所有独立解 24理论 解决二十四点 (解法最多的牌型确实有11个解)需要分数的解 24理论 解决二十四点 (确实有16个牌型)看来程序是没太大问题了。 然后说说算法 参考了本题 小于0 的回答还有 24点算法如何给出所有不同的答案 - 萝卜的回答 - SegmentFault 总之就是列出所有不等价表达式例如 (( a b ) * c) / d 和 (( b a) * c ) / d 是等价的需要去重。虽然是重复在做很多人以前做过的工作但还是有些自认为别出心裁的思路因为并没从代数形式上做分析而是通过试数的办法做的试的是π、e、lnπ和arctan e这四个超越数对近似值做比较(浮点数运算总是有误差的)来判断两个表达式是否等价。(我把近似度设定在1e-6其实算是碰巧蒙对了SegmentFault的萝卜指出lnπ/(e π/arctan(e))和π/e - lnπ/arctan(e)只相差7.9e-6如果把近似度再提高1个数量级结果可能就不对了。)5种括号型(((oxo)xo)xo、(ox(oxo))xo、(oxo)x(oxo)、ox((oxo)xo)、ox(ox(oxo))其中o代表数字x代表运算符)4个数一共有24种排列3个符号一共有64种排列总共需要“试数”的表达式总共有7680个在这些表达式中找出了1170种不等价的也和网上能找到的资料相吻合例如 小于0 给我推荐的 A140606 - OEIS 。后来发现仅仅用这1170个表达式是不够的还要考虑以下14种牌型a, a, b, c // 两个相同的数可以交换也可以抵消a, a, b, ba, a, a, ba, a, a, a1, a, b, c // 1可以舍去1, a, a, b1, a, a, a1, 1, a, b1, 1, a, a1, 1, 1, a2, 2, a, b // 2 2 2 × 2这个算重复解应该说得过去2, 2, a, a1, 2, 2, a2, a, a, b // 2 × a - a (a a) ÷ 2这个居然被我算成重复解了另外还有a、a(a1)、b、c这种牌型需要把(a-a)参与乘除运算的解法排除掉然后单独算bc、b*c有没有可能等于24。所以程序里绝大部分逻辑都是在判断牌型到底属于上面列出来的15种当中的哪一种写得相当啰嗦。另外还有一些小问题比如1、1、5、5只给出了一种解因为对牌型1、1、a、a组成的表达式来说 (a1)(a-1)和a*a-1*1是等价的没有考虑4/2和4-2等价的问题例如2、4、6、6(6-(4-2))*6和(6-4/2)*6被认为是两个不等价的解(凭什么22和2*2等价但4-2和4/2不等价)当2作为中间步骤时没考虑22和2*2的等价还拿2、4、6、6说事(6-42)*6和(6-4)*2*6是不等价的解(写到这里我真后悔把22和2*2算做等价了)仔细想想还真不能轻易认为222*2、4-24/2是等价解法要是真这么算的话那么我们可以写出(6-4/2)*6 (6-(4-2))*6 (6-42)*6 (6-4)*2*6显然每个等号左右两边都是等价的。但要说最左边的和最右边的是重复的解法那又说不过去了。看似很简单的问题本以为可以花半天时间搞定的结果编码、测试、验证、优化一系列过程居然花了1周的时间再次印证了我的盲目乐观 :-( 更早的回答 我在SegmentFault上提了一个相似的问题问完才发现知乎上已经有了。很快就有人给出漂亮的解答了24点算法如何给出所有不同的答案 - 萝卜的回答 - SegmentFault 起初答题者思路跟 小于0 的回答类似后来发现穷举太麻烦就改用符号代数在Mathimatica里用10余行代码搞定了真让我吃惊。另外对于重复解的定义还是有挺大争论的比如我认为2x2和22应该算是雷同的但很多人并不认同。转载一下Clear[game24]game24[input_List,result_:24]:Block[{add,sub,mul,div},With[{oprules{add-Plus,sub-Subtract,mul-Times,div-Divide},specifics{div[x_,1]:x,mul[x_,1]:x,mul[1,x_]:x,add[2,2]-mul[2,2]}},Map[RightComposition[Hold,ReplaceAll[oprules],ToString[#,InputForm],StringDelete[{Hold[,]}],StringReplace[{*-\[Times],/-\[Divide]}]],Union[Select[result(#/.oprules)]Groupings[Permutationsinput,{add,sub,mul,div}-2],SameTest-(0Simplify[sub[#1,#2]//.specifics/.Prepend[oprules,k_Integer:ToString[k]]])]]]]用符号add、sub、mul、div分别对应加减乘除四则运算构建二叉树代表算式。Groupings函数生成了所有可能的表达式二叉树。Select筛选出计算结果符合要求的。Union负责除去雷同的算式。它的SameTest选项计算两个代数式的差化简后是否为0。注意这里通过把数字转为字符进行“符号化”了而且对数字1、2进行了特殊处理(specifics)。最后Map负责把每个算式转成字符串输出。测试
