# 速算24点的实现与求解、有理数运算、表达式解析及其他 **速算24点的实现与求解、有理数运算、表达式解析及其他** ## 引言 [上一篇文章](../RZM_codeTable_and_other/detail.html "认知码码表及其导出过程") 提到我加__软驱一号__QQ群，其实最早加入这个群的目的很简单，就是想重温一下当年在步步高学习卡上玩过的游戏。 最主要想重温的游戏有两个，一个是速算24点，一个是原子对接。其中最让我怀念的还是原子对接这个游戏，这个下一篇文章再谈。本篇主要谈谈速算24点。 步步高速算24点游戏截图1：  步步高速算24点游戏截图2：  速算24点是个很经典的益智类小游戏，然而我最早接触确实是在步步高学习卡上。 游戏规则很简单，从一副扑克牌中任意抽取4张扑克牌，代表4个数字，利用这4个数字任意组合运用加、减、乘、除、括号运算，最终算得24。 这么描述是很抽象的，为了便于大家理解这个过程，先把已经实现的[游戏链接放到这儿](http://1157.huaying1988.com/24dian.html "速算24点游戏")，大家可以边玩游戏边看文章边理解。 速算24点游戏最终效果截图:  我在怀念这个游戏的时候，顺道给孩儿他妈介绍了一下这个游戏，她确实是第一次听说过这个游戏，于是引起了她的强烈好奇和兴趣。 在孩子各种捣乱和哭声的干扰下，我们还是介绍性的玩了几个回合，最后她表示这游戏“还行”。 在“还行”的鼓舞下，我决定实现一个速算24点的游戏，并完成自动求解过程，尽管内心对其实现还不是很有信心，但是迎接挑战还是挺令人振奋的。 ## 目录 [TOC] ## 最初的思路 最初的思路是这样的：四个数中先任意挑两个数进行运算组成一个子表达式，它跟剩下的2个数形成3个表达式，然后再任意挑两个表达式，再组成新的子表达式，最后与剩下的一个表达式运算形成最终结果。这个思路的好处是，很通用，很容易推广，所以最早的实现过程都是跟着这个思路走的，实现到后期才开始思考其他的实现方式，这用于解释当前有如此的底层实现积累的原因。 为了更好的解决两个数的运算时的减与被减、除与除以的问题，简化交换两数带来的不必要的困扰，在实现时对运算操作进行了扩展，由加、减、乘、除四则运算改为了加、减、乘、除、被减、被除这六种运算，于是，整个思路大体要遍历的算式数目为： $$ C\_{4}^{2} \cdot 6 \cdot C\_{3}^{2} \cdot 6 \cdot C\_{2}^{2} \cdot 6 = 3888 $$ ## 有理数运算 ### 为何非要实现有理数运算？ 由于为了让更多的人玩到这个游戏，更方便进行分享，我依然决定用JS来实现游戏的主要逻辑。而JS的基础运算是浮点式的，运算结果采用小数的形式，这个结果并不适合24点这个游戏的适应人群。 速算24点更多的是为中小学青少年学生锻炼四则运算能力而普及的益智类游戏，而在进行四则运算时，采用带分数形式要比小数形式更有亲和力。 当然，这也是为了实现我的一个儿时的梦想和愿望。话说在二十多年前，我还在上小学四五年级的时候，因为数学作业的问题总是很头大，于是开始投机取巧使用计算器。然而家用计算器有一个最大的问题就是，我们当时需要的计算结果是分数形式，而它总是给出一个小数形式的结果，这使得计算器对数学作业的贡献很有限。那个时候我就暗暗发誓，我长大之后，一定要搞个能做分数运算的计算工具，彻底解放数学题中分数计算的苦海。当然那时的想法虽然就跟贫困农民想当皇帝就是为了用上趁手的金锄头一样可笑，因为长大以后根本就不用做那些烦人的数学题了，但是，我还是觉得有必要了却一下这一心愿。 最后的原因就是，前段时间沉迷看《计算机程序的构造和解释》，原作《Structure And Interpretation Of Computer Programs》简称《SICP》，我英语不行，看的是机械工业出版社的中文译本，当然，尽管很沉迷，但是也才看了不到1/4。其中第2.1章节中有关于有理数运算的思路介绍，搞得我热血沸腾的，一时手痒，就想亲身实践一下。 SICP封面:  ### 有理数运算的实现 有理数运算的实现在[RatExp.js](http://1157.huaying1988.com/RatExp.js "有理数表达式运算库文件")中的第0~333行。 由于任意有理数都可以表达为分数形式，所以有理数的存储和运算都采用分数形式，主要存储三个参数：符号（正、负或0，用1、-1、0表达）、分子（整数）、分母（整数）。其中主要实现了分数的四则运算，运算本身都很简单，无非是加法多了些关于正负的判断，除法有关于被除数是否为0的判断，此处不再介绍。 有一点还是值得介绍一下，那就是分数每次运算完之后，形成新的分数时都要进行约分，约分就涉及到分子分母最大公约数的求解。我记得高一下数学必修三时学过的两种求解最大公约数的算法，至今记忆犹新：更相减损法、辗转相除法（又名欧几里德算法），此处用的辗转相除法，在文件的第5~16行，代码不多，结合算法描述很容易理解。 有了最大公约数的求解算法，约分就不是难事了，有了约分算法，分数的四则运算就不是难事了。然后再实现转字符串的算法，有理数的运算基本就完成了。 当然除了四则运算之外，还实现了有理数比较的方法，因为后面经常遇到数组排序之类的问题，大小比较的实现非常有必要。 但是，最后我还是给自己加了点难度，那就是实现小数转有理数的算法，尤其是其中关于无限循环小数转分数的算法。 话说，我从小学四年级一直到初中，一直都有一个疑惑，那就是无限循环小数如何根据循环节转换为分数形式，这个问题一直困扰我到初三，后来我哥高中的课本关于“等比数列”以及“极限”的介绍给了我一个思路，然后那个时候并不能完全理解其中的奥妙，一直到我上大学，学了极限、级数这一类的概念，我才对这件事有一个大体的认识（可见我反应有多慢）。想要了解这其中的奥妙其实也不难，也不用那么深奥的知识就能弄懂，说白了其实很简单： $$ \frac{1}{999 \cdots 9} = 0. \quad 00 \cdots 01 \quad 00 \cdots 01 \quad 00\cdots $$ 所以利用好这个999...9这个分母就可以构造任意位的循环小数。比如说0.181818...其中18是循环节: $$ 0.181818 \cdots = 18 \times 0.010101 \cdots = 18 \times \frac{1}{99} = \frac{18}{99} = \frac{2}{11} $$ 有了这些支撑，剩下的就好说了，我定义了有理数的字符串形式： 分数形式示例: -1&2|15,代表-(1+(2/15))的分数结果 小数形式示例：1.13#1,后面的1代表最后1位为循环节 然后分别实现了进行相应的字符串转换的方法。 这样实现儿时的愿望已经指日可待了。 ## 子表达式运算 子表达式运算对象原型的相关的实现在[RatExp.js](http://1157.huaying1988.com/RatExp.js "有理数表达式运算库文件")中的第333~567行。 当然它最初不是现在这个样子，主要涉及懒运算模式的添加之后就变成现在的样子了。而懒运算模式主要是为了实现后面的表达式参数运算。 最初的时候，子表达式对象在创建时直接计算表达式的值，并且存储，当调用获取方法时直接返回。 而参数运算时，真正用到的值在子表达式对象创建之后才传递，所以需要采用懒运算模式。 不过所用到的修改不过是给直接求值操作加了一层函数闭包，创建时只生成运算方法，不进行运算，调用获取方法时再调用进行运算。 ### 什么是子表达式对象？ 这个是我自己定义的一种对象，用于方便实现最初的思路。 子表达式可以表达一个有理数，可以表达两个有理数的运算，也可以表达两个子表达式的运算。 这样在挑选表达式组成新表达式时可以泛化有理数、运算和表达式的类型。 主要存储两个操作数和一个运算符，当表达一个有理数时，运算符直接指向该有理数对象，两个操作数分别都可以是有理数对象类型或子表达式对象类型。 ### 子表达式运算的实现 这个没啥好说的，真正大头的运算都在有理数运算那里实现了。此处主要是判断了一下类型，做了一下代理调用。 除了类型判断之外，还有一些小细节的判断，比如说“-”到底是代表负号还是代表减法等。 为了更好的做泛化计算，还提供了一个生成逆波兰式列表的方法，这个无非就是表达式树的后序遍历，咱也不搞堆栈遍历那么曲线的方法了，直接采用递归的方法一行代码实现了。 :stuck_out_tongue_closed_eyes: 最后，剩下一个还值得说说的那就是转为字符串的toString方法。这里面最复杂的判断要数是否需要加括号了。此处有一个小坑，我曾经踩过的，那就是常规的思路是先加减后乘除需要加括号，而加减或乘除的平级运算就不用了，当然这是错误的。比如说3-(4+5)这个运算，这里面的括号是不能省略的，否则就变成了3-4+5，计算结果就不对了。也就是说，对待减法和除法的时候，右运算表达式的括号是不能省的。 ## 表达式解析与有理数计算器 由于游戏中需要用户输入计算式，程序进行判断有效性以及结果是否等于24，所以就需要进行表达式的解析和运算。 运算部分上面我们都已经实现了，现在还差解析的部分。 ### 表达式解析 表达式解析的相关的实现在[RatExp.js](http://1157.huaying1988.com/RatExp.js "有理数表达式运算库文件")中的第569~696行。 #### 词法分析 这个没有写什么复杂的方法，仅仅就用了一个正则表达式：`/[\(\)\*\\\/\+\-\~\<\>\=]|[^\(\)\*\\\/\+\-\~\<\>\=]+/g` 这个正则表达式的构成很简单，那就是所定义的运算符单个是一个token，非运算符连续组合形成一个token。 因为运算表达式的构成很简单，除了运算符就是有理数，它是有理数和运算符进行有机组合的结果，那么非运算符连续组合token理论上一定就是一个有理数的表达。 而有理数的解析，其实就是有理数的字符串转换，上面已经实现了，直接套用就行。剩下的就是对于运算结构的解析了。 #### 语法解析 语法解析用的还是老一套的办法，还是状态机的状态转换矩阵，输入很简单，状态也很少，都是本人做解析时惯用的小伎俩，[前面的文章](../java_JSON_Resolver_instruction/detail.html "自己写的java版的json解析器详解")已经介绍过了，不再细说了。 然而这个矩阵对于解析运算结构用处不大，也没打算把它搞得那么复杂，只是用它来判断语法是否正确，并有利于发现并提示异常信息。 真正用来解析运算结构的方法其实还是数据结构中学到的方法，操作数栈和操作符栈： 遇见操作数直接作为有理数类型的子表达式压操作数栈，遇见操作符判断跟栈顶操作符的优先级，如果栈顶操作符优先级高，则直接弹出两个操作数与栈顶操作符组成新的子表达式压操作数栈，并回退新操作符到token列表中；如果当前操作符优先级低，则直接压操作符栈，最后直到token列表遍历结束，操作数栈中唯一的元素就是最终解析好的表达式。 ### 有理数的表达式计算器 表达式解析都已经实现了，不如我们来实现一个[有理数的表达式计算器](http://1157.huaying1988.com/RatCalc.html "有理数四则运算表达式计算器")吧！顺便验证一下上面所写的基础方法是否正确。 有理数四则运算表达式计算器 效果图:  至此儿时想要脱离分数计算苦海的愿望终于达成了。剩下的开始集中精力、快马加鞭的实现速算24点的核心逻辑了。 ## 带参数的表达式运算 带参数的表达式的相关的实现在[RatExp.js](http://1157.huaying1988.com/RatExp.js "有理数表达式运算库文件")中的第696~847行（末尾）。 这一块其实是后来又回来加的。因为实现到一半，发现一个问题：对于表达式的遍历其实只需要一遍就行了，剩下的不过是改变四个数的值并进行运算。 所以表达式对象本身应该是可以重复利用的，不应该每次都进行遍历重建，浪费CPU运算时间以及内存。 于是我在原来已经实现了的表达式运算库的基础上修修补补，楞是弄出来一个参数求值的对象原型。 由于这一块是后补的，事先没有考虑，其补丁特性就明显的多，本来终端运算数都是有理数，楞是用来表达参数序号了。理论上不会有太大问题，只是让人不太舒坦罢了。 继承了子表达式对象的原型，重新实现了它的一系列核心方法，在计算以及生成字符串时传递参数数组进行运算，核心算法除了取值方式的不同，一个是直接取值，一个是从数组中取值，其他大部分代码直接复制粘贴过来的。同时还提供了利用递归遍历生成真正的执行子表达式对象的方法。 至此，整个基础运算库的实现已经完成了，剩下的就是具体的关于速算24点的算法问题的研究了。 ## 速算24点求解算法的实现 速算24点求解算法本质上就是四则运算的算式遍历算法，便利并检查是否等于制定数值 ### 最初的想法的实现 由于最初的想法是采用组合取数的方式，所以一时技痒，先实现了一套求排列组合的计算方法，所使用的算法依然参考自《SICP》，自然也是用的递归。具体实现在[24dian.js](http://1157.huaying1988.com/24dian.js "速算24点运算库文件")中的第1~79。 而这个最初想法的实现就是“速算24点遍历方式1”，具体实现在[24dian.js](http://1157.huaying1988.com/24dian.js "速算24点运算库文件")中的第117~184。 真正的算法代码并没有这么长，也就一小段，其中有一大部分是对算式的有限去重。 去重主要考虑力所能及的两个方面（其他去重算法实在是心有余而力不足）：一个是最终字符串hash去重，用一个Map实现的，很简单；另一个是关于同级运算去重。 啥叫同级运算的去重呢？就是如果一个算式只有加减或者只有乘除，那么括号以及运算数的顺序就都不重要了，因为同级运算是满足交换律的。 举个例子，1+2-3-4和1-3-4+2以及1+2-(3+4)这三个算式其实是同一种情况的，也就是说，固定运算数的顺序，这样只需要遍历运算符就可以了。 ### 速算24点定制遍历算法的实现 最初的遍历算法能适应更复杂的情况，但是，当前情况下我们并不需要。当前我们更需要定制化的，符合需求减少计算量的遍历算法。 于是我便又实现了“速算24点遍历方式2（推荐）”，具体实现在[24dian.js](http://1157.huaying1988.com/24dian.js "速算24点运算库文件")中的第185~293。 它的思路是由上一个算法进行特化的来的：四个有理数中取出两个有理数数组成一个子表达式之后，第二次再取两个的时候有两种情况，一种是取得的两个都是有理数，另一种情况是取得一个有理数、一个子表达式。这也就是所谓的2+2和(2+1)+1这两种情况。由于我们把四则运算扩展成“六则运算”之后，运算数的左右在运算符的考虑范畴，所以省去了考虑1+(1+2)类似的镜像、手相或者对称等复杂情况。最终归纳后的结果就只有2+2和(2+1)+1这两种情况。 2+2情况还可以进行简化，那就是4个数取出两个数之后，剩下的两个数就立刻固定了，不用再取一次。 该算法的实现也采取了类似的去重方式，此处不再赘述。 ### 速算24点的一些辅助方法 生成一个索引序列数组，没啥好说的，[24dian.js](http://1157.huaying1988.com/24dian.js "速算24点运算库文件")中的第80~95。 返回对参数数组洗牌的函数闭包，没啥好说的，洗牌算法见[之前的文章](../generate_random_array/detail.html "C语言中的随机函数分析与生成m个不重复随机数算法比较")，[24dian.js](http://1157.huaying1988.com/24dian.js "速算24点运算库文件")中的96~111。 两个遍历参数表达式列表计算，并检查结果是否等于指定数值（24）的方法，一个检查到一个就立即返回，另一个检查参数表达式列表中所有的算式，返回所有计算结果正确的算式列表，没啥好说的，[24dian.js](http://1157.huaying1988.com/24dian.js "速算24点运算库文件")中的294~333。 检查表达式是否符合速算24的要求，[24dian.js](http://1157.huaying1988.com/24dian.js "速算24点运算库文件")中的333~399。这个还是需要说说的。 这个主要检查三类错误：表达式语法错误、表达式内容错误、表达式结果错误。 表达式语法错误主要包括参数异常、表达式语法解析异常、空表达式等。 表达式内容错误主要包含操作数不在参数列表中、操作符不在要求范围等。 表达式结果错误主要包含计算结果不等于指定数值（24）等。 检查结果返回一个数组，数组的第一项为检查结果true或false，前两类错误时第二项为错误描述信息，最后一类错误或者结果正确结果时第二项为解析后的表达式，只有最后一类错误有第三项，为该错误的描述信息。 ## 速算24点求解算法的验证 上面实现了这么多的算法，写了这么多的基础代码，还是需要验证一下的，顺便做一些统计和调查，满足一下好奇心。 ### 速算24点无解的数字组合 速算24点游戏中有一些组合是无解的，在玩步步高的游戏时也经常遇到此类情况，游戏中也提供了无解按钮。 而对于无解数字组合的对比最能体现算法的结果是否具有参考性，因为只要针对无解的情况不会误判，而针对有解的情况，只要至少求出一个正确算式作为参考，就不失为一个有效的求解算法。 于是，我写了如下代码进行测试： ```javascript function visitAll(num){ var rstList = []; var uniqueMap = {}; var expList = visitExp2(); // expList = visitExp1(); var calcList = null; // Math.pow(13,4) = 28561 for(var i=1;i<=13;i++){ for(var j=1;j<=13;j++){ for(var k=1;k<=13;k++){ for(var l=1;l<=13;l++){ var paramList = [i,j,k,l].sort(function(a,b){return a-b;}); if(!checkVal(expList,paramList,num)){ var nums = paramList.join(","); if(!uniqueMap[nums]){ uniqueMap[nums] = true; rstList.push(paramList); } } } } } } return rstList.sort(function(a,b){ for(var i=0;i<Math.min(a.length,b.length);i++){ if(a[i]!=b[i]){ return a[i]-b[i]; } } return a.length-b.length; }); } var num = 24; var list = visitAll(num); document.writeln("------------------------------------------------------------------------------------------<br />"); document.writeln("!="+num+"<br />") document.writeln("------------------------------------------------------------------------------------------<br />"); document.writeln(list.length+"<br />") document.writeln("------------------------------------------------------------------------------------------<br />"); document.writeln(list.join("<br />")); document.writeln("------------------------------------------------------------------------------------------<br />"); ``` 算得速算24无解的数字组合有458组，这与网上搜到的总数是一样的。 但是具体是不是这458组我没有进行验证，因为网上能搜到的详表都要么要会员VIP下载，要么要积分下载，要么要花钱下载，真是烦死了，一点分享精神都没有。 既然你们不愿意分享，那么就姑且认为我算得的就是正确答案吧…… 结果如下(为节约文章长度和用户滚轮的损耗，部分换行用“ | ”代替): ``` ------------------------------------------------------------------------------------------ !=24 ------------------------------------------------------------------------------------------ 458 ------------------------------------------------------------------------------------------ 1,1,1,1 | 1,1,1,2 | 1,1,1,3 | 1,1,1,4 | 1,1,1,5 | 1,1,1,6 | 1,1,1,7 | 1,1,1,9 | 1,1,1,10 | 1,1,2,2 | 1,1,2,3 | 1,1,2,4 | 1,1,2,5 | 1,1,3,3 | 1,1,4,11 | 1,1,4,13 | 1,1,5,9 | 1,1,5,10 | 1,1,5,11 | 1,1,5,12 | 1,1,5,13 | 1,1,6,7 | 1,1,6,10 | 1,1,6,11 | 1,1,6,13 | 1,1,7,7 | 1,1,7,8 | 1,1,7,9 | 1,1,7,11 | 1,1,7,12 | 1,1,7,13 | 1,1,8,9 | 1,1,8,10 | 1,1,8,11 | 1,1,8,12 | 1,1,8,13 | 1,1,9,9 | 1,1,9,10 | 1,1,9,11 | 1,1,9,12 | 1,1,10,10 | 1,1,10,11 | 1,2,2,2 | 1,2,2,3 | 1,2,5,11 | 1,2,7,13 | 1,2,8,11 | 1,2,8,12 | 1,2,9,9 | 1,2,9,10 | 1,2,10,10 | 1,3,3,13 | 1,3,5,5 | 1,3,7,11 | 1,3,10,13 | 1,3,11,13 | 1,4,4,13 | 1,4,7,10 | 1,4,8,10 | 1,4,9,9 | 1,4,10,13 | 1,4,11,11 | 1,4,11,12 | 1,4,11,13 | 1,4,12,13 | 1,4,13,13 | 1,5,5,7 | 1,5,5,8 | 1,5,7,7 | 1,5,11,13 | 1,5,12,13 | 1,5,13,13 | 1,6,6,7 | 1,6,7,7 | 1,6,7,8 | 1,6,7,13 | 1,6,9,11 | 1,6,10,10 | 1,6,10,11 | 1,6,11,11 | 1,6,13,13 | 1,7,7,7 | 1,7,7,8 | 1,7,7,13 | 1,7,8,13 | 1,7,10,10 | 1,7,10,11 | 1,7,11,11 | 1,7,11,12 | 1,7,11,13 | 1,8,8,13 | 1,8,9,9 | 1,8,9,10 | 1,8,10,10 | 1,8,11,11 | 1,8,12,13 | 1,8,13,13 | 1,9,9,9 | 1,9,9,10 | 1,9,9,11 | 1,9,9,13 | 1,9,10,10 | 1,9,10,11 | 1,9,12,13 | 1,9,13,13 | 1,10,10,10 | 1,10,10,11 | 1,10,10,13 | 1,10,11,11 | 1,10,11,13 | 1,10,13,13 | 1,11,11,11 | 1,13,13,13 | 2,2,2,2 | 2,2,2,6 | 2,2,5,13 | 2,2,7,9 | 2,2,7,11 | 2,2,8,11 | 2,2,8,13 | 2,2,9,9 | 2,2,9,13 | 2,2,10,12 | 2,3,3,4 | 2,3,9,11 | 2,3,10,11 | 2,4,7,13 | 2,4,9,11 | 2,4,11,13 | 2,4,12,13 | 2,5,5,5 | 2,5,5,6 | 2,5,7,12 | 2,5,9,9 | 2,5,9,13 | 2,5,11,11 | 2,5,11,13 | 2,5,13,13 | 2,6,7,7 | 2,6,9,13 | 2,6,11,11 | 2,6,13,13 | 2,7,7,7 | 2,7,7,9 | 2,7,8,10 | 2,7,9,9 | 2,7,9,12 | 2,7,10,13 | 2,7,11,11 | 2,7,11,13 | 2,7,13,13 | 2,8,11,13 | 2,9,9,9 | 2,9,9,10 | 2,9,11,12 | 2,9,12,12 | 2,10,10,10 | 2,10,12,12 | 2,10,13,13 | 3,3,3,13 | 3,3,4,10 | 3,3,5,8 | 3,3,5,11 | 3,3,7,10 | 3,3,8,11 | 3,3,10,10 | 3,3,10,11 | 3,3,10,12 | 3,3,11,11 | 3,3,13,13 | 3,4,6,7 | 3,4,7,13 | 3,4,8,8 | 3,4,9,10 | 3,4,10,11 | 3,4,11,11 | 3,4,13,13 | 3,5,5,5 | 3,5,5,10 | 3,5,5,13 | 3,5,7,7 | 3,5,8,10 | 3,5,9,11 | 3,5,11,13 | 3,6,7,11 | 3,6,8,11 | 3,6,10,13 | 3,7,7,11 | 3,7,8,10 | 3,7,10,12 | 3,7,11,13 | 3,8,8,13 | 3,8,10,13 | 3,8,11,13 | 3,10,10,10 | 3,10,10,11 | 3,10,10,13 | 3,10,11,11 | 3,10,12,12 | 3,10,12,13 | 3,10,13,13 | 3,11,11,11 | 3,11,11,13 | 3,11,12,13 | 3,11,13,13 | 3,13,13,13 | 4,4,4,13 | 4,4,5,9 | 4,4,6,6 | 4,4,6,7 | 4,4,7,11 | 4,4,9,9 | 4,4,9,10 | 4,4,9,13 | 4,4,10,11 | 4,4,11,11 | 4,4,13,13 | 4,5,5,11 | 4,5,5,12 | 4,5,5,13 | 4,5,9,11 | 4,6,6,11 | 4,6,6,13 | 4,6,7,11 | 4,6,7,13 | 4,6,8,11 | 4,6,9,11 | 4,6,10,13 | 4,6,11,13 | 4,7,7,9 | 4,7,7,10 | 4,7,7,12 | 4,7,7,13 | 4,7,10,13 | 4,8,10,13 | 4,9,9,9 | 4,9,9,11 | 4,9,9,13 | 4,9,10,10 | 4,9,11,13 | 4,9,12,13 | 4,9,13,13 | 4,10,10,10 | 4,10,10,13 | 4,10,11,11 | 4,10,13,13 | 4,11,11,11 | 4,11,11,12 | 4,11,11,13 | 4,11,12,12 | 4,11,13,13 | 4,12,12,13 | 4,12,13,13 | 4,13,13,13 | 5,5,5,7 | 5,5,5,8 | 5,5,5,10 | 5,5,5,11 | 5,5,5,13 | 5,5,6,9 | 5,5,6,10 | 5,5,6,12 | 5,5,6,13 | 5,5,7,9 | 5,5,7,12 | 5,5,7,13 | 5,5,9,12 | 5,5,9,13 | 5,5,10,12 | 5,6,6,11 | 5,6,6,13 | 5,6,7,10 | 5,6,7,11 | 5,6,8,11 | 5,7,7,7 | 5,7,7,8 | 5,7,7,12 | 5,7,7,13 | 5,7,8,11 | 5,7,8,12 | 5,7,8,13 | 5,7,9,9 | 5,7,11,12 | 5,7,12,13 | 5,8,8,11 | 5,8,8,12 | 5,8,9,9 | 5,8,9,10 | 5,8,10,10 | 5,8,10,13 | 5,8,11,11 | 5,8,12,13 | 5,8,13,13 | 5,9,9,9 | 5,9,9,10 | 5,9,9,13 | 5,9,10,12 | 5,9,11,11 | 5,9,11,12 | 5,9,13,13 | 5,10,10,10 | 5,10,11,12 | 5,10,11,13 | 5,10,12,12 | 5,11,11,11 | 5,11,11,12 | 5,11,11,13 | 5,11,12,13 | 5,11,13,13 | 5,12,12,12 | 5,12,12,13 | 5,12,13,13 | 5,13,13,13 | 6,6,6,7 | 6,6,6,13 | 6,6,7,7 | 6,6,7,8 | 6,6,7,13 | 6,6,9,9 | 6,6,10,10 | 6,6,10,11 | 6,6,11,11 | 6,6,13,13 | 6,7,7,7 | 6,7,7,8 | 6,7,7,9 | 6,7,7,12 | 6,7,7,13 | 6,7,8,8 | 6,7,8,13 | 6,7,9,10 | 6,7,9,11 | 6,7,9,13 | 6,7,10,11 | 6,7,13,13 | 6,8,8,13 | 6,8,10,10 | 6,8,12,13 | 6,9,9,9 | 6,9,9,13 | 6,9,10,10 | 6,9,10,13 | 6,9,11,11 | 6,9,13,13 | 6,10,10,11 | 6,10,10,12 | 6,10,11,11 | 6,10,11,13 | 6,10,13,13 | 6,11,11,11 | 6,11,11,13 | 6,11,13,13 | 6,13,13,13 | 7,7,7,7 | 7,7,7,8 | 7,7,7,9 | 7,7,7,10 | 7,7,7,11 | 7,7,7,13 | 7,7,8,8 | 7,7,8,9 | 7,7,8,10 | 7,7,8,12 | 7,7,8,13 | 7,7,9,9 | 7,7,9,11 | 7,7,9,12 | 7,7,9,13 | 7,7,10,10 | 7,7,10,11 | 7,7,10,12 | 7,7,11,11 | 7,7,13,13 | 7,8,8,8 | 7,8,9,9 | 7,8,9,11 | 7,8,10,12 | 7,8,11,11 | 7,8,13,13 | 7,9,9,9 | 7,9,9,10 | 7,9,9,11 | 7,9,9,12 | 7,9,10,10 | 7,9,10,13 | 7,9,11,13 | 7,9,12,13 | 7,10,10,10 | 7,10,10,13 | 7,10,11,11 | 7,10,11,12 | 7,10,13,13 | 7,11,11,11 | 7,11,11,12 | 7,11,11,13 | 7,11,12,12 | 7,11,12,13 | 7,11,13,13 | 7,12,12,12 | 7,12,13,13 | 7,13,13,13 | 8,8,8,8 | 8,8,8,9 | 8,8,9,9 | 8,8,9,10 | 8,8,10,10 | 8,8,10,11 | 8,8,11,11 | 8,8,13,13 | 8,9,9,9 | 8,9,9,10 | 8,9,9,11 | 8,9,9,13 | 8,9,10,10 | 8,9,10,11 | 8,9,13,13 | 8,10,10,10 | 8,10,10,11 | 8,10,10,13 | 8,10,11,12 | 8,10,11,13 | 8,11,11,11 | 8,11,11,12 | 8,11,11,13 | 8,11,12,13 | 8,11,13,13 | 8,12,12,12 | 8,12,12,13 | 8,12,13,13 | 8,13,13,13 | 9,9,9,9 | 9,9,9,10 | 9,9,9,11 | 9,9,9,13 | 9,9,10,10 | 9,9,10,11 | 9,9,10,12 | 9,9,11,11 | 9,9,13,13 | 9,10,10,10 | 9,10,10,11 | 9,10,10,12 | 9,10,11,11 | 9,10,13,13 | 9,11,11,12 | 9,11,11,13 | 9,12,12,13 | 9,12,13,13 | 9,13,13,13 | 10,10,10,10 | 10,10,10,11 | 10,10,11,11 | 10,10,13,13 | 10,11,11,11 | 10,11,13,13 | 11,11,11,11 | 11,11,13,13 | 13,13,13,13 ------------------------------------------------------------------------------------------ ``` ### 各组合计算结果统计 实现到这儿，不知道大家有没有过这么一个疑问，为何速算24点必须要算24？其他数值不行么？24宁有种乎？ 反正我是有类似的疑问……于是我就又写了一段代码来验证一下各结果的可算性，所有数字组合的运算中，哪个结果出现的次数最多？ 是不是有这么一个数，所有的组合进行四则运算后都可以算到这个数？24是不是真的比其他的数可算性更高？ ```javascript function visitAll(){ var rstMap = {}; var expList = visitExp2(); var calcList = null; for(var i=1;i<=13;i++){ for(var j=1;j<=13;j++){ for(var k=1;k<=13;k++){ for(var l=1;l<=13;l++){ calcList = [Rat.Int(i),Rat.Int(j),Rat.Int(k),Rat.Int(l)]; var elemMap = {}; for(var m=0;m<expList.length;m++){ var key = expList[m].value(calcList).toString(); if(!elemMap[key]){ if(key.indexOf(">")==-1){ var n = parseInt(key); if(n>=0){ elemMap[n] = true; if(rstMap[n]){ ++ rstMap[n]; }else{ rstMap[n] = 1; } } } } } } } } } return rstMap; } var data = visitAll(); var list = []; for(var k in data){ var n = parseInt(k); if(n>=0){ list.push([n,data[k]]); } } list = list.sort(function (a,b){return b[1]-a[1];}); console.log(JSON.stringify(list)); ``` 我列一下前100项吧，列表中第一列为制定数值，第二列为可以计算得到本数值的数字组合的个数（基数为 13的4次方 = 28561）, 为节约文章长度和用户滚轮的损耗，部分换行用“ | ”代替: ``` 2,27865 | 3,26675 | 4,26249 | 6,25702 | 5,25415 | 1,25317 | 7,24977 | 9,24880 | 8,24820 | 10,24740 | 12,24720 | 14,24169 | 15,24016 | 11,24003 | 0,23881 | 16,23643 | 18,23306 | 13,22999 | 20,22789 | 24,22615 | 36,21348 | 21,21189 | 22,21121 | 17,20995 | 28,20356 | 19,20314 | 30,20209 | 26,20160 | 40,19837 | 27,19652 | 48,19275 | 23,19132 | 32,19090 | 60,18955 | 25,18483 | 33,18216 | 72,17811 | 35,17761 | 42,17324 | 44,17305 | 29,16940 | 45,16881 | 39,16852 | 54,16267 | 31,16004 | 56,15930 | 34,15810 | 84,15322 | 80,15186 | 52,15099 | 38,15012 | 120,14945 | 90,14918 | 50,14786 | 37,14733 | 66,14693 | 70,14584 | 96,14232 | 55,14195 | 64,14162 | 63,13979 | 49,13723 | 78,13599 | 108,13571 | 51,13364 | 46,13310 | 43,13260 | 41,13224 | 65,13025 | 88,12678 | 47,12442 | 77,12198 | 57,12094 | 144,11780 | 75,11737 | 53,11718 | 68,11569 | 58,11544 | 100,11544 | 76,11284 | 62,11016 | 126,10984 | 59,10948 | 69,10942 | 81,10858 | 112,10854 | 104,10738 | 110,10736 | 132,10634 | 99,10611 | 180,10377 | 61,10306 | 91,10019 | 67,9918 | 105,9755 | 168,9644 | 140,9504 | 74,9396 | 85,9324 | 117,9318 | ... ... ``` 这个结果告诉我们，24并不是一个特殊的数字，甚至速算20点都比速算24点的效果要好一些，而效果最好的应该算是速算2点了…… :stuck_out_tongue_closed_eyes: 而24处于一个还凑合的一个状态，真是毫无可圈可点之处。 再利用上面计算无解的代码，我们让num=2，看看无解组合最少的2到底能少到什么程度吧。 结果如下(为节约文章长度和用户滚轮的损耗，部分换行用“ | ”代替): ``` ------------------------------------------------------------------------------------------ !=2 ------------------------------------------------------------------------------------------ 62 ------------------------------------------------------------------------------------------ 1,1,1,7 | 1,1,1,8 | 1,1,1,9 | 1,1,1,10 | 1,1,1,11 | 1,1,1,12 | 1,1,1,13 | 1,1,3,11 | 1,1,3,13 | 1,2,2,11 | 1,2,2,13 | 1,5,13,13 | 1,7,10,10 | 1,7,11,11 | 1,8,11,11 | 1,8,13,13 | 1,9,12,12 | 1,9,13,13 | 1,10,10,13 | 1,10,13,13 | 2,2,3,13 | 2,2,4,11 | 2,2,4,13 | 2,2,8,13 | 2,5,7,10 | 3,3,3,13 | 3,6,8,11 | 3,9,9,11 | 3,10,10,11 | 3,10,11,11 | 3,11,11,12 | 3,11,11,13 | 3,11,12,12 | 3,11,13,13 | 3,12,12,13 | 3,12,13,13 | 4,4,4,11 | 4,4,4,13 | 4,4,8,13 | 4,8,8,11 | 4,8,8,13 | 5,6,8,13 | 5,7,9,11 | 5,8,9,13 | 5,8,10,13 | 5,11,11,13 | 5,13,13,13 | 6,6,9,13 | 7,7,7,11 | 7,7,9,13 | 7,9,11,13 | 7,11,11,11 | 7,11,13,13 | 8,8,8,13 | 8,10,11,13 | 8,11,11,13 | 8,12,12,12 | 8,12,12,13 | 8,12,13,13 | 8,13,13,13 | 9,9,9,13 | 9,13,13,13 ------------------------------------------------------------------------------------------ ``` 2果然比24高到不知道哪里去了，只有62组无解组合，我觉得已经足够少了。 但是我觉得这些事还是不要较真了，毕竟我们只是在验证算法罢了，还是老老实实的继续实现速算24点而不是速算2点吧。 ### 速算24点求解器 搞了这么多，速算24点的求解器是说什么也要搞的。 当然，这也并没有太多需要解释的，因为该实现的上面都已经实现了，直接[点击链接](http://1157.huaying1988.com/24dianSolve.html "速算24点解算")玩(zuo bi)吧 速算24点求解器最终效果截图:  ## 游戏素材设计 首先，我想要一套扑克的图片素材，因为要做速算24点游戏，必然无法避开抽扑克牌这一最初最原始的形式。 于是我在网上搜了好多关于扑克的素材包。甚至连windows自带的空心接龙、蜘蛛纸牌游戏的资源我都扒出来了。 但是这些我都不太满意，因为这些素材要么下载需要VIP、花积分、花钱，要么有水印、不清晰，要么牌面全是广告，或者面临潜在的版权问题之类的。 于是想来想去，我为啥不自己设计一套扑克牌呢？有那么难么？ 说干就干，于是我很快就自己搞样式，生成了2~10的牌面花色。之后我就遇到了一个难题，那就是J、Q、K、A、JOKER的牌面设计以及牌背。 按照我最初的想法，J、Q、K是需要我自己用Inkscape分别临摹出来的，但是当我画了两张K之后，我放弃了，没有天赋，太难画了，而且对不齐，效率也低。 我花了两个星期的时间，才只[画了两张牌](http://1157.huaying1988.com/pukerK.svg "花两个星期画的方块K和梅花K")，之后我彻底放弃了这个思路。 于是我决定J、Q、K还是用[现成的素材](JQK.jpg "网上现成的JQK大图素材")吧！我对这张素材进行了加工，只取了其中方框中的小人的部分拼在一起做成拼图资源，以供使用。 之后A和JOKER以及牌背都是用现有的素材自己设计的，尽管不太好看，但是好歹我们努力过嘛。 于是这一切加以排列形成了我想要的[最终效果](http://1157.huaying1988.com/poker.html "扑克绘制")。 扑克牌素材设计最终效果截图:  由于字体原因，该页面在某些手机上显示效果不佳。为了保证最终效果，我要把该页面截图作为素材。 Chrome开发者工具中的截取节点屏幕截图真好用，一下子就满足[最终的素材](http://1157.huaying1988.com/puker.png "速算24点扑克素材贴图")要求了。 Chrome开发者工具审查元素截取节点屏幕截图演示：  ## 游戏的最终实现 最后游戏逻辑的实现还剩这么几部分： 游戏开始时的素材加载等待，[页面源码](http://1157.huaying1988.com/24dian.html "速算24点游戏页面源码")的第192~263行； 游戏摸牌的动画效果，[页面源码](http://1157.huaying1988.com/24dian.html "速算24点游戏页面源码")的第95~191行、404~437行； 游戏初始化，包括控制变量的初始化、页面元素的初始化、按钮事件的绑定等，其中按钮绑定的方法主要包括四类操作：校验用户输入、返回提示信息、记录解题日志、页面元素的显隐控制，[页面源码](http://1157.huaying1988.com/24dian.html "速算24点游戏页面源码")的第286~407行。 ### 动画效果的控制逻辑 这样整个游戏的实现就大体说完了，不过其中还有一部分我想说说，那就是动画效果的控制逻辑。为了完成每轮游戏开始时的摸牌动画，费了很大的功夫，不过好在顺利实现了。 我觉得结合JQuery的动画效果工具，我发明的这个动画队列框架结构还是可圈可点的。 由于JS的事件回调机制，JQuery的动画回调机制，如果想在动画结束时开始新的动画就很容易陷入回调地狱。深度的嵌套回调既不美观，也不方便调试。 有一种解决方法是自定义事件，动画结束时触发事件，这个方法解决了回调地狱问题，但是引来的新问题就是组织形式过于松散。 为了解决这一问题，我思考良久，最终确立了当前的方案，将回调函数以及参数列表队列作为参数传递给回调函数，这样在进行自我递归回调或者动画结束回调时结构都可以统一，各个动画效果独立，只要保持统一的回调形式，不管是调整动画效果的顺序还是动画效果的内部调整，都可做到互不影响，以队列的形式消解掉调用层次，并且组织形式集中。这是当前我能想到的较好的一种实现。 最后再放一遍: [速算24点的游戏链接](http://1157.huaying1988.com/24dian.html "速算24点游戏") 。 速算24点游戏最终效果截图:  ## 后话 ### 我印了一套速算24点的纪念扑克 我把为速算24点设计的扑克印出来了，就是用的这个[速算24点扑克素材贴图](http://1157.huaying1988.com/puker.png "速算24点扑克素材贴图")，然后再淘宝上定制印刷的。 本来游戏都做完了，除了写这篇博文也没有太多的念想了吧？ 但是我还是有些不甘心的，因为我为这个游戏还是付出了很多个不眠之夜的，总得留下点什么作为纪念吧…… 既然这套扑克的素材都已经设计完成了，而且费好大的的功夫，为啥不印出来做纪念呢？ 快递到货之后，不管印刷质量如何，还是挺感动的。 速算24点定制扑克-正面：  速算24点定制扑克-背面：  因为经验不足，尤其是牌背的设计还是有值得改进的地方的： 1.没有绘制一个正反对称的图案，导致牌背有正反，打牌时会有别扭感 2.牌背背景是白色的，跟正面区分度差，导致牌背产生牌面的错觉 这两点至少下次注意吧…… ### 后记的后记 后来这套扑克牌被我家娃用来玩“摆火车”游戏了，估计离被霍霍掉不远了……