24点算法：思考与记录

2024-07-14 00:50| 来源: 网络整理| 查看: 265

24点算法：思考与记录 前言

突然回想起小时候玩扑克牌时常玩的游戏，24点。四张扑克牌，可以随意用加减乘除运算进行组合，最终能凑成24，是一个考验心算的小游戏。于是就想尝试用计算机实现，看看有多少种可能，不过24点是很容易穷举的，可能性并不多。最终程序跑出来，一共有28561种组合，其中22615种都可以凑出24点，成功率有79.1%。

枚举分析

以下的分析法比较朴实，但实际上编码实现比较复杂。我个人在编码过程中将组合处理成字符串，最后再基于字符串进行计算，会用到中后缀表达式，比较复杂，但这里还是做一个保留，就当作一个记录吧。

24点基础模型可以以▯◌▯◌▯◌▯表示，四张牌三个运算符，但由于运算符优先级不同，还引入了括号的枚举，因此增加了复杂度。仅仅四张牌三个运算符的排列组合可以很快穷举，而加入括号的组合，一下子就复杂起来了，下面我们进行括号的分类讨论。

我们根据括号进行枚举分类：这部分因为四张牌括号组合比较少，可以手工完成。

无括号：▯◌▯◌▯◌▯ 一对括号：(▯◌▯)◌▯◌▯、(▯◌▯◌▯)◌▯ 两对括号：(▯◌▯)◌(▯◌▯)、((▯◌▯)◌▯)◌▯

其他括号组合都是无意义的，读者可以自行尝试。例如三对括号(▯)◌(▯)◌(▯◌▯)等价于(▯◌▯)◌▯◌▯，(▯◌▯◌▯◌▯)也没有意义。

接着，我们就可以将数字和运算符填充进▯◌▯◌▯◌▯模型中。简单分析可以知道，数字填充一共有4*3*2*1=24种组合，运算符组合有4*4*4=64种组合，那么模型一共就有64*24=1536种组合，对应五种括号模型，故判断一个四数组合能否凑成24点，最多需要判断1536*5=7680个组合。

对于运算符填充的枚举，还有一定的优化空间，因为高优先级的运算用括号括起来是没有意义的。举例说明，(▯◌▯)+(▯*▯)实际上就等价于(▯◌▯)+▯*▯，这会产生重复枚举，所以对于局部模式(▯◌▯)，其运算符填充为*或/都是没有意义的，剔除这一部分会使组合数降低至4992种。

那么到此我们就完成了枚举分析，我们可以先枚举数字，然后再枚举五种括号模式，最后填充运算符。

注意！计算是实数计算，并不是整数计算，如果使用整数计算10/9*12*2=24显然是错误的。

更简单的枚举分析

当完成上述的分析过后，之后偶然看到Leetcode上有类似的题目（679.24 点游戏），看了人家的思路，发现他编码实现容易得多，我自己的方案差不多用了200行才实现，官方题解只有50行。

这种方案避开了括号组合，简单来说，就是四个数字挑出两个进行四种运算，剩下三个数字，再挑出两个进行四种运算，最后剩两个数字进行四种运算。实际上我也考虑过这个方案，但是陷入定性思维觉得这样穷举不了，简单想了一下就略过了。回头来想，这个方案不就是人心算的过程吗。

有兴趣的可以看看官方题解，或者自己尝试进行编码。

代码实现

两两运算的实现代码：

int TARGET = 24; double EPSILON = 1e-6;//由于是浮点运算，需要一个误差范围 int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3; bool judgePoint24(vector &nums) { vector l; for (const int &num : nums) { l.emplace_back(static_cast(num)); } return solve(l); } //回溯算法，当列表里只有一个元素的时候，代表已经完成了四数运算 bool solve(vector &l) { if (l.size() == 0) { return false; } if (l.size() == 1) { return fabs(l[0] - TARGET) < EPSILON; } int size = l.size(); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (i != j) { //l[i]和l[j]为取出的两个数 vector list2 = vector(); for (int k = 0; k < size; k++) { //将没取到的数放入list2中，留作后续计算 if (k != i && k != j) { list2.emplace_back(l[k]); } } for (int k = 0; k < 4; k++) { //剪枝操作，加法和乘法有交换律，去重 if (k < 2 && i > j) { continue; } if (k == ADD) { list2.emplace_back(l[i] + l[j]); } else if (k == MULTIPLY) { list2.emplace_back(l[i] * l[j]); } else if (k == SUBTRACT) { list2.emplace_back(l[i] - l[j]); } else if (k == DIVIDE) { //如果除数是0，运算一定不成立 if (fabs(l[j]) < EPSILON) { continue; } list2.emplace_back(l[i] / l[j]); } //继续回溯 if (solve(list2)) { return true; } //弹出l[i]和l[j]的计算结果，尝试下一种运算 list2.pop_back(); } } } } return false; } 文章作者: Yuan. 文章链接: /archives/24game 版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yuan.！力扣算法微信扫一扫上一篇下一篇评论 | 0条评论

【本文地址】

公司简介

联系我们