点游戏的开发和实现

摘 要：近年来,随着经济的日益发展,人们的生活水平不断提高,生活质量也在渐渐的改善。适当的娱乐游戏对人们的业余生活是不可必缺的。说到娱乐游戏，人们可能会想到网络上许许多多让人迷恋的网络游戏，比如说，传奇，奇迹，cs等等。是的，的确这些游戏给人们的业余生活添加了很多乐趣。借鉴网上的边锋游戏，我用vc++开发设计了24点游戏的实现算法，并在windows图形环境下设计出一个人机交互的游戏系统（类似于纸牌游戏）。
关键词：穷举法 栈 递归函数 think58 [来源：http://www.think58.com]

1 24点游戏算法实现
1.1 24点游戏简介
要开发一个游戏不是那么容易的，哪怕是简单的算术游戏。要是没有一定的专业知识，没有一定的思维能力是不行的。24点游戏是一个传统的算术游戏，其游戏之精髓就是考验人脑的反应能力。所谓24点游戏，就是通过加，减，乘，除4则运算，将给定的4个整数算出24。当然，传统的纸牌游戏其数字是有限定范围的，一般是从1到13。经统计，当算的目标数把24改为2的时候，独立解数更多，就是解的形式趣于集中化，大多数最后一步用减法（如：2*8-3*5）。游戏时会感到单调。由于24的因数多，解的形式就丰富，能充分发掘游戏者数学发散思维能力。要做好一个简单的24点游戏要具备很多知识。其中最主要的思想就是，24点的表达式要怎样行成，这是此游戏的关键。而要做一个完美的24点纸牌游戏，则需要的知识将会更多。现今，网络上的纸牌游戏数不甚数，比较出名的有联众游戏，边锋游戏，qq游戏。当然，他们的开发队伍庞大之极不是我们个人可以比及的。因此要一个人做好一个比较完美的游戏，是需要一定的游戏天分。以下我就开发24点游戏的几个关键算法和分析做详细的剖析。
1.2 24点游戏的算法
1.2.1 24点算法（1）
24点游戏的算法，其中最主要的思想就是穷举法。所谓穷举法就是列出4个数字加减乘除的各种可能性，包括括号的算法。我们可以将表达式分成以下几种：首先我们将4个数设为a,b,c,d,，其中算术符号有+，—，*，/，（，）。其中有效的表达式有a*(b-c/b)，a*b-c*d,等等。列出所有有效的表达式。其中我们用枚举类型将符号定义成数字常量，比如用1表示+，2表示-等。如下是我对穷举法的一种编程语言。在编程的头部要对变量做下定义。其中a,b,c,d的范围是1到13。因为传统的24点游戏是纸牌游戏，而纸牌游戏的数字就是从1到13，其中a是1，K是13,Q是12，J是11，其他的就是牌面的数字。这就需要在定义变量的时候要有限制。在vc++中的MFC编程中，在定义控件的变量范围可以直接填写变量的最大和最小，在此编程中的最大是13，最小是1。这就给编程写语句带来了方便（因为其自动会生成语句）。下面我介绍下穷举法的主要实现，我们知道要实现24点的算法，就是通过4个数字，4个运算符号和2对括号（最多为2对），通过各种组合判断其结果是否为24。我们用a，b，c,d代替4个数字。考虑每种可能，总的算法就有7种可能。分别为：1，没括号的（形如a*b*c*d）； think58.com [来源：http://think58.com]
2有括号的（形如(a * b) * c * d）；3有括号的（形如(a * b * c) * d）；4有括号的（形如a * (b * c) * d）；5有括号的（形如(a * b) * (c * d)）；6有括号的（形如((a * b) * c) * d）；7有括号的（形如(a * (b * c)) * d）。接下来就是对每一种进行分析判断。我们拿2种情况做为例子，一种是没括号的，一种有括号的。先拿没括号的分析。我们知道没括号的式子包括其运算符和数字总共为7个（3个运算符，4个数字），于是我们定义一个数组，用于存放运算符和数字。运算符我们可以用枚举变量来定义，首先我们通过循环语句形成一个表达式子（但这个表达式的运算循序是乱的）。表达式子有很多种情况，利用循环语句我们可以一一将其写出，例如（a+b+c+d，a+b+c-d，a+b+c*d，a+b+c/d….等等）生成表达式子的后，接着就是判别运算顺序。在没有括号存在的情况下，我们令其先运算*，/。这个顺序的选择很轻松，我们可以定义一个bool类型的函数，我们对数组进行扫描，当扫描到/，*，其返回真值，就直接进行运算。依次照样进行扫描，当所有的/，*运算都进行为止，接着将/，*运算生成的结果合并栈（即将运算的结果放在一个变量中），接着就对其与下一个数字进行运算，直到所有的值都计算出来了，最后将最后运算结果放于一个变量中。我们将这个变量的值和24相减，假如其值是在1E-6之外，则说明此运算式能计算出24。接下来我们来做第2种有括号的算法，有括号的算法和没括号的算法就是在判断运算循序的时候有所差别。我们知道，括号就是用来改变运算顺序而添加的。判断括号的先后顺序，我们同样可以用一个bool类型的函数来判别，在生成表达式要判断其运算顺序时，我们首先扫描表达式存放的数组，假如扫描到左括号，则将先对左括号后面的式子进行运算，接着在是对/，*的优先级进行计算。在第2种（形如(a * b) * c * d）的情况下，我们先将a，b先进行运算，生成其值，并将结果存放与另一个变量中，接着将得到的初步结果和c和d进行运算，最后得到总的结果。将其总结果和24相减，若其值小于1E-6则说明此表达式能算出24。接下来几种有括号的算法和第2种情况类似，我们不做详细的说明。以上就是穷举法的基本实现算法。

内容来自think58 [资料来源：THINK58.com]

[资料来源：www.THINK58.com]

1.2.2  24点游戏算法（2）
24点游戏的算法各种各样，各有千秋，现在让我们来讨论另一种24点游戏算法。此算法是在dos下实现的，但其思想明确，语句简短。其主要思想是简化算法，他将24点的算法排序分成如下几种，如下我们用a，b来代替变量。他将其分成如下6种情况，分别是a+b，a-b，b-a，a*b，a/b，b/a这6种情况，我们知道a+b和b+a是一样的，a*b和b*a是一样的。这样就可以省去2种算法。提高系统的使用效率，内存占用量小。还有其第2个思想是在判别24点正确与否的时候，采用了与24点相减绝对直在1E-6之外则判别其为正确，这就给运算带来了精确度，就如5 5 5 1等的数字也可以轻松算出，不会略过了。如下我们通过一段程序来看看其主程序段。
bool Search(int n)
{
    if (n == 1) {
        if ( fabs(number[0] - NUMBER_TO_CAL) < PRECISION ) {
            cout << expression[0] << endl;
            return true;
        } else { think58好，好think58 [资料来源：http://www.THINK58.com]
            return false;
        }
    } 本文来自think58

[来源：http://www.think58.com]

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double a, b;
            string expa, expb;
            a = number[i];
            b = number[j];
            number[j] = number[n - 1];
            expa = expression[i];
            expb = expression[j];
            expression[j] = expression[n - 1];
            expression[i] = '(' + expa + '+' + expb + ')';
            number[i] = a + b;

            if ( Search(n - 1) ) return true;
            expression[i] = '(' + expa + '-' + expb + ')';
            number[i] = a - b;
            if ( Search(n - 1) ) return true;
            expression[i] = '(' + expb + '-' + expa + ')';
            number[i] = b - a;
            if ( Search(n - 1) ) return true;
                       
            expression[i] = '(' + expa + '*' + expb + ')';
            number[i] = a * b;

think58.com

            if ( Search(n - 1) ) return true;
            if (b != 0) {
                expression[i] = '(' + expa + '/' + expb + ')';
                number[i] = a / b;
                if ( Search(n - 1) ) return true;
            }
            if (a != 0) {
                expression[i] = '(' + expb + '/' + expa + ')';
                number[i] = b / a;
                if ( Search(n - 1) ) return true; think58.com [资料来源：www.THINK58.com]
            }
            number[i] = a;
            number[j] = b;
            expression[i] = expa;
            expression[j] = expb;
        }
    }
    return false;
}
我们简单分析下以上的程序，我们可以清楚看到，SEARCH函数一个递归函数，其返回的是bool类型的值，其中number[0]为计算结果，假若其值和24相减为1E-6，则说明算法正确。其主要思想如下：首先我们取前面的两个数a,b对其进行相加，接着将两个相加的数结果存放于number[i]中，于是第2次循环的运算的时候，令其a= number[i]；则a成了原先的a和b之和，接着再将其存放于number[i]中，接着我们看到了程序中的递归函数SEARCH（n-1）。当调用递归函数的时候，我们可以看到其实现了所有数的相加，其中的n从原来的最大值4，经过递归达到2，最后生成4个数之和。接着就是递归函数的调用，假如number[i]其中i=0时，如果number[i]与24相减为零，则可以算出24点。如果，其返回直为否，则说明不能算出24点。则程序往下继续执行，接着是判断其他运算。同样的道理可以得出其返回值的正假，由此判断出24点的生成算法。注意假如我们只是简单的用计算结果和24相减为0则大错特错了，因为其中牵涉了到小数的问题。假如在运算中遇到了小数的式子不算，则此种判别是正确的，但24点游戏是允许中间过程存在有限小数，甚至是无限循环小数。因此要判断结果是否为24只能采用模糊的判别，即相减为1E-6之外，则说明其结果为24。 copyright think58 [资料来源：THINK58.com]
我们可以举个例子如5 5 5 1 ，其中的运算就牵涉到了小数，其算法为（5-1/5）*5。只要我们的判别是如以上程序的，则此算式将轻易的解出。还有一点就是，简化式子的算法。形如a+b和b+a是一样的，可以省略其中的一种。
   24点游戏的算法有多种多样，以上我只是简单对2种不同思想的算法做了简短的介绍，当然还有些算法也是大同小异，我们也不逐一列出了。介绍了24点算法后，接下来我们来探讨一下，一个有着纸牌图形界面的24点游戏将怎样完成。

think58.com [资料来源：http://think58.com]

[资料来源：www.THINK58.com]

参考文献：
[1] 刘卫宏、陈培：“《Visual c++编程基础》，上海理工大学出版社
[2] 石俊斌、李笑盈：《c++设计新思维》，清华大学出版社
[3] 林敏、方颖立：《游戏发展历史》，北京电子工业出版社
[4] 侯伯亨：《２４点游戏的各种开发工具》，西安电子科技大学出版社
[5] 潘松、黄继业编：《网络游戏世界》，科技出版社，2000年1月第2版
[5] 黄维通编：《Visual C++面向对象与可视化程序设计》，清华大学出版社 copyright think58

[版权所有：http://think58.com]