24点破解的Java实现

2014-11-24 11:30:47 ? 作者: ? 浏览: 6

一、基本思想


要想计算24点游戏的结果,则必须要采用基于搜索的算法(即穷举法)对每种情况进行遍历,我们怎么样才能遍历所有的情况呢?其实我们只要总结一下,还是有规律可以找的。


输入a、b、c、d,组成a Op1 bOp2 c Op3 d的表达式,其中先算哪个子表达式未知,一共有5种计算方式,如下图所示:


此时如果要实现该程序,需要存储5棵树,为了能够使得存储量达到最小,通过分析,其实总的来说,只需要存储2棵树即可,即:


其他树都是冗余的,因为我们可以通过a、b、c、d的交换,比如((a+(b*c))+d)可以变为(((b*c)+a)+d);


对于每棵树来说,abcd的可能性为4*3*2*1=24;op1op2 op3的可能性为4*4*4=64,因此总个数为1536,而两棵树的总个数为3072。因此只需要穷举这些方法,就可以知道结果。


TfUtils类为实现穷举24点所有可能情况的类,calculate函数用于计算,参数a、b、c、d分别为给定的4个数,而TfUtils类中的expr属性为求解的表达式。


二、代码实现


CalculatorUtils.java


TfUtils.java


测试代码:


输入为:3,3,7,7


输出为:(((3/7)+3)*7)


-->

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: