歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

24點破解的Java實現

一、基本思想

要想計算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

  1. package org.xiazdong;  
  2.   
  3. import java.util.Stack;  
  4.   
  5. public class CalculatorUtils {  
  6.   
  7.     /** 
  8.      * 計算後綴表達式 
  9.      */  
  10.     public static String calculateReversePolish(String str) {  
  11.   
  12.         String[] splitStr = str.split(" ");  
  13.         Stack<String> s = new Stack<String>();  
  14.         for (int i = 0; i < splitStr.length; i++) {  
  15.             String ch = splitStr[i];  
  16.             if (ch.matches("\\d+.\\d+")||ch.matches("\\d+")) {  
  17.                 s.push(ch);  
  18.             } else {  
  19.                 if (s.size() >= 2) {  
  20.                     String c1 = s.pop();  
  21.                     String c2 = s.pop();  
  22.                     if (ch.equals("+")) {  
  23.                         if(c1.contains(".")||c2.contains(".")){  
  24.                             s.push(String.valueOf((Double.parseDouble(c2 + "") + Double  
  25.                                 .parseDouble(c1 + ""))));  
  26.                         }  
  27.                         else{  
  28.                             s.push(String.valueOf((Integer.parseInt(c2 + "") + Integer  
  29.                                     .parseInt(c1 + ""))));  
  30.                         }  
  31.                           
  32.                     } else if ("-".equals(ch)) {  
  33.                         if(c1.contains(".")||c2.contains(".")){  
  34.                         s.push(String.valueOf((Double.parseDouble(c2 + "") - Double  
  35.                                 .parseDouble(c1 + ""))));  
  36.                         }  
  37.                         else{  
  38.                             s.push(String.valueOf((Integer.parseInt(c2 + "") - Integer  
  39.                                     .parseInt(c1 + ""))));  
  40.                         }  
  41.                     } else if ("*".equals(ch)) {  
  42.                         if(c1.contains(".")||c2.contains(".")){  
  43.                         s.push(String.valueOf((Double.parseDouble(c2 + "") * Double  
  44.                                 .parseDouble(c1 + ""))));  
  45.                         }  
  46.                         else{  
  47.                             s.push(String.valueOf((Integer.parseInt(c2 + "") * Integer  
  48.                                     .parseInt(c1 + ""))));  
  49.                         }  
  50.                     } else if ("/".equals(ch)) {  
  51.                         s.push(String.valueOf((Double.parseDouble(c2 + "") / Double  
  52.                                 .parseDouble(c1 + ""))));  
  53.                     }  
  54.   
  55.                 } else {  
  56.                     System.out.println("式子有問題!");  
  57.                     return null;  
  58.                 }  
  59.             }  
  60.         }  
  61.         return s.pop();  
  62.     }  
  63. }  

TfUtils.java

  1. package org.xiazdong;  
  2.   
  3. import java.io.Serializable;  
  4.   
  5. public class TfUtils implements Serializable{  
  6.     private int result;  
  7.     private String expr = "";   //存放中綴表達式   
  8.       
  9.     public String getExpr() {  
  10.         return expr;  
  11.     }  
  12.   
  13.     public void setExpr(String expr) {  
  14.         this.expr = expr;  
  15.     }  
  16.   
  17.     /* 
  18.                         (操作符1) 
  19.                         /      \  
  20.                    (操作符2) (操作數4)  
  21.                    /     \  
  22.               (操作符3)  (操作數3)  
  23.                /     \  
  24.           (操作數1) (操作數2) 
  25.      */  
  26.     private int tree1[] = new int[7];; // 存放第一棵樹   
  27.     //private int tree2[]; // 存放第二棵樹   
  28.     private final int PLUS = 1// 加   
  29.     private final int MINUS = 2// 減   
  30.     private final int MULT = 3// 乘   
  31.     private final int DIV = 4// 除   
  32.   
  33.     /** 
  34.      * 計算24點的主函數 
  35.      */  
  36.     public void calculate(int a, int b, int c, int d) {  
  37.   
  38.         int data[] = { a, b, c, d };  
  39.   
  40.           
  41.         // 1.用數組構建一棵樹,其中0,1,3處填操作符;2,4,5,6填充操作數   
  42.         // 2.按照參數a,b,c,d不同順序填充樹,+-*/也填充   
  43.         for (int h = 0; h < 4; h++) {  
  44.             for (int i = 0; i < 4; i++) {  
  45.                 if (i == h) {  
  46.                     continue;  
  47.                 }  
  48.                 for (int j = 0; j < 4; j++) {  
  49.                     if (j == i || j == h) {  
  50.                         continue;  
  51.                     }  
  52.                     for (int k = 0; k < 4; k++) {  
  53.                         if (k == h || k == i || k == j) {  
  54.                             continue;  
  55.                         }  
  56.                         tree1[2] = data[h];  
  57.                         tree1[4] = data[i];  
  58.                         tree1[5] = data[j];  
  59.                         tree1[6] = data[k];  
  60.   
  61.                         // 填充操作符   
  62.                         for (int m = PLUS; m <= DIV; m++) {  
  63.                             for (int n = PLUS; n <= DIV; n++) {  
  64.                                 for (int o = PLUS; o <= DIV; o++) {  
  65.                                     tree1[0] = m;  
  66.                                     tree1[1] = n;  
  67.                                     tree1[3] = o;  
  68.                                     String t[] = new String[4];  
  69.                                     for (int z = 0; z < 4; z++) {  
  70.                                         switch (tree1[z]) {  
  71.                                         case PLUS:  
  72.                                             t[z] = "+";  
  73.                                             break;  
  74.                                         case MINUS:  
  75.                                             t[z] = "-";  
  76.                                             break;  
  77.                                         case MULT:  
  78.                                             t[z] = "*";  
  79.                                             break;  
  80.                                         case DIV:  
  81.                                             t[z] = "/";  
  82.                                             break;  
  83.                                         }  
  84.                                     }  
  85.   
  86.                                     // 目前為止tree數組全部已賦值   
  87.                                     String postexpr = tree1[5] + " " + tree1[6]  
  88.                                             + " " + t[3] + " " + tree1[4] + " "  
  89.                                             + t[1] + " " + tree1[2] + " " + t[0];  
  90.                                     String result = CalculatorUtils  
  91.                                             .calculateReversePolish(postexpr);  
  92.                                     if (Double.parseDouble((result)) == 24.0) {  
  93.                                         expr = "(((" + tree1[5] + t[3] + tree1[6]  
  94.                                                 + ")" + t[1] + tree1[4] + ")"  
  95.                                                 + t[0] + tree1[2] + ")";  
  96.                                         System.out.println(expr);  
  97.                                         return;  
  98.                                     }  
  99.                                 }  
  100.                             }  
  101.                         }  
  102.                     }  
  103.                 }  
  104.             }  
  105.         }  
  106.         //tree2 = new int[7];   
  107.         for (int h = 0; h < 4; h++) {  
  108.             for (int i = 0; i < 4; i++) {  
  109.                 if (i == h) {  
  110.                     continue;  
  111.                 }  
  112.                 for (int j = 0; j < 4; j++) {  
  113.                     if (j == i || j == h) {  
  114.                         continue;  
  115.                     }  
  116.                     for (int k = 0; k < 4; k++) {  
  117.                         if (k == h || k == i || k == j) {  
  118.                             continue;  
  119.                         }  
  120.                         tree1[3] = data[h];  
  121.                         tree1[4] = data[i];  
  122.                         tree1[5] = data[j];  
  123.                         tree1[6] = data[k];  
  124.   
  125.                         // 填充操作符   
  126.                         for (int m = PLUS; m <= DIV; m++) {  
  127.                             for (int n = PLUS; n <= DIV; n++) {  
  128.                                 for (int o = PLUS; o <= DIV; o++) {  
  129.                                     tree1[0] = m;  
  130.                                     tree1[1] = n;  
  131.                                     tree1[2] = o;  
  132.                                     String t[] = new String[3];  
  133.                                     for (int z = 0; z < 3; z++) {  
  134.                                         switch (tree1[z]) {  
  135.                                         case PLUS:  
  136.                                             t[z] = "+";  
  137.                                             break;  
  138.                                         case MINUS:  
  139.                                             t[z] = "-";  
  140.                                             break;  
  141.                                         case MULT:  
  142.                                             t[z] = "*";  
  143.                                             break;  
  144.                                         case DIV:  
  145.                                             t[z] = "/";  
  146.                                             break;  
  147.                                         }  
  148.                                     }  
  149.                                     // 目前為止tree數組全部已賦值   
  150.                                     String postexpr = tree1[4] + " " + tree1[3]  
  151.                                             + " " + t[1] + " " + tree1[6] + " "  
  152.                                             + tree1[5] + " " + t[2] + " " + t[0];  
  153.                                     String result = CalculatorUtils  
  154.                                             .calculateReversePolish(postexpr);  
  155.                                     if (Double.parseDouble((result)) == 24.0) {  
  156.                                         expr = "((" + tree1[3] + t[1] + tree1[4]  
  157.                                                 + ")" + t[0] +"("+tree1[5]  
  158.                                                 + t[2] + tree1[6] + "))";  
  159.                                         System.out.println(expr);  
  160.                                         return;  
  161.                                     }  
  162.                                 }  
  163.                             }  
  164.                         }  
  165.                     }  
  166.                 }  
  167.             }  
  168.         }  
  169.         expr = "無解";  
  170.     }  
  171.   
  172.     public int getResult() {  
  173.         return result;  
  174.     }  
  175.   
  176.     public void setResult(int result) {  
  177.         this.result = result;  
  178.     }  
  179.   
  180.   
  181.       
  182. }  

測試代碼:

  1. TfUtils tf = new TfUtils();  
  2. tf.calculate(d1, d2, d3, d4);  
  3. System.out.println(tf.getExpr());  

輸入為:3,3,7,7

輸出為:(((3/7)+3)*7)

Copyright © Linux教程網 All Rights Reserved