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 {
return false;
}
}
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;
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;
}
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。
我们可以举个例子如5 5 5 1,其中的运算就牵涉到了小数,其算法为(5-1/5)*5。只要我们的判别是如以上程序的,则此算式将轻易的解出。还有一点就是,简化式子的算法。形如a+b和b+a是一样的,可以省略其中的一种。
24点游戏的算法有多种多样,以上我只是简单对2种不同思想的算法做了简短的介绍,当然还有些算法也是大同小异,我们也不逐一列出了。介绍了24点算法后,接下来我们来探讨一下,一个有着纸牌图形界面的24点游戏将怎样完成。
1.2.3 24点算法的多样性(即多解的算法和优化算法)的讨论
我们拿递归算法来分析其算法的多样性。我们知道递归算法是通过调用一个递归函数,将n值依次减1到最小值为止。并且在此递归的过程中实现了,表达式的4则运算,然而在以上的递归函数中已经考虑到了各种算法的可能性。其主要思想就是对4个数字的运算顺序和运算符号通过递归逐一的算出各种表达式。先重加法算起,依次算到除法(被除数不为零)为止。显然,其中已经包括了24点的所有算法,假如要输出每种可能性进性判别其优化性,那就需要用到编译原理的知识。通过逆波兰式的判定,求出其最优化的算法。我们拿a+b+c+d为例子,我们知道在有括号的情况下,(a+b)+(c+d)以及(a+b+c)+d这3种情况中,很明显前一种是最简洁。那我们在程序中要如何设置其最简单的算法呢。这就需要对两种算法进行逆波兰式的判别,我们将前者写成逆波兰式,则为ab+c+d+,第2种写成逆波兰式为也为ab+c+d+。说明两者运算的结果是一样的。但是很明显,前者简洁。因此,对于逆波兰式相同,但实际程序中不同的程序,就可以判断其优化程度。假如我们将左右括号定义为枚举变量,接着扫描每个字符,假如字符串最短的则为最优化的算法。还有我们假定,在能用中间过程为全整数,而某种表达式中间过程则存在着小数结果,则认为后者算法是不优化的。但有些算式,通过前者是算不出来的,只能通过后者算出,则其也应该算是优化了的算法。因此判断优化与否的关键就是,判断其中间过程是否有小数结果生成,并讨论其用不存在小数中间结果的算法是否可行。如果,存在整数的算法,则要去掉其小数的算法。因为它肯定是没有优化。
1.3 24点游戏输入表达式的判别算法
讨论了24点游戏的各种算法思想后,接着要考虑的是游戏的关键技术,即是表达式的判别。表达式的判别是除了算法之后的首当其冲也解决的问题。何为表达式判别?所谓表达式的判别就是,你在对话框中输入数字和字符的时候,是不是牌面所显示的值,这是一个非常关键的重点。我们举个例子说明下,假设现在我们已经开始某一个24点纸牌游戏,然后按下开始键。接着游戏截面显示了,红桃A,黑桃5,红桃5和梅花5这4张牌,要求你算出24点。假设现在你要测试这个游戏的表达式判别怎么样。那我们可以轻松的试出其正确与否。我们可输入1*2*3*4这个算式子。如果系统未提示任何错误,反而弹出计算正确的提示。则说明此游戏没有做任何的表达式判别,至少没有对输入数字进行控制。这就是所谓的表达式判别。然而要做到表达式真正的符和要求,其需要对其采取一定的措施。表达式判别有简单有复杂,我们的目的是力争简洁但实用。要进行表达式的判别,我们必须要用编译原理。编译原理是对计算机语言进行文法分析,词法分析的一种学科。特别是对表达式运算顺序和表达式输入正确与否能轻易的做出。我们将在文本中输入的一段字符串,将其进性文法分析和语法判断。我们可以轻松的将其判断出来。对于表达式顺序的问题更是简单,现在我们介绍一种方法叫逆波兰式。逆波兰式的思想是这样的:比如我们现在输入一串运算符号和一些整形类型的变量,他能通过一定的算法顺序进性排列 。例如我们在程序中要得到a+b则逆波兰式为ab+,要得到(a+b)*c则逆波兰式为ab+c*,更复杂的a:=b*c+b*d其逆波兰式为abc*bd*+:=。我们可以看出,逆波兰式可以将有括号的表达式省略括号,那为什么其能省略括号呢,正就是逆波兰式的实现方法。
我们拿上面最复杂的例子做分析,得出逆波兰式子的思想。其实,逆波兰的思想是利用了栈的功能。我们看,我们将第一个字符a推入栈顶,接着推入第2字符,接着第3,4一直将推如栈中。假如,中间遇到了运算符号,就如在c后面遇到了*号,则系统将离*号最近的两个变量进行乘运算,得到一个结果。将b,c栈合并用于存放结果。接着在往栈中推入b,d,我们看到在d后又出现了*号,着将离*最近的两个变量进行想乘,并且合并栈,将结果存放于栈中。依着以上的思想进行运算,就可以实现语句a:=b*c+b*d。因此我们在判断输入表达式是否错误的时候就可以利用此种思维方法。我们将每个输入的字符推入栈中,并且对其进行判别,假如遇到的字符是除了如(1—9,+,-,*,/,(,))等符号外的数据,则说明输入有误,此算法完成了语法错误的判别。接着是判断,输入的数字和系统给的直是否一样,这也非常的简单。我们对每次推入栈的数字和系统的数字进行比较,假如有不同的则报“数字和系统提供的不相同”的错误。在判断括号匹配的时候,我们可以定义一整形数组变量a[]和2个整形变量count1,count2另其初始值全为0,当遇到左括号字符是另其变量a[0]++,并且count1++;如过遇到第2个左括号则a[1]++,并且count1++,其中数组的序号值1有count1控制(即如count1=1则序号为1),同理第3个左括号,第4个左括号都是同样的语句。然而在推入栈的时候碰到的第一个右括号,我们令a[0]--,count2++,接着和上面的步骤类似。最后,判断括号匹配的时候只要求出数组中所有数字的绝对值之和,如果其值不为0则说明括号没匹配,否则就是匹配的。通过逆波兰式的原理,我们可以轻松完成24点游戏表达式的判别。
1.4 纸牌游戏界面的算法
1.4.1 获得纸牌界面的函数
接下来是纸牌游戏的制作,要做纸牌游戏。首先必须要有纸牌的界面。界面需要通过截图来获得。将一副标准扑克牌的52张牌面截下来,将其加入到vc++的res文件夹中,也就是资源文件夹。并且将其中的52张纸牌牌面进行系统化的命名。比如,用a前缀代替红桃,b前缀代替黑桃,c前缀代替梅花,d前缀代替方块。这样52张牌就对应了52个图形文件。做好了牌面的截图后就是对其进行发牌。发牌算发也是一个直的考虑是关键。我们将其中的52个数设为数组行如:a[52],这样每张牌就对应了数组中的一个变量。我们先将每个数和数组相连接起来。接着我们用一个随即函数令其随即的产生4个数,函数行如:
b[1]=rand() b[2]=rand() b[3]=rand() b[4]=rand(),其函数的意思就是产生随即数。但是这里产生的随即数都是任意的,可能大于52。这样我们需要对产生的随即数进行处理。在这里我们使用整除求余功能,如:b[1]=rand()%52+1这样每次输出随即数就不会大于52了,达到了预期的效果。
此程序的关键就是随即搜索牌面的路径,通过牌面的搜索和刷新,形成一组新的数字,根据此4个数字生成24点。其中最主要的函数就是一个随即函数rand(),此函数是c++系统中自带的函数,存放于stblib.h头文件中。此函数在使用之前,必须有个诱导函数srand()。通过调用Rand()函数就可以生成随即数据,但随即函数生成的数字是凌乱无序的,它范围很大,因此必须对它加以限定范围,这时我们用到了一个方法,就是用整除求余的方法。假如将52张牌标记成0到51的数字,那么我们可以通过对随即函数求余的方法,找到每张牌。其函数形式为rand()%52+1;其中形成的0到51个数将代表一副扑克牌中的52张。牌面在程序中将怎样生成?首先我们要做的是截图,所谓截图就是从已有的纸牌游戏中截下相应的52张牌(不包括大,小王)。将其中的52张牌存放为52个图片文件。要注意在文件命名的时候是有讲究的,因为此后要搜索牌的路径。因此给其中的牌面文件命名时要有统一性,又要有区别性。统一性就是我们可以将4种不同花色的牌分别命名以a,b,c,d开头,区分性就是我们用每张牌面的数值来区分其不同行。比如,我们命名黑桃k为a13,桃花k为b13,梅花k为c13,方快k为d13。这样我们就将52张牌和52个有序的文件一一对应了。牌面做好了,接下来就是要怎样在游戏界面中形成牌面。在面向对象的程序编程中,vc++中的图形界面的设计可以在API中来完成。首先我们要指定牌面存放的位置,位置的研究是很重要的。位置包含了很多属性,包括一般的长,高等。其次就是要定义一个矩形空间,此函数的定义在c++中有着现存的函数。可以用以下函数。
rectdate[0].originrect.top =rectdate[0].rect.top =50;
rectdate[0].originrect.bottom=rectdate[0].rect.bottom =rectdate[0].rect.top+height;
rectdate[0].originrect.left =rectdate[0].rect.left =50;
rectdate[0].originrect.right=rectdate[0].rect.right =rectdate[0].rect.left+width;
rectdate[0].firstrect =rectdate[0].originrect;
4张纸牌对应于其中的4个如上的函数,其他三个同理可得。只是大小上有点差别,比如高度,左右位置等都应该有相应的变化。
存放位置编好了之后,接着就是在怎样生成图片了。在API中生成图片我们用到了绘制图片的功能和刷新功能。
1.4.2不发重复牌的算法
我们在完成纸牌游戏界面的设计之后,接着要考虑的一个问题就是:因为你用到的是一副牌,如何实现每次发牌的时候不产生相同的牌面。这是游戏中的一个关键,也是程序成功与否的关键因素。其实,要完成此功能也极为简单。既然我们在做界面的时候已经给52张牌给了命名,则我们只要对52张牌的花色进行分类。就如上面所提到的,用52个有着相同点又有区别的图形文件来区分其花色和大小。接着我们定义一个a[52],将52张牌按顺序依次存放于数组中。其中花色一样的牌为一样的顺序,例如红桃花色的牌存放在a[0]-a[12]中,黑桃的牌存放在a[13]-a[25]中,梅花花色为a[26]-a[38]中,方块为a[39]-a[51]中。这样做的目的是为了有利于判别其花色。将花色进行了分类后,我们可以对其进行选择判断了。比如我们要拿一张红桃10,则具备两个条件的数组值只有一个。首先我们找出大小为10的值,我们知道有4个,接着我们要找到红桃花色,这只要我们做简单的判断,即数组的下标(这里我们设它为i)0=<i<=12。通过以上的查找我们可以找到红心10。我们知道一张牌有两个要素组成,一个是大小,一个花色。大小我们可以对其很好的做控制,而花色则没有相映的程序代码。因此只能采用以上方法以区分。
1.4.3重新发牌的函数
重新开始游戏的算法简介。我们知道游戏中重新开始是肯定要用到的,你不可能让别人只算一次,这就失去了其实际意义,也得不到娱乐和益智的效果。因此,重新发牌也是其中很重要的算法。在API的编程中,我们使用了一个关键技术,那就是刷新函数。刷新函数可以令原有的界面撤消,然后在重新绘制界面。
如下让我们看看此24游戏中,重新发牌的关键程序。
void CWorkView::OnPaint() //重新绘制牌面的程序
{
int i;
CPaintDC dc(this); // device context for painting
for(i=0;i<4;i++)
{
rectdate[i].hBitmap=(HBITMAP)LoadImage(AfxGetInstanceHandle(),rec
GetObject(rectdate[i].hBitmap, sizeof BITMAP, &bm1);
SelectObject(hSrcDC1, rectdate[i].hBitmap);
::SetStretchBltMode(hDesDC1,COLORONCOLOR);
::StretchBlt(hDesDC1, rectdate[i].rect.left, rectdate[i].rect.top, width, height, hSrcDC1, 0, 0, bm1.bmWidth, bm1.bmHeight,+SRCCOPY);
}
通过以上的函数,我们就可以得到下一轮游戏的牌面。
以上是完成一个简单24点游戏必要的程序设计,接着我介绍下游戏中其他的一些控件。比如时间控制,开始和结束控制等。
1.5 其他一些控件的设置
1.5.1 时钟的设置
时钟是用来控制游戏速度,和提高的人的智力所必需的控件。也是为游戏增添乐趣,提供思索空间所必需的。时钟的设置在vc++钟也是比较简单的,其中用到的函数也非常简介,接着让我们来看看其简单的程序。
void CWorkView::OnTimer(UINT nIDEvent) //定时器响应程序
{CString temp;
UpdateData(true);
temp=m_edit;
timercount--;
m_edit4=timercount;
UpdateData(FALSE);}
if(timercount<=0)
{KillTimer(1) ;
timercount=30;
(CButton*)CWnd::GetDlgItem(IDC_BUTTON5)->EnableWindow(TRUE);}
查看如上函数,我们看到的关键函数就只有一个,那就是KillTimer函数。我们从他的拼写可以看到,其意思是消除时间。其中还用到了控制时间秒数的变量timercount,在如上函数中其最大直为30,则说明游戏将在30秒内结束。另外在时间控制下,其他一些控件也要实行相应的变化。在如上程序中,id为IDC-BUTTON5的空件在时间结束的时候要消除灰化。
1.5.2 游戏的开始和结束控制
每个游戏都有其游戏的开始控制和结束控制,当然24点游戏也不例外。因此要控制游戏的开始结束也是游戏中必要的控件。我们来看下其程序:
void CWorkView::OnButton5()
{if(istimer==false)
{SetTimer(1,1000,NULL);
(CButton*)CWnd::GetDlgItem(IDC_BUTTON5)->EnableWindow(FALSE);
(CButton*)CWnd::GetDlgItem(IDC_BUTTON3)->EnableWindow(FALSE);
(CButton*)CWnd::GetDlgItem(IDC_BUTTON2)->EnableWindow(FALSE);
(CButton*)CWnd::GetDlgItem(IDC_BUTTON4)->EnableWindow(FALSE);}}
其中在控件中我们添加了控件BUTTOM5,用于控制游戏的开始。当按下开始按钮时,我们将控件BUTTTON3,2,4都灰化。这就实现了简单的游戏开始控制。
结束按钮和开始按钮大同小异,这里我们就不详细介绍了。