java 24点算法实现

原创
2014/10/14 23:40
阅读数 42

 

  最近闲来无事,突然怀念起小时候和堂兄表姐们经常玩24点游戏,于是就琢磨着是不是开发一个安卓手机版本。然后上网上一搜,发现已经被别人给开发烂了啊。不过这只能说明这个小游戏要想赚广告费很难了,但是拿来锻炼和在妹纸面前装逼还是很有价值的,嘿嘿,想到这里,我最终还是花了3天时间开发了一个小游戏出来。

 

  算法实现

  在网上试玩了一个flash的版本,发现还需要实现计算所有正确的结果,然后网上稍微百度了下思路,就开始自己实现了。我开始时大概的思路就是穷举出所有的数字和算式的排列组合,然后一一进行验算,中间碰到两个问题,

  1. 第一是计算顺序的问题,稍微思考一下,就会发现,+,*是不考虑先后顺序的,-,/是考虑先后顺序的,所以考虑计算顺序后每两个数都会有6种计算方法。而括号也会产生很多不同的情况。
  2. 第二是保存计算的表达式的问题,因为穷举完了,计算机是知道答案了,但是用户还是不知道啊,所以得想办法保存起来(这个问题开始时没注意,后来小花了点时间才完美解决的,后面会有说明)。

 

  然后,具体怎样进行遍历才能做到既不重复又无遗漏呢? 我的思路是这样的,还是得利用递归来简化实现,虽然递归很耗资源,但是作为非acm大神,算法水平一般般的我来说,还是先从简单的角度考虑。一个算式,不管包不包括括号,都可以抽象成两个数的计算的叠加,因为每次单个运算都是拿两个数运算的。然后再通过递归,将计算的结果和其他的数重新做两个数的运算,一直递归到只剩下一个结果时,那么这个数就是这种计算方法得到的答案了,和24比较就可以了。

 

  至于每一个运算轨迹得到的表达式该怎么保存呢?我的做法是用一个类封装起来,然后维护两个数组,一个是数字(这个数字既是用户输入的,也可以是两个或多个数运算得到的结果),另一个就是这个数对应的表达式(当这个数是用户输入的时候就是一个数字而已,当这个数字是运算的结果时就是算式)的字符串。

 

  实现代码:

  1 package net.yunstudio.p24.util;
  2 
  3 import java.util.ArrayList;
  4 import java.util.HashSet;
  5 import java.util.List;
  6 import java.util.Random;
  7 import java.util.Set;
  8 
  9 import com.umeng.a.a.a.b.n;
 10 
 11 public class Count24 {
 12     private List<String> answerList=new ArrayList<String>();
 13     public List<String> getAnswerList() {
 14         return answerList;
 15     }
 16     public static class Data{
 17         public float[]  arr;
 18         public String expStr="";
 19         public String[] strs;
 20         public Data(){}
 21         public Data(int a,int b,int c,int d) {
 22             arr=new float[]{a,b,c,d};
 23             strs=new String[]{a+"",b+"",c+"",d+""};
 24             expStr=a+"";
 25         }
 26         public Data(int arr[]) {
 27             this.arr=new float[]{arr[0],arr[1],arr[2],arr[3]};
 28             this.strs=new String[]{arr[0]+"",arr[1]+"",arr[2]+"",arr[3]+""};
 29         }
 30     }
 31     public void count(Data data){
 32         float[] arr=data.arr;
 33         if(arr.length<=1){
 34             if(arr.length==1&&arr[0]==24){
 35                 answerList.add(data.expStr.substring(1, data.expStr.length()-1));
 36             }
 37             return ;
 38         }
 39         for(int i=0,len=arr.length;i<len-1; i++){
 40             for(int j=i+1;j<len;j++){
 41                 float x=arr[i];
 42                 float y=arr[j];
 43                 String xs=data.strs[i];
 44                 String ys=data.strs[j];
 45                 for(int k=0;k<6;k++){
 46                     Data newData=getNewArr(data,i);
 47                     switch(k){
 48                         case 0:
 49                         newData.arr[j-1]=x+y;
 50                             newData.expStr=xs+"+"+ys;
 51                         break;
 52                         case 1:
 53                         newData.arr[j-1]=x-y;
 54                             newData.expStr=xs+"-"+ys;
 55                         break;
 56                         case 2:
 57                         newData.arr[j-1]=y-x;
 58                         newData.expStr=ys+"-"+xs;
 59                         break;
 60                         case 3:
 61                         newData.arr[j-1]=x*y;
 62                             newData.expStr=xs+"*"+ys;
 63                         break;
 64                         case 4:
 65                         if(y!=0){
 66                             newData.arr[j-1]=x/y;
 67                                 newData.expStr=xs+"/"+ys;
 68                         }else {
 69                             continue;
 70                         }
 71                         break;
 72                         case 5:
 73                         if(x!=0){
 74                             newData.arr[j-1]=y/x;
 75                                 newData.expStr=ys+"/"+xs;
 76                         }else {
 77                             continue;
 78                         }
 79                         break;
 80                     }
 81                     newData.expStr="("+newData.expStr+")";
 82                     newData.strs[j-1]=newData.expStr;
 83                     count(newData);
 84                 }
 85             }
 86         }
 87         
 88     }
 89     private static Data getNewArr(Data data, int i) {
 90         Data newData=new Data();
 91         newData.expStr=data.expStr;
 92         newData.arr=new float[data.arr.length-1];
 93         newData.strs=new String[data.arr.length-1];
 94         for(int m=0,len=data.arr.length,n=0;m<len;m++){
 95             if(m!=i){
 96                 newData.arr[n]=data.arr[m];
 97                 newData.strs[n]=data.strs[m];
 98                 n++;
 99             }
100         }
101         return newData;
102     }
103     
104     public static final List<String> easyCount(int[] curRandNums){
105         Count24 count24=new Count24();
106         count24.count(new Data(curRandNums));
107         Set<String> set=new HashSet<String>(count24.getAnswerList());//去重
108         return new ArrayList<String>(set);
109     }
110     
111     public static void main(String[] args) throws InterruptedException {
112         long start=System.currentTimeMillis();
113         List<String> answerStris=easyCount(new int[]{1,2,3,4});
114         System.out.println(System.currentTimeMillis()-start);
115 
116         for (String string : answerStris) {
117             System.out.println(string);
118         }
119     }
120 }
24点算法实现

  

 

  在电脑上面(神舟i7)大概需要60ms,这个速度初看还是可以接受的,但是到了手机上,居然需要6秒以上!!不过无意中发现,在android系统中对大量运算有优化,貌似计算了一定次数之后系统会缓存编译后的本地代码,然后手机上也可以像电脑上一样秒算了。

 

   之后又花了一天做了个丑陋无比的简单界面,再花了一天时间加上积分功能,修复各种bug,添加广告和统计sdk,上传应用市场。。

 

完整应用体验:http://as.baidu.com/a/item?docid=6481764&pre=web_am_se

 

 

展开阅读全文
打赏
0
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
0
分享
在线直播报名
返回顶部
顶部