快捷搜索:

关于24点游戏的思路和算法

闲来无聊便和同砚玩起童年时常常玩的二十四点牌游戏来。此游戏说来简单,便是使用加减乘除以及括号将给出的四张牌组成一个值为24的表达式。然则此中却不乏一些有趣的题目,这不,我们刚玩了一下子,便碰到了一个难题——3、6、6、10(着实后来想想,这也不算是个太难的题,只是当时我们的脑子都没有转弯而已,呵呵)。

问题既然呈现了,我们当然要办理。冥思苦想之际,我的脑中擦过一丝动机——何不编个法度榜样来办理这个问题呢?文曲星中不就有这样的法度榜样吗?以是这个设法主见应该是可行。想到这里我立即开始思考这个法度榜样的算法,最先想到的自然是穷举法(后来发明我再也想不到更好的措施了,伤心呀,呵呵),由于在这学期我曾经写过一个小法度榜样——谋略有括号的简单表达式。只要我能编程实现四个数加上运算符号所构成的表达式的穷举,不就可以使用这个谋略法度榜样来完成这个谋略二十四点的法度榜样吗?确定了这个思路之后,我开始想这个问题的细节。

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

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

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

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

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

/* ans[] 用来寄放各类排列组合的数组 */

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

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

用它来代替c[]做处置惩罚,斟酌到c[]中有可能呈现相同数的环境 */

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

/* j 嵌套轮回的次数 */

int fans(c,k,ans,kans,j)

int j,k[],c[];char ans[],kans[];

{ int i,p,q,r,h,flag,s[4],t[4][4];

for(p=0,q=0;p<4;p++)

{ for(r=0,flag=0;r if(k[p]!=kans[r]) flag++;

if(flag==j) t[j][q++]=k[p];

}

for(s[j]=0;s[j]<4-j;s[j]++)

{ kans[j]=t[j][s[j]];

if(j==3) { for(h=0;h<4;h++)

ans[2*h]=c[kans[h]-1]; /* 调剂天生的排列组合在终极的表

达式中的位置 */

for(h=0;h<3;h++)

symbol(ans,h); /* 在表达式中添加运算符号 */

}

else { j++;

fans(c,k,ans,kans,j);

j--;

}

}

}

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

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

int sans(ans,sy,j,h)

char ans[],sy[];int j,h;

{ int i,p,k[3],m,n; char ktans[20];

for(k[j]=0;k[j]<4;k[j]++)

{ ans[2*j+1]=sy[k[j]]; /* 刚才的四个数分手寄放在0、2、4、6位

这里的三个运算符号分手寄放在1、3、5位*/

if(j==2)

{ ans[5]=sy[k[j]];

/* 此处根据不合的表达式形式再进行响应的处置惩罚 */

}

else { j++; sans(ans,sy,j--,h); }

}

}

好了,接下来我再斟酌不合表达式的处置惩罚。刚才我已经将表达式分为三类,是由于添加三个括号对付四张牌来说肯定是重复的。对付第一种,无括号自然不用另行处置惩罚;而第二种环境由以下代码可以得出其可能性有六种,此中还有一种是多余的。[Page]

for(m=0;m<=4;m+=2)

for(n=m+4;n<=8;n+=2)

这个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。本次的运算符下次将从新斟酌。[Page]

第二种措施——

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

那么什么是表达式的线性化呢?人们所习气的表达式的表达措施称为中缀表示。中缀表示的特征是运算符位于运算工具的中心。但这种表示要领,无意偶尔必须借助括号才能将运算顺序表达清楚,而且处置惩罚也对照繁杂。

1929年,波兰名学家Lukasiewicz提出一种不用括号的逻辑符号体系,后来人们称之为波兰表示法(Polish notation)。波兰表达式的特征是运算符位于运算工具的后面,是以称为后缀表示。在对波兰表达式进交运算,严格按照自左至右的顺序进行。下面给出一些表达式及其响应的波兰表达式。

表达式 波兰表达式

A-B AB-

(A-B)*C+D AB-C*D+

A*(B+C/D)-E*F ABCD/+*EF*-

(B+C)/(A-D) BC+AD-/

OK,所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对付每一个表达式,使用栈可以把表达式变换成波兰表达式,也可以使用栈来谋略波兰表达式的值。

至于转换和谋略的历程和第一种措施大年夜同小异,这里就不再赘述了。

下面给出转换和谋略的详细实现法度榜样——

/* first函数给出各个运算符的优先级,此中=为表达式停止符 */

int first(char c)

{ int p;

switch(c)

{ case \'*\': p=2; break;

case \'/\': p=2; break;

case \'+\': p=1; break;

case \'-\': p=1; break;

case \'(\': p=0; break;

case \'=\': p=-1; break;

}

return(p);

}

/* 此函数实现中缀到后缀的转换 */

/* M的值宏定义为20 */

/* sp[]为表达式数组 */

int mid_last()

{ int i=0,j=0; char c,sm[M];

c=s[0]; sm[0]=\'=\'; top=0;

while(c!=\'\\0\')

{ if(islower(c)) sp[j++]=c;

else switch(c)

{ case \'+\':

case \'-\':

case \'*\':

case \'/\': while(first(c)0) sp[j++]=sm[top--];

sp[j]=\'\\0\'; return(0);

}

/* 由后缀表达式来谋略表达式的值 */

int calc()

{ int i=0,sm[M],tr; char c;

c=sp[0]; top=-1;

while(c!=\'\\0\')

{ if(islower(c)) sm[++top]=ver[c-\'a\'];/*在转换历程顶用abcd等来代替数,

这样才可以更方便的处置惩罚非一位数,

ver数组中寄放着这些字母所代替的数*/

else switch(c)

{ case \'+\': tr=sm[top--]; sm[top]+=tr; break;

case \'-\': tr=sm[top--]; sm[top]-=tr; break;

case \'*\': tr=sm[top--]; sm[top]*=tr; break;

case \'/\': tr=sm[top--];sm[top]/=tr;break;

default : return(1);

}

c=sp[++i];

}

if(top>0) return(1);

else { result=sm[top]; return(0); }

}

这样这个法度榜样基础上就算办理了,回偏激来拿这个法度榜样来算一算文章开始的那个问题。哈哈,算出来了,原本如斯简单——(6-3)*10-6=24。

着末我总结了一下这此中轻易掉足的地方——

1、 排列的时刻因为一个数只能呈现一次, 以是一定有一个判断语句。然则用什么来判断,用大年夜小显然不可,由于有可能这四个数中有两个或者以上的数是相同的。我的措施是给每一个数设置一个代号,在排列停止时,经由过程这个代号找到这个数。[Page]

2、在利用嵌套函数时,需仔细阐发法度榜样的履行历程,并对个别变量进行适当的调剂(如j的值),法度榜样才能精确的履行。

3、在阐发括号问题的时刻要卖力仔细,不要错过任何一个可能的时机,也要只管即便使法度榜样变得简单一些。不过我的阐发可能也有问题,还请高手辅导。

4、在用函数对一个数组进行处置惩罚的时刻,必然要留意假如这个数组还必要再利用,就必须将它先保存起来,否则会掉足,而且是很严重的差错。

5、在处置惩罚用户输入的表达式时,因为一个十位数或者更高位数是被分化成各位数寄放在数组中,以是需对它们进行处置惩罚,将它们转化成实际的整型变量。别的,在转化历程中,用一个字母来代替这个数,并将这个数存在一个数组中,且它在数组中的位置和代替它的这个字母有必然的联系,这样才能取回这个数。

6、因为在穷举历程难免会呈现谋略历程中有除以0的谋略,以是我们必须对calc函数种对付除的运算加以处置惩罚,否则法度榜样会由于掉足而退出(Divide by 0)。

7、着末一个问题,本法度榜样尚未办理。对付一些对照闻名的题目,本法度榜样无法解答。比如说5、5、5、1或者8、8、3、3。这是因为这些题目在谋略的历程用到了小数,而本法度榜样并没有斟酌到小数。

着末,因为此文档并没有在写法度榜样的同时完成,以是难免由于影象的缺点和小弟水平的不够而有不少差错,还望各位品评斧正;或者你觉得我写得还不敷清楚,你也可以给我来信评论争论。

您可能还会对下面的文章感兴趣: