关于二十四点游戏的编程思路与基本算法
漫长的假期对于我来说总是枯燥无味的,闲来无聊便和同学玩起童年时经常玩的二十四点牌
游戏来。此游戏说来简单,就是利用加减乘除以及括号将给出的四张牌组成一个值为 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<J;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++;