二十四点在线计算

二十四点在线计算

-

2023年3月20日发(作者：凉粉的制作)关于二十四点游戏的编程思路与基本算法 漫长的假期对于我来说总是枯燥无味的，闲来无聊便和同学玩起童年时经常玩的二十四点牌游戏来。此游戏说来简单，就是利用加减乘除以及括号将给出的四张牌组成一个值为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); }}} 好了，接下来我再考虑不同表达式的处理。刚才我已经将表达式分为三类，是因为添加三个括号对于四张牌来说肯定是重复的。对于第一种，无括号自然不用另行处理；而第二种情况由以下代码可以得出其可能性有六种，其中还有一种是多余的。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；运算符栈用来记忆表达式中的运算符y 0）。 7、最后一个问题，本程序尚未解决。对于一些比较著名的题目，本程序无法解答。比如说5、5、5、1或者8、8、3、3。这是由于这些题目在计算的过程用到了小数，而本程序并没有考虑到小数。 最后，由于此文档并没有在写程序的同时完成，所以难免因为记忆的差错和小弟水平的不足而有不少错误，还望各位批评指正；或者你认为我写得还不够清楚，你也可以给我来信讨论。