java 24点算法实现

青旅半醒 2021-11-22 18:08 193阅读 0赞

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

## 　　算法实现 ##

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

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

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

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

实现代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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，上传应用市场。。

![241931021372140.png][]

完整应用体验：[http://as.baidu.com/a/item?docid=6481764&pre=web\_am\_se][http_as.baidu.com_a_item_docid_6481764_pre_web_am_se]

转载于:https://www.cnblogs.com/Mr-Nobody/p/3750252.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/d7d6bc00e7e64457acc0b31b688c3536.png
[241931021372140.png]: /images/20211122/86c6fc4335094ae9a11a6dfb146fea38.png
[http_as.baidu.com_a_item_docid_6481764_pre_web_am_se]: http://as.baidu.com/a/item?docid=6481764&pre=web_am_se