| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 562 人关注过本帖
标题:关于24点算法
只看楼主 加入收藏
hcypx
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2010-4-6
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:3 
关于24点算法
24点算法是怎么样的,怎么用Java语言实现?
搜索更多相关主题的帖子: 算法 
2010-04-24 21:05
myhnuhai
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:3
帖 子:425
专家分:1725
注 册:2010-3-17
收藏
得分:0 
计算24点算法

基本原理是穷举4个整数所有可能的表达式,然后对表达式求值。

表达式的定义: expression = (expression|number) operator (expression|number)
因为能使用的4种运算符 + - * / 都是2元运算符,所以本文中只考虑2元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。

由上所述,构造所有可能的表达式的算法如下:
(1) 将4个整数放入数组中
(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,
(2.1) 对 + - * / 每一个运算符,
  (2.1.1) 根据此排列的两个数字和运算符,计算结果
  (2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中
  (2.1.3) 对新的数组,重复步骤 2
  (2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉

可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。

在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。

括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。

不要让肮脏的记忆,迷失了原本纯洁的心灵!
2010-04-25 19:11
myhnuhai
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:3
帖 子:425
专家分:1725
注 册:2010-3-17
收藏
得分:10 
public class Test24Point{
    public static void main(String[] args){
     int index = 0 ;
     int temp = 0 ;
     int totalSuc = 0 ;
      
     int numb[] = new int[4];//the first four numbers
     double num[][] = new double[36][3];//three numbers after calculating
     double total[] = new double[6];//the number after three steps of calculating
      
      
      
     double p[][] = new double[6][8];
     double q[][] = new double[3][7];
      
      
      
     //System.out.println(2465%108);
     //System.out.println(2465/108);
      
     System.out.println("\"a--b\"means\"b-a\"");
     System.out.println("\"a//b\"means\"b/a\"\n");
      
    /* for(int h = 0; h <= 9; h ++)//Get the first four numbers for calculating and store into the array numb[4];.
      for(int i = 0; i <= 9; i ++)
       for(int j = 0; j <= 9; j ++)
        for(int k = 0; k <= 9; k ++){
         numb[0] = h ;
         numb[1] = i ;
         numb[2] = j ;
         numb[3] = k ;  
        }*/
  for(int i = 0 ; i < 4 ; i ++){
   numb[i] = Integer.parseInt(args[i]);  
  }
         
       for(int i = 0; i < 3; i ++)//Get two of the four to calculate and then store the new number into the array p;
        for(int j = i + 1; j < 4 ; j ++,temp ++){
         p[temp][0] = numb[i] + numb[j];  
         p[temp][1] = numb[i] - numb[j];
         p[temp][2] = numb[j] - numb[i];
         p[temp][3] = numb[i] * numb[j];
         if(numb[j] != 0)
          p[temp][4] = numb[i] / (double)numb[j];
         else
          p[temp][4] = 10000;
         if(numb[i] != 0)
          p[temp][5] = numb[j] / (double)numb[i];
         else
          p[temp][5] = 10000;
         
         
         
        switch(temp){
         case 0:p[temp][6] = numb[2]; p[temp][7] = numb[3];break;
         case 1:p[temp][6] = numb[1]; p[temp][7] = numb[3];break;
         case 2:p[temp][6] = numb[1]; p[temp][7] = numb[2];break;
         case 3:p[temp][6] = numb[0]; p[temp][7] = numb[3];break;
         case 4:p[temp][6] = numb[0]; p[temp][7] = numb[2];break;
         case 5:p[temp][6] = numb[0]; p[temp][7] = numb[1];
        }
         
       }
         
  for(int k = 0,tem = 0; k < 6; k ++)//Get the possible three numbers and store into the array num[36][3] for calculating .
   for(int l = 0; l < 6; l ++,tem ++){
    num[tem][0] = p[k][l] ;
    num[tem][1] = p[k][6] ;
    num[tem][2] = p[k][7] ;
   
     
    for(int t = 2,m = 0, n = 0,te = 0; t >= 0; t --,te ++){//Get two of the three to calculate and then store the new number into the array q;  
       m = (t + 1)%3;
       n = (t + 2)%3;
       q[te][6] = num[tem][t];
        
       q[te][0] = num[tem][m] + num[tem][n];
       q[te][1] = num[tem][m] - num[tem][n];
       q[te][2] = num[tem][n] - num[tem][m];
       q[te][3] = num[tem][m] * num[tem][n];
       if(num[tem][n] != 0)
        q[te][4] = num[tem][m] / (double)num[tem][n];
       else
        q[te][4] = 10000 ;
       if(num[tem][m] != 0)
        q[te][5] = num[tem][n] / (double)num[tem][m];
       else
        q[te][5] = 10000 ;
      }
     
      for(int u = 0; u < 3; u ++)
        for(int v = 0; v < 6; v ++){
         if(u == 2){//We must insure that the old value is in the left ,so the result string can be appended rightly.
          total[0] = q[u][6] + q[u][v];
          total[1] = q[u][6] - q[u][v];
          total[2] = q[u][v] - q[u][6];
          total[3] = q[u][v] * q[u][6];
          if(q[u][6] != 0)
           total[4] = q[u][6] / (double)q[u][v];
          else
           total[4] = 10000;
          if(q[u][v] != 0)
           total[5] = q[u][v] / (double)q[u][6];
          else
           total[5] = 10000;
          }
         else{
          total[0] = q[u][v] + q[u][6];
          total[1] = q[u][v] - q[u][6];
          total[2] = q[u][6] - q[u][v];
          total[3] = q[u][v] * q[u][6];
          if(q[u][6] != 0)
           total[4] = q[u][v] / (double)q[u][6];
          else
           total[4] = 10000;
          if(q[u][v] != 0)
           total[5] = q[u][6] / (double)q[u][v];
          else
           total[5] = 10000;
         }
         
          for(int s = 0 ; s < 6 ; s ++){
           if(total[s]>23.9999&&total[s]<24.0001){
            //System.out.println("24!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
            totalSuc ++ ;
            //print the expression
       char x[] = new char[3];
       int n0 = index ;
       String expre = "" ;
       String expre1 = "" ;
       int n1 = index/108;//the first composition and its operator.
       int n2 = index%108/6;//the second composition and its operator.
       int n3 = index%6;//the last operator.
      

        //now ready to printout the equation.
          switch(n1){
               
               case 0:expre += "((a+b)";x[1]=’c’;x[2]=’d’;break;
               case 1:expre += "((a-b)";x[1]=’c’;x[2]=’d’;break;
               case 2:expre += "((b-a)";x[1]=’c’;x[2]=’d’;break;
               case 3:expre += "((a*b)";x[1]=’c’;x[2]=’d’;break;
               case 4:expre += "((a/b)";x[1]=’c’;x[2]=’d’;break;
               case 5:expre += "((b/a)";x[1]=’c’;x[2]=’d’;break;
               case 6:expre += "((a+c)";x[1]=’b’;x[2]=’d’;break;
               case 7:expre += "((a-c)";x[1]=’b’;x[2]=’d’;break;
               case 8:expre += "((c-a)";x[1]=’b’;x[2]=’d’;break;
               case 9:expre += "((a*c)";x[1]=’b’;x[2]=’d’;break;
               case 10:expre += "((a/c)";x[1]=’b’;x[2]=’d’;break;
               case 11:expre += "((c/a)";x[1]=’b’;x[2]=’d’;break;
               case 12:expre += "((a+d)";x[1]=’b’;x[2]=’c’;break;
               case 13:expre += "((a-d)";x[1]=’b’;x[2]=’c’;break;
               case 14:expre += "((d-a)";x[1]=’b’;x[2]=’c’;break;
               case 15:expre += "((a*d)";x[1]=’b’;x[2]=’c’;break;
               case 16:expre += "((a/d)";x[1]=’b’;x[2]=’c’;break;
               case 17:expre += "((d/a)";x[1]=’b’;x[2]=’c’;break;
               case 18:expre += "((b+c)";x[1]=’a’;x[2]=’d’;break;
               case 19:expre += "((b-c)";x[1]=’a’;x[2]=’d’;break;
               case 20:expre += "((c-b)";x[1]=’a’;x[2]=’d’;break;
               case 21:expre += "((b*c)";x[1]=’a’;x[2]=’d’;break;
               case 22:expre += "((b/c)";x[1]=’a’;x[2]=’d’;break;
               case 23:expre += "((c/b)";x[1]=’a’;x[2]=’d’;break;
               case 24:expre += "((b+d)";x[1]=’a’;x[2]=’c’;break;
               case 25:expre += "((b-d)";x[1]=’a’;x[2]=’c’;break;
               case 26:expre += "((d-b)";x[1]=’a’;x[2]=’c’;break;
               case 27:expre += "((b*d)";x[1]=’a’;x[2]=’c’;break;
               case 28:expre += "((b/d)";x[1]=’a’;x[2]=’c’;break;
               case 29:expre += "((d/b)";x[1]=’a’;x[2]=’c’;break;
               case 30:expre += "((c+d)";x[1]=’a’;x[2]=’b’;break;
               case 31:expre += "((c-d)";x[1]=’a’;x[2]=’b’;break;
               case 32:expre += "((d-c)";x[1]=’a’;x[2]=’b’;break;
               case 33:expre += "((c*d)";x[1]=’a’;x[2]=’b’;break;
               case 34:expre += "((c/d)";x[1]=’a’;x[2]=’b’;break;
               case 35:expre += "((d/c)";x[1]=’a’;x[2]=’b’;
              }
               
              switch(n2){
               
               case 0:expre += "+" +x[1] +")";x[1]=x[2];break;//x[0] and x[1].
               case 1:expre += "-" +x[1] +")";x[1]=x[2];break;
               case 2:expre += "--" +x[1] +")";x[1]=x[2];break;
               case 3:expre += "*" +x[1] +")";x[1]=x[2];break;
               case 4:expre += "/" +x[1] +")";x[1]=x[2];break;
               case 5:expre += "//" +x[1] +")";x[1]=x[2];break;
               
               case 6:expre += "+" +x[2] +")";x[1]=x[1];break;//x[2] and x[0].
               case 7:expre += "--" +x[2] +")";x[1]=x[1];break;
               case 8:expre += "-" +x[2] +")";x[1]=x[1];break;
               case 9:expre += "*" +x[2] +")";x[1]=x[1];break;
               case 10:expre += "//" +x[2] +")";x[1]=x[1];break;
               case 11:expre += "/" +x[2] +")";x[1]=x[1];break;
               
               case 12:expre1 += x[1] + "+" + x[2] +"))";x[1]=’(’;break;//x[1] and x[2].
               case 13:expre1 += x[1] + "-" + x[2] +"))";x[1]=’(’;break;
               case 14:expre1 += x[1] + "--" + x[2] +"))";x[1]=’(’;break;
               case 15:expre1 += x[1] + "*" + x[2] +"))";x[1]=’(’;break;
               case 16:expre1 += x[1] + "/" + x[2] +"))";x[1]=’(’;break;
               case 17:expre1 += x[1] + "//" + x[2] +"))";x[1]=’(’;
              }
               
              switch(n3){
               
               case 0:expre += "+" +x[1] + expre1;break;
               case 1:expre += "-" +x[1] + expre1;break;
               case 2:expre += "--" +x[1] + expre1;break;
               case 3:expre += "*" +x[1] + expre1;break;
               case 4:expre += "/" +x[1] + expre1;break;
               case 5:expre += "//" +x[1] + expre1;
              }
              expre = expre.replace(’a’,(char)(numb[0] + 48));
              expre = expre.replace(’b’,(char)(numb[1] + 48));
              expre = expre.replace(’c’,(char)(numb[2] + 48));
              expre = expre.replace(’d’,(char)(numb[3] + 48));
                    
              System.out.println(expre+"  ");
           }
           //System.out.println("total : " + total[s] + " index :" +"\n\n");
            
               
               index ++ ;
       }
              
     }
         
      }System.out.println("The number of total successful expressions is : " + totalSuc);
 }
        
}

不要让肮脏的记忆,迷失了原本纯洁的心灵!
2010-04-25 19:12
hcypx
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2010-4-6
收藏
得分:0 
回复 3楼 myhnuhai
"a--b"means"b-a"
"a//b"means"b/a"

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    at Test24Point.main(Test24Point.java:34)
会有个这样的错误呢
2010-04-26 13:57
快速回复:关于24点算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.023135 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved