24點破解的Java實現 – 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
[java] 
package org.xiazdong; 
 
import java.util.Stack; 
 
public class CalculatorUtils { 
 
    /**
     * 計算後綴表達式
     */ 
    public static String calculateReversePolish(String str) { 
 
        String[] splitStr = str.split(" "); 
        Stack<String> s = new Stack<String>(); 
        for (int i = 0; i < splitStr.length; i++) { 
            String ch = splitStr[i]; 
            if (ch.matches("\\d+.\\d+")||ch.matches("\\d+")) { 
                s.push(ch); 
            } else { 
                if (s.size() >= 2) { 
                    String c1 = s.pop(); 
                    String c2 = s.pop(); 
                    if (ch.equals("+")) { 
                        if(c1.contains(".")||c2.contains(".")){ 
                            s.push(String.valueOf((Double.parseDouble(c2 + "") + Double 
                                .parseDouble(c1 + "")))); 
                        } 
                        else{ 
                            s.push(String.valueOf((Integer.parseInt(c2 + "") + Integer 
                                    .parseInt(c1 + "")))); 
                        } 
                         
                    } else if ("-".equals(ch)) { 
                        if(c1.contains(".")||c2.contains(".")){ 
                        s.push(String.valueOf((Double.parseDouble(c2 + "") – Double 
                                .parseDouble(c1 + "")))); 
                        } 
                        else{ 
                            s.push(String.valueOf((Integer.parseInt(c2 + "") – Integer 
                                    .parseInt(c1 + "")))); 
                        } 
                    } else if ("*".equals(ch)) { 
                        if(c1.contains(".")||c2.contains(".")){ 
                        s.push(String.valueOf((Double.parseDouble(c2 + "") * Double 
                                .parseDouble(c1 + "")))); 
                        } 
                        else{ 
                            s.push(String.valueOf((Integer.parseInt(c2 + "") * Integer 
                                    .parseInt(c1 + "")))); 
                        } 
                    } else if ("/".equals(ch)) { 
                        s.push(String.valueOf((Double.parseDouble(c2 + "") / Double 
                                .parseDouble(c1 + "")))); 
                    } 
 
                } else { 
                    System.out.println("式子有問題!"); 
                    return null; 
                } 
            } 
        } 
        return s.pop(); 
    } 

TfUtils.java

[java] 
package org.xiazdong; 
 
import java.io.Serializable; 
 
public class TfUtils implements Serializable{ 
    private int result; 
    private String expr = "";   //存放中綴表達式 
     
    public String getExpr() { 
        return expr; 
    } 
 
    public void setExpr(String expr) { 
        this.expr = expr; 
    } 
 
    /*
                        (操作符1)
                        /      \ 
                   (操作符2) (操作數4) 
                   /     \ 
              (操作符3)  (操作數3) 
               /     \ 
          (操作數1) (操作數2)
     */ 
    private int tree1[] = new int[7];; // 存放第一棵樹 
    //private int tree2[]; // 存放第二棵樹 
    private final int PLUS = 1; // 加 
    private final int MINUS = 2; // 減 
    private final int MULT = 3; // 乘 
    private final int DIV = 4; // 除 
 
