24点游戏7节课--第1节-游戏介绍与基本算法

迷南。 2022-07-05 15:28 165阅读 0赞

这仅仅是一个控制台（DOS窗口下）的小游戏——有人欢喜有人烦了。欢喜的是因为可以专心于游戏逻辑自身过程，就算你只学过C++简单的屏幕输入输出(cin 、cout )，乃至换用java，C\#也可以写这个小程序。甚至用的是C的printf/scanf也问题不大，这个程序基本不用去考虑“面向对象”的问题。烦的人是正好他想学习高级的游戏编程，比如2D甚至3D(Direct X / OpenGL)啊，或者至少有图形用户界面，比如MFC或wxWidgets啊……这个就另外学习了。

这个游戏会用到boost::thread，也就是需要有个后台线程——又有人欢喜又有忧愁了。欢喜的是这游戏才算有点意思嘛，后台线程……估计是会搞个人机对战吧？忧愁的是，很多人说我不会编译boost啊……呵呵，自行解决吧。如果一时不想编译，也没关系，线程会相对后才使用。

最后一句废话，这系列文章虽然在本处归为“《白话C++》”下，但为了适合在网上（这样没有上下文的情况下）发表，做了大量的修改，包括分章，还包括代码（被粗暴地）简化，因此和最后书里的内容相差很大。

**（一）****游戏规则介绍**

言归正传，先谈下我们要实现24点游戏规则（有很多注意点，别跳过）：

A    基本玩法：出4张牌（不含大小鬼），然后用“加减乘除” 组合计算这四个数，能算出24就算得解。

B   虽然我们的算法能支持，但我们要故意禁掉在计算过程中，会出现小数的算法，比如这四张牌：5 、5、 5、1 的某种算法：（5 - 1/5 ）/5，不被我们接受，因为会让它显得不像是给人玩的游戏（我家小朋友不喜欢）。

C  我们不会让计算过程中，出现负数。原因之一类同B，读小学的小孩不会这么算。原因之二是它其实没有必要。对于24点游戏，带负数的计算过程，可以转换为不带负数的，比如： (4 - 5 + 9) \* 3，可以转换为： (9 - 5 + 4)  \*  3。

** ****（二）****算法考虑**

我只用过两种算法计算24点，其一是“知识库”法。是我当学生时的作品。大致是将可能计算出24点的算式，先全部列出来，比如：a+b+c+d, a+b+c-d, (a+b)\*(c-d) 等等……事实上也不多，20几个就够了。

然后针对每一个算法，再进行穷举法，像初中的代数，把四个数不断代入到算式，形成一个表达式，再计算出来结果是24。

这种方法当然比完全穷举要高效得多，但以当前的计算机运算能力，但穷举法也不过在毫秒之间，所以不是很有所谓。

当初用这个方法……倒是因为人机竞争中，我为给“机器人”设置了几个角色，比如“哭鼻子大王”，“马虎王”，“机器猫”等等，不同的角色拥有不同的计算能力，比如“哭鼻子大王”代表一位二年级学生，所以他就只拥有那些不带乘除运算的算式……

如果要用这个方法，就得需要一个表达式求值的功能，比如给一个(9 - 2) \* 2 + 9，能够算出它是23 ——当然在C++中，这样的库多乎其多……实在要自己写一个也可以，但为了简化，我们不想碰表达式求值的东东，也不想再引入其它库（除了boost::thread）。

另一个方法是纯粹的穷举法，也称为“暴力法”。

首先一个事，要先悟到：对于四个数计算，括号"（和"）"在穷举过程其实可以有效规避，从而仅仅变成两种计算方式。

先说第1种：从左向右，两个数两个数地计算，比如：1+2+3+4,可以分解为这样三步：1+2=>3   3+3=>6  6+4=>10。

注意！这个过程是不需要考虑优先级的，比如：1 + 2 \* 3 - 4，计算过程还是仅仅从左到右：1 +2 =>3

，3 \* 3 =>9 , 9 -4 =>5，即运算过程是：(1+2) \* 3 - 4。那存在优先级计算的1 + 2 \* 3 – 4何时计算？不要紧，因为我们是穷举，所以必然会有机会计算这个： 2 \* 3 + 1 – 4，耤以我们强大的小学算术知识，可以知道它就是1 + 2 \* 3 – 4——这样一想，我们这个算法很英明了，因为它可以避免出现大量的重复答案。

不过，有没有漏洞，有噢，因为是4个数，所以，类似  （1+2） \* （3+5）,这样先计算两头，再用中间的操作符处理左右两个（临时）结果，最终得出结果的，没办法换成那种不需要考虑优先级的计算式来的……不过幸好，对于四个数组合，也就这一种特例。（得出一个小提示：如果题目变成5个数或6个数，或更多数，我们的算法就不能直接改几个值就想使用的，不过我们现在对写一个超级通用算法不感冒）。

结论是：拿到一个表达式，我们分别用两种方法进行计算。

例如：存在算式：1 + 2 \* 3 +5 ，则两种方式计算：

第一种，我们称为“连贯式计算”，（代码中用“consecutive”表示，别问我为什么），得到 14。看本文到现在，你必须搞懂这个14是如何得来的。真不懂？答：((1+2) \* 3) + 5

第二种，我们称为“分隔式计算”，（代码中用“separate”表示，很想问我为什么？因为我就懂这个词），得到24。如何得来？答：(1+2) \* (3+5)。

推而广之：我们用n1..4表示四个操作数，用\_o1..3\_ 表示中间三个算符，则有：

算式：n1  \_o1\_  n2  \_o2\_  n3  \_o3\_  n4，要计算其值，我们仅通过以下a,b两算式计算：

a:   ((n1  \_o1\_  n2)   \_o2\_   n3) \_ o3\_  n4

b:  (n1  \_o1\_  n2)   \_o3\_   ( n3  \_o3\_  n4)

n1..4 是拿到手四个数，\_o1..3\_ 则是从四个操作符（\+、\- 、 \*、 /）挑出三个操作符，并且可以重复，比如可以挑出3个加号，或者2个减号1个除号等等。有学过高中数学的，可以回忆一下排列组合的知识。

就算回忆不出高中数学知识，也不要紧，反正我们是不讲理的，是要用暴力解决问题的……所以剩下的问题，就是如何把真实的数字及操作符不断地放入到那7个位置上，方法当然就是循环，就是最强的暴力穷举工具：for，来一段示例代码：

Code:

1.  int calc\_24(int num\[4\])  //\[4\]中的那个‘4’，你知道，我也知道是无用的...仅为了好看...
2.  \{  
3.      int n\[4\];  
4.        
5.      /\*开始丑陋的多层循环...如果用OO，是可以换成一个可遍历的对象来解决...但...算了吧 \*/
6.      /\* 只会让实际代码更多并且更不直观\*/  
7.      for (int i1=0; i1<4; ++i1)  
8.      \{  
9.          n\[0\] = num\[i1\];  
10.           
11.         for (int i2=0; i2<4; ++i2)  
12.         \{  
13.             if (i2==i1)    //第二张牌不能和第一张一样  
14.                 continue;  
15.           
16.             n\[1\] = num\[i2\];  
17.           
18.             for (int i3=0; i3<4; ++i3)  
19.             \{  
20.                 if (i3 == i1 || i3 == i2) //第3张...同样要绕过前面两张  
21.                     continue;  
22.                       
23.                 n\[2\] = num\[i3\];  
24.                   
25.                 int i4 = 6-i1-i2-i3;  //最后一张当然不用挑...  
26.                                                      //因为..可以计算出来  
27.                   
28.                 n\[3\] = num\[i4\];  
29.   
30.                  //... 现在，我们准备好（一次）四个数了...  
31.                  //下面应该开始摆放3个操作符了...以后说...  
32.              \}  
33.          \}  
34.     \}  
35. \}

(黑色注释部分是我用来自我解释的……还有像‘数组’入参没有检查边界等等...)

看得懂这段代码，就可以准备看第2节……看不懂，那得复习C或C++去，还可以google搜索下，网上谈24点算法很多，估计我这个不算什么另类的。

布置一个作业： 在下节开始之前，或许你应该把这段代码写完：再准备一个数组（o\[3\]），用来从4个操作符里，挑出3个来存着。

（后续：第2节……）   [http://student.csdn.net/space.php?uid=112600&do=blog&id=34327][http_student.csdn.net_space.php_uid_112600_do_blog_id_34327]

\-------------------------------------------------------------------------------

如果您想与我交流,请点击如下链接成为我的好友：  
[http://student.csdn.net/invite.php?u=112600&c=f635b3cf130f350c][http_student.csdn.net_invite.php_u_112600_c_f635b3cf130f350c]

[http_student.csdn.net_space.php_uid_112600_do_blog_id_34327]: http://student.csdn.net/space.php?uid=112600&do=blog&id=34327
[http_student.csdn.net_invite.php_u_112600_c_f635b3cf130f350c]: http://student.csdn.net/link.php?url=http://student.csdn.net%2Flink.php%3Furl%3Dhttp%3A%2F%2Fstudent.csdn.net%252Finvite.php%253Fu%253D112600%2526amp%253Bc%253Df635b3cf130f350c