24点游戏算法

计时制

同名手机游戏(游戏信息 游戏介绍 游戏截图)

二十四点是一种益智游戏，它能在游戏中锻炼人们的心算，它往往要求人们将四个数字进行加减乘除四则混合运算（允许使用括号）求得二十四。

24点游戏算法

利用计算程序来完成这个计算二十四点的程序

方法如下:

首先穷举的可行性问题。我把表达式如下分成三类——

1、 无括号的简单表达式。

2、 有一个括号的简单表达式。

3、 有两个括号的较复杂表达式。

穷举的开始我对给出的四个数进行排列，其可能的种数为4*3*2*1=24。我利用一个嵌套函数实现四个数的排列，算法如下:

/* ans[] 用来存放各种排列组合的数组*/

/* c[] 存放四张牌的数组 */

/* k[] c[]种四张牌的代号，其中k=I+1。

用它来代替c[]做处理，考虑到c[]中有可能出现相同数的情况 */

/* kans[] 暂存生成的排列组合 */

/* j 嵌套循环的次数 */

正如上面函数中提到的，在完成四张牌的排列之后，在表达式中添加运算符号。由于只有四张牌，所以只要添加三个运算符号就可以了。由于每一个运算符号可重复，所以计算出其可能的种数为4*4*4=64种。仍然利用嵌套函数实现添加运算符号的穷举，算法如下:

/* ans[],j同上。sy[]存放四个运算符号。h为表达式形式。*/

好了，接下来我再考虑不同表达式的处理。刚才我已经将表达式分为三类，是因为添加三个括号对于四张牌来说肯定是重复的。对于第一种，无括号自然不用另行处理；而第二种情况由以下代码可以得出其可能性有六种，其中还有一种是多余的。

这个for循环给出了添加一个括号的可能性的种数，其中m、n分别为添加在表达式中的左右括号的位置。我所说的多余的是指m=0，n=8，也就是放在表达式的两端。这真是多此一举，呵呵！最后一种情况是添加两个括号，我分析了一下，发现只可能是这种形式才不会是重复的——（a b）(c d)。为什么不会出现嵌套括号的情况呢？因为如果是嵌套括号，那么外面的括号肯定是包含三个数字的（四个没有必要），也就是说这个括号里面包含了两个运算符号，而这两个运算符号是被另外一个括号隔开的。那么如果这两个运算符号是同一优先级的，则肯定可以通过一些转换去掉括号（你不妨举一些例子来试试），也就是说这一个括号没有必要；如果这两个运算符号不是同一优先级，也必然是这种形式((a+-b)*/c)。而*和/在这几个运算符号中优先级最高，自然就没有必要在它的外面添加括号了。

综上所述，所有可能的表达式的种数为24*64*（1+6+1）=12288种。哈哈，只有一万多种可能性（这其中还有重复），这对于电脑来说可是小case哟！所以，对于穷举的可行性分析和实现也就完成了。

接下来的问题就是如何对有符号的简单表达式进行处理。这是栈的一个著名应用，那么什么是栈呢？栈的概念是从日常生活中货物在货栈中的存取过程抽象出来的，即最后存放入栈的货物（堆在靠出口处）先被提取出去，符合“先进后出，后进先出”的原则。这种结构犹如子弹夹。

在栈中，元素的插入称为压入（push）或入栈，元素的删除称为弹出（pop）或退栈。

栈的基本运算有三种，其中包括入栈运算、退栈运算以及读栈顶元素，这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。

那么作为栈的著名应用，表达式的计算可以有两种方法。

第一种方法——

首先建立两个栈，操作数栈OVS和运算符栈OPS。其中，操作数栈用来记忆表达式中的操作数，其栈顶指针为topv，初始时为空，即topv=0；运算符栈用来记忆表达式中的运算符，其栈顶指针为topp，初始时，栈中只有一个表达式结束符，即topp=1，且OPS（1）=‘；’。此处的‘；’即表达式结束符。

然后自左至右的扫描待处理的表达式，并假设当前扫描到的符号为W，根据不同的符号W做如下不同的处理：

1、 若W为操作数

2、 则将W压入操作数栈OVS

3、 且继续扫描下一个字符

4、 若W为运算符

5、 则根据运算符的性质做相应的处理：

(1)、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top)),则将运算符W压入运算符栈OPS，并继续扫描下一个字符。

(2)、若运算符W为表达式结束符‘；’且运算符栈栈顶的运算符也为表达式结束符（即OPS(topp)=’;’），则处理过程结束，此时，操作数栈栈顶元素（即OVS（topv））即为表达式的值。

(3)、若运算符W为右括号且运算符栈栈顶的运算符为左括号（即OPS（topp）=’(‘)，则将左括号从运算符栈谈出，且继续扫描下一个符号。

(4)、若运算符的右不大于运算符栈栈顶的运算符（即OPS(topp)），则从操作数栈OVS中弹出两个操作数，设先后弹出的操作数为a、b，再从运算符栈OPS中弹出一个运算符，设为+，然后作运算a+b,并将运算结果压入操作数栈OVS。本次的运算符下次将重新考虑。

第二种方法——

首先对表达式进行线性化，然后将线性表达式转换成机器指令序列以便进行求值。

那么什么是表达式的线性化呢？人们所习惯的表达式的表达方法称为中缀表示。中缀表示的特点是运算符位于运算对象的中间。但这种表示方式，有时必须借助括号才能将运算顺序表达清楚，而且处理也比较复杂。

1929年，波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系，后来人们称之为波兰表示法（Polish notation）。波兰表达式的特点是运算符位于运算对象的后面，因此称为后缀表示。在对波兰表达式进行运算，严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。

表达式 波兰表达式

A-B AB-

OK，所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对于每一个表达式，利用栈可以把表达式变换成波兰表达式，也可以利用栈来计算波兰表达式的值。

至于转换和计算的过程和第一种方法大同小异，这里就不再赘述了。

下面给出转换和计算的具体实现程序——

这样这个程序基本上就算解决了，回过头来拿这个程序来算一算文章开始的那个问题。哈哈，算出来了，原来如此简单——（6-3）*10-6=24。

计时制

24小时计时制二十四点指的是零点

同名手机游戏

游戏信息

应用类别： 棋牌天地

应用开发：ustb_20090830128_zhongjiahong

应用版本： 1.0.0.0

应用大小： 45.00 KB

应用语言： 中文

正版价格： 免费

支持平台：WinMobile 7.1

游戏介绍

给出4正整数，系统就会推算出能得到24的数学式子。该游戏仅供大家娱乐。

游戏截图