    /**
     * 計算24點的主函數
     */ 
    public void calculate(int a, int b, int c, int d) { 
 
        int data[] = { a, b, c, d }; 
 
         
        // 1.用數組構建一棵樹,其中0,1,3處填操作符;2,4,5,6填充操作數 
        // 2.按照參數a,b,c,d不同順序填充樹,+-*/也填充 
        for (int h = 0; h < 4; h++) { 
            for (int i = 0; i < 4; i++) { 
                if (i == h) { 
                    continue; 
                } 
                for (int j = 0; j < 4; j++) { 
                    if (j == i || j == h) { 
                        continue; 
                    } 
                    for (int k = 0; k < 4; k++) { 
                        if (k == h || k == i || k == j) { 
                            continue; 
                        } 
                        tree1[2] = data[h]; 
                        tree1[4] = data[i]; 
                        tree1[5] = data[j]; 
                        tree1[6] = data[k]; 
 
                        // 填充操作符 
                        for (int m = PLUS; m <= DIV; m++) { 
                            for (int n = PLUS; n <= DIV; n++) { 
                                for (int o = PLUS; o <= DIV; o++) { 
                                    tree1[0] = m; 
                                    tree1[1] = n; 
                                    tree1[3] = o; 
                                    String t[] = new String[4]; 
                                    for (int z = 0; z < 4; z++) { 
                                        switch (tree1[z]) { 
                                        case PLUS: 
                                            t[z] = "+"; 
                                            break; 
                                        case MINUS: 
                                            t[z] = "-"; 
                                            break; 
                                        case MULT: 
                                            t[z] = "*"; 
                                            break; 
                                        case DIV: 
                                            t[z] = "/"; 
                                            break; 
                                        } 
                                    } 
 
                                    // 目前為止tree數組全部已賦值 
                                    String postexpr = tree1[5] + " " + tree1[6] 
                                            + " " + t[3] + " " + tree1[4] + " " 
                                            + t[1] + " " + tree1[2] + " " + t[0]; 
                                    String result = CalculatorUtils 
                                            .calculateReversePolish(postexpr); 
                                    if (Double.parseDouble((result)) == 24.0) { 
                                        expr = "(((" + tree1[5] + t[3] + tree1[6] 
                                                + ")" + t[1] + tree1[4] + ")" 
                                                + t[0] + tree1[2] + ")"; 
                                        System.out.println(expr); 
                                        return; 
                                    } 
                                } 
                            } 
                        } 
                    } 
                } 
            } 
        } 
        //tree2 = new int[7]; 
        for (int h = 0; h < 4; h++) { 
            for (int i = 0; i < 4; i++) { 
                if (i == h) { 
                    continue; 
                } 
                for (int j = 0; j < 4; j++) { 
                    if (j == i || j == h) { 
                        continue; 
                    } 
                    for (int k = 0; k < 4; k++) { 
                        if (k == h || k == i || k == j) { 
                            continue; 
                        } 
                        tree1[3] = data[h]; 
                        tree1[4] = data[i]; 
                        tree1[5] = data[j]; 
                        tree1[6] = data[k]; 
 
                        // 填充操作符 
                        for (int m = PLUS; m <= DIV; m++) { 
                            for (int n = PLUS; n <= DIV; n++) { 
                                for (int o = PLUS; o <= DIV; o++) { 
                                    tree1[0] = m; 
                                    tree1[1] = n; 
                                    tree1[2] = o; 
                                    String t[] = new String[3]; 
                                    for (int z = 0; z < 3; z++) { 
                                        switch (tree1[z]) { 
                                        case PLUS: 
                                            t[z] = "+"; 
                                            break; 
                                        case MINUS: 
                                            t[z] = "-"; 
                                            break; 
                                        case MULT: 
                                            t[z] = "*"; 
                                            break; 
                                        case DIV: 
                                            t[z] = "/"; 
                                            break; 
                                        } 
                                    } 
                                    // 目前為止tree數組全部已賦值 
                                    String postexpr = tree1[4] + " " + tree1[3] 
                                            + " " + t[1] + " " + tree1[6] + " " 
                                            + tree1[5] + " " + t[2] + " " + t[0]; 
                                    String result = CalculatorUtils 
                                            .calculateReversePolish(postexpr); 
                                    if (Double.parseDouble((result)) == 24.0) { 
                                        expr = "((" + tree1[3] + t[1] + tree1[4] 
                                                + ")" + t[0] +"("+tree1[5] 
                                                + t[2] + tree1[6] + "))"; 
                                        System.out.println(expr); 
                                        return; 
                                    } 
                                } 
                            } 
                        } 
                    } 
                } 
            } 
        } 
        expr = "無解"; 
    } 
 
    public int getResult() { 
        return result; 
    } 
 
    public void setResult(int result) { 
        this.result = result; 
    } 
 
 
     

測試代碼:
[html] 
TfUtils tf = new TfUtils(); 
tf.calculate(d1, d2, d3, d4); 
System.out.println(tf.getExpr()); 

輸入為:3,3,7,7
輸出為:(((3/7)+3)*7)
作者:xiazdong

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。