“粑粑，跟我玩一下算24吧！刚赢了外公，一点挑战都没有……”

嘿，小样！才学会乘除法了不起了？

“走开走开，粑粑没时间！”

“哼！我们一人十张牌，看你赢不赢得了我！”

嘿，还用激将法！来就来，谁怕谁！想要赢我，至少得等你六……五，啊，不，四年级才行！

Ten minutes later……

“啊！不会吧！你居然赢不了小骞？”老婆轻蔑地看着正抱头叹气的我说，“你研究生不会是假的吧？”

“呃……状态不好……最近老加班……”

“哈哈……粑粑……那下次我只拿四张牌？”

……

不就是算24吗？你赢得了计算机吗？老爸跟你玩算法！

穷举法

穷举法的基本思想是根据题目的部分条件确定答案的大致范围，并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。若某个情况验证符合题目的全部条件，则为本问题的一个解；若全部情况验证后都不符合题目的全部条件，则本题无解。穷举法也称为枚举法。

用穷举法解题时，就是按照某种方式列举问题答案的过程。针对问题的数据类型而言，常用的列举方法一有如下三种：

（1）顺序列举：是指答案范围内的各种情况很容易与自然数对应甚至就是自然数，可以按自然数的变化顺序去列举。（如上一讲的线性查找算法）

（2）排列列举：有时答案的数据形式是一组数的排列，列举出所有答案所在范围内的排列，为排列列举。（如第一讲中列举的排列组合排序算法）

（3）组合列举：当答案的数据形式为一些元素的组合时，往往需要用组合列举。组合是无序的。

算24的穷举法

算24是随机取1～13间的4个数字，通过＋、－、×、÷四则运算计算出24为赢。这显然可以采用组合列举法，穷举所有4个数字及四则运算的排列组合。

记4张牌为a、b、c、d，计算符号用*表示（可为＋、－、×、÷），则根据计算顺序，可以表示为如下五种情况：

（（a*b）*c）*d

(a*(b*c))*d

a*（b*（c*d））

a*（（b*c）*d）

（a*b）*（c*d）

每种情况中有三个符号计算，对＋、－、×、÷运算遍历三次，可以得到运算结果。考虑到小数减大数为负的情况，最后取绝对值为24就是正确的计算过程。

上代码！

算24的Scratch实现

“计算”积木

根据符号来计算A和B的值，并写入到“得数”变量。

“算法”积木

对应上述情况1（（a*b）*c）*d的实现∶

如果得数绝对值为24，则加入到计算结果列表。

后面的实现类似：

计算(a*(b*c))*d

计算a*（b*（c*d））

计算a*（（b*c）*d）

计算（a*b）*（c*d）

上面几步都可以直接用得数变量作为中间运算结果，但这一步，需要将中间计算结果保存起来，再做计算。

初始化数据

开始计算吧

计算完成后通知小猫说结果。

试一下效果∶

再来一个∶

嘿，真不赖！你算出了吗？

小结

穷举法在算法设计中被大量应用，常用于解决“是否存在”或“有多少种可能”等问题。其中许多实际应用问题靠人工推算求解是不可想象的，而应用计算机来求解，充分发挥计算机运算速度快、擅长重复操作的特点，穷举判断，快速简便。

“来来来，小骞！和计算机玩一局算24？你要是能赢，我把牌吃了！！”

“哼！用计算机算什么本事！”

嘿，还反了天了！你老爸就靠这个吃饭的！不然你哪来的东西吃，哪来的新衣服穿！

“去！跟计算机玩十把！赢不了就没饭吃……”

“小气鬼粑粑……”