让计算机来做多点妙算
原创 零零爸爸 零的奇妙世界 6月4日
上周，我应邀给一所小学的多点妙算活动出了一套比赛题，并给参赛的学生们做了一个关于如何编程来解多点妙算的小讲座。好多年不上讲台，又是第一次给小学生做讲座，开始还颇有些紧张，好在最后反响不错。
下面是我事后整理的幻灯片及讲稿，供喜欢多点妙算游戏的孩子和家长参考。想立即玩上游戏的可以直接拖到本文最后。
图片
很⾼兴来到这⾥和同学们交流⼀下玩多点妙算的⼼得。在座的都是做多点妙算的⾼⼿，今天我准备的内容，不是我们怎么做多点妙算，而是怎么让计算机来做多点妙算。
图片
⾸先我们看看计算机擅长做些什么。
⼤家都可以想到的⼀点，顾名思义，就是它的计算能⼒很强，算得超级快。第二呢，计算机能存⼤量的数据，不管什么形式的，存得下，找得到。第三点，就是计算机听话。它本身没有智⼒，就听我们的，你写程序指挥它⼲什么它就⼲什么。
再然后呢，第四点是什么？我觉得没了，它就这么点本事。
有的同学可能会说，计算机很聪明的，⼈⼯智能下围棋已经能下赢最厉害的围棋选⼿了。但是它怎么下赢的呢？其实还是我们给计算机写了⼀些⼈⼯智能的算法，然后⽤它计算快的特点，靠它⾃⼰⼤量的左右互搏的对弈，去学习了神经⽹络中⼤量的参数，然后记住，最后对弈的时候⽤出来了。本质上还是上⾯这三条，没有什么额外的秘密。
让计算机做多点妙算的难度和下围棋的难度是有天壤之别。有的同学可能已经开始学编程，有的还没有。我希望今天我讲完之后，即使还没开始学编程的同学，也能基本掌握我讲的内容。
图片
在让计算机做多点妙算之前，我这⾥有⼀个题，⼤家花30秒钟想⼀想，想到⼀种解法之后再去多想⼀两种。3，6，7，12，13算88。
……
好了，时间到。右边我给出了所有计算过程中不需要⽤到分数⼩数的解法。现在希望⼤家回顾⼀下，⾃⼰是怎么想到其中的⼀种或者⼏种的？
（学生回答：先找一个接近的数字，凑出来之后再看剩下的牌能不能凑到结果）
对，这些就是我们思考的⽅法。靠猜，靠凑，靠自己的数感去摸索，然后就做出来了。
图片
那计算机怎么做？
前面说过，它很笨的，没有数感，也不会推理，不会试探，不会猜测，只会算。怎么办？它虽然能算，但是不知道该去算什么呀！没关系，你不是算得快吗？那就⽤最笨的⽅法，把所有可能的式⼦可能的解法都去计算⼀遍吧！
图片
先看看一道多点妙算题要算多少个式⼦。
五个不同的数字，放在综合式的五个位置上，那就是120种放法；然后中间插⼊四个运算符，有256种插法；最后是这四个运算，先算哪个后算哪个，不同的运算顺序，有24种。
最后把它们乘起来，737280个式⼦，对计算机来说⼩菜⼀碟。
更何况也不全是73万个，⽐如如果数字重复怎么办？有两个数字⼀样的话，那最前⾯就不是120种了。甚⾄极端情况，如果五个数字都⼀样呢，那120种就变成了1种。⽐如五个10算101，⾃⼰去做一下就会发现，不需要考虑数字顺序了，因为数字都⼀样，只要考虑运算符和运算顺序就可以了。
所以不是所有的题⽬都是737280个不同的式⼦的，这是个最⼤值，⼤家记住就⾏。我后⾯⼏⻚有很多地⽅为了方便，直接写了这个数字，我就不每次都申明⼀下了。
图片
有的同学可能已经发现了⼀个问题。就是这么多个式⼦，其实好多都⼀样啊。
⽐如如果都是加法，那数字怎么排序，计算顺序怎样，都没任何影响。⼤家⼀眼就看出来了，因为我们知道加法有交换律结合律。但是我们笨笨的计算机不知道。
再来⼀个例⼦，⽐如这个式⼦，先算两个括号的哪一个，结果是⼀样的，甚⾄两个括号交换顺序成后⾯这个式⼦，还是没区别。计算机还是不知道。
那怎么办？第一个办法是写很多程序去教会计算机去判断式子是不是重复，但是这个难度实在太⼤了，我觉得我未必能完全做对。另一个方法就很容易，反正总共就73万，让它傻算就是了！
图片
那我们就可以写程序了。
⾸先我们写⼀个功能模块，就是让这段程序实现⼀个解多点妙算题的功能。这个功能模块在不同的编程语⾔⾥有不同的名字，有叫函数，过程，模块，⼦程序，等等，⽆所谓，反正就是⼀段程序能做⼀件事情。这段程序需要⽤它的⼈给五个数字，外加⼀个⽬标数。
最开始⽣成737280个运算式。具体怎么⽣成不是我们今天关注的重点，不同的编程语⾔都有⼀些排列组合的函数可以⽤来做这个。虽然我就写了简单的一句话，实际上写成程序没有这么简单。
然后做⼀个循环，在这里循环的意思就是把所有这些运算式⼀个个按顺序拿出来。每次拿出一个就去计算⼀下结果。我在这里就写了⼀⾏，其实前面⽣成的这个运算式未必是计算机能看懂的，所以真的写这个程序的时候，也有⼀些⼯作量。
算出结果之后去比较看这个结果是不是想要的⽬标数，如果是，那就可以了，不需要把剩下的式⼦都算完，直接把算出来的这个式子返回就可以了。如果不是，那就继续这个循环，算下⼀个式⼦。
最后要是所有的式⼦都算完了，还是没有，怎么办，就返回⼀个这题⽆解。
这就是今天我讲的第⼀个内容，怎么让计算机来做⼀道多点妙算题。特别简单粗暴是不是？
学生提问：这个程序每次运行是不是会返回一样的结果？怎么返回不同解？
回答：如果这里不退出让它继续算，就能得到所有解。如果只想每次得到一个不同解，那就在生成所有运算式之后给它们随机排个序，就像洗一下牌一样。
图片
下个问题就⽐较有趣了。
我在设计这个游戏卡牌的时候，必须要知道的⼀件事情，就是随便抽⼀个数再抽五张牌，有多少题是可以解的？多点妙算这个游戏很好玩，也能培养数感，但是要是每次抽⼀题都是⽆解，那可能也没有不会有⼈喜欢玩了。所以在设计完这个游戏，把它推出之前，我需要知道在所有的多点妙算题目里，有多少是可解的。
⽤⼀副扑克牌算24点，所有组合中⼤约是75%左右能有解，这个游戏⾄少不能⽐24点还少吧。
图片
首先开看一下总共有多少种不同的题目。26张牌抽5张，有⼏种可能？⼀道很典型的排列组合题。分三种情况讨论。
如果五张都不同，就是C(13,5)，如果有⼀对，相当于我们先从13个数字⾥选1个重复的，然后剩下C(12,3)，如果有两对，那就是选两对重复的，C(13,2)，剩下单张11种可能。全部加起来，5005种。
所以多点妙算的题目就有5005乘以101这么多道，似乎也不是很多。
图片
既然这样，程序就很好写了。因为前⾯写过⼀个解多点妙算题的功能模块了，可以直接拿来⽤。
先⽣成5005种题⽬数字，然后循环，从1开始算到101，每组数字都算，如果算不出来，我们的⽆解数量就加1，最后全部算完，我们就知道有多少题⽬⽆解了！特别简单。
假如我们每道题平均0.2秒能算出结果，总共要算多久呢？做个乘法就知道是一天多。今天放学回去开始运⾏这个程序，电脑不关，明天睡觉前应该就有结果了。觉得太慢了吗？
图片
那么来看看问题出在哪⾥。
这是前⾯那个⼯作得很好的模块。每次计算完会判断⼀下结果是不是⽬标数是吧？如果不是呢，就什么都不做，看下⼀个算式。这⾥有很多浪费。⽐如我开始给五个数字要算1，没算出来，第⼀个式⼦算了个99，继续；下次要算2，还是算出99，不对继续，直到真要算99了，这次计算才有⽤。但是这已经反复算了好多次了，每次都⽩⽩浪费了时间。
所以这⾥得到了⼀个经验，就是写程序的时候可能有⼀些现成的功能模块可以直接⽤，但是如果这个模块的实现和你现在想做的事情不完全匹配，就有可能降低程序效率。做数学题也⼀样，可能会学到⼀些解题套路，看到题直接套上去，也许可以做出来，但很可能不是最好的做法。
图片
知道问题之后就可以改进了。
这次的模块，功能再不是解一道题了，⽽是给你五个数字，返回从1到101之间的整数中有⼏个能算出来的。
和刚才的模块⽐，每次计算完之后，不是判断对不对。如果结果是我们想知道的，1到101之间的整数，那就放进可解的集合⾥。
（学生插话：这是个数组吗？回答：用数组的话你最后需要判断重复。我用的是集合。集合的特性就是没有重复的元素的，所以你⼏种⽅法算出⼀个结果，也不会被重复计数。）
最后就是把这737280个式⼦都算⼀遍，看看集合⾥有⼏个结果，这就是有⼏个结果是可解的了。
图片
有了这个新的模块之后，就只要循环5005个题⽬数字组，把有解数量加起来，就是有解的题⽬总数了。
回想刚才的做法，循环次数是101乘以5005次，这⾥101没有了，只需循环5005次就可以了！
当然，也有⼀些代价。之前的模块只要找到解就退出来了，绝⼤部分时候不⽤把73万个式⼦都算完，⽽现在，则⼀定要算完。
所以假设现在每次算完需要的时间是以前的5倍，需要1秒钟，那总共的耗时也缩短到了1个多⼩时。如果是⾃⼰写着玩，想知道答案，那这个速度是可以接受的了。
图片
如果觉得1个小时还是太长了，想精益求精，还能不能更快呢？我给⼤家介绍⼀种新的⽅法，这次要从另⼀个⻆度来看问题。比较前面的两种方法，为什么第二种能快这么多？因为它减少了大量重复计算的式子。所以如果想更快，就需要继续去掉更多的重复运算。
前面提及的所有方法，我们都是把一个运算式当作一个整体来看待，估算了需要计算多少个运算式。而事实上，一个算式并不是一个整体，它是由4次运算组成的。前⾯的所有⽅法，一个式子⼀定是做4次运算。然而这里就有很多运算是重复的。⽐如这里的两个例⼦，算完前面的这个式⼦之后再算后⾯这个，⼤家都知道，最后⼀步做⼀遍就⾏了，前面的(a-b)×(c+d)不需要再去计算。但是计算机不知道啊，前面的程序还是4次运算反复算。
所以就可以产生⼀个⼤胆的想法，我们要是把所有中间结果都存下来的话，是不是能算得更快呢？毕竟计算机两⼤优点，算得快，存得多，我们只⽤了第⼀个。这次我们可以尝试⽤上第⼆个优点，⽤更多的存储空间来换取计算时间，让程序更快地算出结果来。
图片
从最简单例⼦看起，⼀张牌，1，能算什么？只能算1，2只能算2，3只能算3。
两张牌呢？1和2能算⼏？1+2，1-2，2-1，1*2，1/2，2/1，⼀共6个数。还有没有？为什么⼀定没了。因为1只能算1，2只能算2。
假如临时改变一下游戏规则，可以在数字前随便添加负号会怎么样？这时候1和2是不是能算出更多的结果？因为1可以算1和-1，2可以算2和-2了。所以此时不仅要把1和2做六次计算，还要把-1和2，1和-2，-1和-2都做这样的计算，最后把结果放在一起。
简单地说，完整的操作就是从1能算出的结果集合⾥，取⼀个数，从2能算出的结果集合⾥，取⼀个数，把所有这样的组合取法都做加减乘除六种计算，这六个结果就是1和2两张牌能算出的全部结果。我把这个操作定义个符号，⽅便后⾯写式⼦。
同样⼤家可以⼿算出别的两张牌都能算出⼏来。如果是两个⼀样的数，就是四次运算，结果中还必然有0和1。
图片
继续看三张牌的情况，⽐如[1, 2, 3]。能算出⼏？
可以有⼏种算法，可以先拿[1, 2]去算，然后把所有结果去和3做加减乘除，也可以先算[2, 3]最后和1去算，也可以先算[1, 3]最后和2去算。最后把所有结果放⼀起，就是[1, 2, 3]的可能的结果了。去掉重复的，29个结果。这个可以⼿算，不过并不推荐。
再看个简单的例⼦，[1, 2, 2]。那就只有两种做法，⼀种先拿[1, 2]去算，结果再去和剩下那个2做计算，⼀种先算两个2，结果去和1做计算。结果也会少一些，17个不同的。
这些计算算完之后，都需要保存下来。
图片
牌再多也⼀样。[1, 2, 3, 4]四个数字，直接看最后⼀步运算怎么算？是先算完三个数字的结果，去和剩下那个数字算，还是先算两组两个数字的结果，最后拿它们来计算？也就是说，我们需要把四个数字分成两组，分别知道它们能算出什么数，然后分别把它们能算出来的数分别拿出来做最后⼀次计算。写下来就是这七种情况，⼀共能算出230种不同结果。
五个数字也⼀样，分成两组，⼀共15种分法，都算⼀遍合并起来就⾏了。我让程序算了[1, 2, 3, 4, 5]，⼀共有2144种不同结果。然后看⼀下我们关⼼的1～101在不在这2144个结果⾥？有94个数在，7个数不在。
计算机做这些事情，耗时远远不到1秒。
图片
现在⼜到了程序时间。
这次的模块叫这些数字能算出⼏。这些数字，不⼀定是5个，可能是⼀个两个三个四个，如果只有⼀个，那就只能算出它⾃⼰。否则呢，就先找到能把它们分成两组的分法，这也不难。数字不同的话，两个数字就是1种，三个数字就是3种，四个数字就是7种，五个就是15种。
然后对每⼀个分法，先看看分成的两组数字，前⾯有没有被计算过，知不知道它能算出⼏来。如果不知道，那就先⽤这个模块算⼀下。这个模块⾥在调⽤⾃⼰，术语叫递归。
在有了两组数字分别能算出⼏的两个⼤集合之后，就可以对它们分别进⾏循环，保证第⼀组结果⾥的每个数和第⼆组结果⾥的每个数两两都配对做⼀次和差积商六次运算。最后把所有这些结果的集合，也就是最开始给功能模块的的那些数字可以求得的所有结果，保存下来。
图片
有了这个功能模块之后，就可以循环所有的5005种数字组，然后在结果集合⾥找1～101，看看能找到多少个就⾏了。
这个⽅法还有⼀个好处，就是它其实是把所有这组数字可以求得的结果都存下来了，所以你想看看算任何⼀个数，⽐如999或者1/2能不能算出来，不会增加任何计算复杂性，最后查找的时候顺便判断⼀下就可以。
这个程序要运⾏多久？随着保存的结果越来越多，它会越算越快，总共只需要不到1分钟，就能得出结果，和前⾯的算法⽐，上百倍的效率提升。
那么这个程序运⾏的时候实际上占⽤了多少存储空间呢？前⾯说要利⽤计算机存得多的特性，⽤存储空间来换时间。⼤家刚才也看到了我们保存了所有的中间结果的数字。先看总共存了多少组数字的结果？就是所有1，2，3，4，5张牌的可能组合，7202组，这个数字可以⼿算，相信大家都很容易算出来。每组能算出多少个结果？前⾯说了[1,2,3,4,5]这五张牌能算出2000多种结果，这是五个不同数字⾥⽐较少的，多的能上万。最后总共是存了三千万出头个数字，对计算机来说，根本不算什么。
当然如果要想再省也很容易，程序保存所有结果的目的是什么？是为了重复使⽤，⽽五张牌的计算结果不会被其他式⼦重复⽤到，可以不需要存下来，改⼀下程序，算完直接查⽬标数就⾏，⼀点也不影响程序速度。于是存储空间可以降到⼀百万个数字以内。⼀百万个数字什么概念呢，⽐你⼿机拍张照需要的储存空间还要⼩得多。
图片
总结⼀下。我今天讲了⽤计算机来解题算得快，存得多的两个优势来做多点妙算。可以做⼀道指定的题，也可以让计算机判断所有的多点妙算题是不是有解。如果把后⾯那个程序稍微改⼀下的话，还可以顺便把解也都给出来，⼤家之后可以⾃⼰想想怎么改。今天我没有给出任何语⾔的真实代码，因为我觉得今天讲的这个问题，实际上是⼀个数学问题，你只要在数学解法上弄明⽩了，不管你会什么语⾔都应该可以写出程序来。
最后说些题外话，我⼤概就是像你们这么⼤的时候，开始接触编程的。放到现在看不算早，但是在三十年前⾮常稀有。学着学着就发现计算机太厉害了，如果你能写好程序，那他就是你的⼀个⾼性能外挂，可以在⽇常⽣活中帮你解决各种问题。之所以说是外挂，是因为解决问题的⽅法，⽐如算法啊，决策啊，数学模型啊，还是要⾃⼰思考⾃⼰研究的，然后计算机就帮你更快地计算，并且处理规模更⼤的问题，就像你⾃⼰玩游戏开了外挂⼀样，它不能替代你的脑⼦，但是能成为你的好助⼿。
到了中学我就没有继续钻研数学竞赛，⽽是选择去参加信息学竞赛了。数学竞赛是⽤⼤脑去解⼀些数学问题，信息学竞赛是⽤⼤脑，外加⼀个⾼级助⼿，去解另⼀类数学问题，我个⼈更喜欢这种感觉。所以归根到底，如果想更好地利⽤计算机去解决问题，最重要的还是学好数学，打好数学基础。
在最后的提问环节，学生提了不少很有意思也很有深度的问题。我最喜欢的是这个：如何找到所有必须使用分数求解的题？当时我的回答是在第二种方法基础上，在每个式子计算的时候判断一下这个式子计算过程中有没有用到分数，加点简单优化就是只判断带除法的式子。其实也可以在第三种方法的基础上靠额外存储一些信息来解决，和最后留的思考题难度差不多。