【编程心得系列*24点】

写在前面：编程心得系列不谈具体问题的代码，只谈解决思路。

这是一个关于二十四点的软件。属于典型的先有目的再有初衷的软件。

在此之前我倒是写过一个解数独的软件。但那个的核心代码部分毕竟是抄袭的。这次是觉得对自己更有信心，也是想就此考验一下最近的编程学习，因而，挑选了看上去不是而很有难度的24点作为突破点，以此来在实践中进一步学习。

 

二十四点问题

输入：四个数字

操作：以不同顺序和不同符号不断匹配，直到算得24点并输出。

输出：是否可以算得24点，若可以，输出方法。

很自然的我想到如下方法，书写一个等式：

A？B？C?D=24  （？对应的是不同运算符）

不停的替换ABCD和运算符，佐之以不同括号位置，直到算出二十点为止。

最开始困惑我的主要方面在于——运算优先级。如果加减乘除还有括号放在了一个公式中，那么排序优先级别就是我首先应该做的事情了。左一个括号，右一个括号，需要讨论的括号分类非常多，而每种分类又只对应了很少量的类别。这种分类价值显得很低，用起来让人很不愉快。而且，要实现一个运算优先级的算法，也不是一个简单的操作。

 

否定了自己思路的我查看了网上诸多解算24点的算法。这些算法质量层次不齐，其中大部分就是不断进行分类，多者甚至可以分出十多个类别。

实在不想费尽心思去学习别人那低劣的算法的我，终止了对此问题的探索。

 

方法一

后来我和朋友D君一起散步。说明我的困惑（带着吐槽的目的）。他说，你思考的方法不对，他说，我给你四个数字，你算一下24点。

他给的四个数字是：

4 3 4 4

我说，这有何难啊。3加4得到7, 7乘以4得到28，28减去4等于24。

接着D君说，你算的时候，要进行复杂的分类么？

 

聪明，我暗中夸奖他。下边是他提供的思路的归纳。

解决24点算法之——基数扩充法。

说明：在四个数字中挑选一个数，将之当成基数，不断对其加减乘除其他数来修改他，直到将之修改为24点。

所以，以循环图的方式表示此过程，如下图。

For（在四个数字中挑一个数字A）

For（挑选计算符号Z1）

   For（在剩下的三个数字中再挑一个数字B）计算result1=JiSuan（A,Z1,B）；

     For（挑选一个计算符号Z2）

  For（在剩下的两个数字中再挑一个数字C）计算result2=JiSuan（result1,Z2,C）；

   For（挑选一个计算符号Z3）

    For（选出最后的数字D）{计算result3=JiSuan（result1,Z2,C）；if（result3==24）输出；}

 

基数扩充法虽然好，但无法包含所有可能。还存在一种可能。例如1 2 3 5，那么解决这个问题的最好方式就是（1+2）*（3+5）。显然的，这儿要进行两个基数扩充。所以，方法与上边一样。（请读者自己思考，并像上边那样写出流程图）

 

这个算法解决该问题需要计算：

这个数字可以说是相当的小，计算机完全可以在1ms内完成这个操作。

 

方法二

第一种方法已经很好。但后来，与另一个朋友小Z聊天，他看了我的算法，摇头说道：你这个方法不好，不具有通用性。

小Z问我：

为什么一定要从一个数字开始到算出24为止？为什么不反过来？能否考虑一下分治法（一种循环迭代的算法）？

 

高明，我一拍手，整理出了思路。

问题：将N个数字进行加减乘除得到24。

步骤：1.将两个数字合并为一个新的数字。（共存在相加，相乘，除以，减去，被除，被减6种可能）

2.将N-1个数字加减乘除得到24。

#当N=2，可以直接判断

 

那么，这样解决这个问题的总的执行次数就是：

可以看到，比第一种算法略多一些。但对计算机而言，这个数字仍旧相当小。但这段算法可以解决N个数算24点的问题，更具有通用性。

算法如下：

 

解决24点算法之——分治法。

Get24（长度为N数组）

{

If（N==2）就反复套加减乘除，判断是否可以为24点，若可，则输出。

If（N!=2）就从中选出两个数字，合并为为一个新的数字，并倒入一个新的数组，N-1数组，并对之调用Get24(长度为N-1的数组)；

}

 

 

最后是文末的一点总结。不得不感慨，一个好的算法真的是思维的火花。第一：开开脑洞，进行类比，换种方向思考，想想自己学习的数据结构知识。第二：对24点问题，还有其他问题，都要先想清楚思路，绘制好流程图然后再下手。第三：绝知此事要躬行。

望各位编程道路上的学习者不断总结，不断奋进。

 

2018.9.6