日期:2014-05-20  浏览次数:20905 次

24点算法求助
现在我有计算+,-,*,/,()算式的算法
即给一个加减乘除包含括号的字符串式子,该算法能算出该算式的值int getResult(String expresion);
现在打算写一个24点游戏的,
随便取出4张扑克牌,例如2,4,J,7
相应抽出24点的式子是(2+4)*(11-7)
JQKA分别是11,12,13,1
其中有个功能是电脑算出能拼出24点的算式,并表示出来,如果没有,就显示没有解


我是打算现将得出的4个数,全排列,同时在数字之间的间隙加上+ - * /运算符号
这样大概就有4!*4^3中可能性,还要添上括号
这就更麻烦了

现在小弟向大家求助一下,提供一下思路,小弟感激不尽

------解决方案--------------------
http://zhidao.baidu.com/question/10699890.html
------解决方案--------------------
随便写了个小例子
因为排列组合的关系,有重复的计算式子,如果不允许重复,LZ自己过滤掉重复的结果
Java code
import java.util.*;
import javax.script.*;
public class Test {
    public static void main(String[] args) throws Throwable {
        int[] num = {2, 4, 11, 7};
        //int[] num = {11, 12, 13, 1};
        List<String> list = exp(num);
        ScriptEngineManager sem = new ScriptEngineManager();
        ScriptEngine se = sem.getEngineByName("JavaScript");
        for (String s : list) {
            Object v = se.eval(s);
            double d = 0;
            if (v instanceof Integer) {
                d = ((Integer)v).intValue();
            } else if (v instanceof Double) {
                d = ((Double)v).doubleValue();
            }

            if (d - 24 == 0) {
                System.out.printf("%s=%d\n", s, (int)d);
            }
        }
    }

    public static List<String> exp(int[] num) {
        List<String> list = new ArrayList<String>();
        if (num==null || num.length < 2) return list;

        if (num.length == 2) {
            list.add(String.format("%s+%s", num[0], num[1]));
            list.add(String.format("%s-%s", num[0], num[1]));
            list.add(String.format("%s-%s", num[1], num[0]));
            list.add(String.format("%s*%s", num[0], num[1]));
            list.add(String.format("%s.0/%s", num[0], num[1]));
            list.add(String.format("%s.0/%s", num[1], num[0]));
        }

        int[] tmp = new int[num.length-1];
        for (int i=0; i<num.length; i++) {
            for (int j=0, k=0; j<num.length; j++) {
                if (j != i) tmp[k++] = num[j];
            }

            List<String> sub = exp(tmp);

            for (String s : sub) {
                list.add(String.format("%s+%s", num[i], s));
                list.add(String.format("%s-%s", num[i], s));
                list.add(String.format("%s-%s", s, num[i]));
                list.add(String.format("%s*%s", num[i], s));
                list.add(String.format("%s*%s", s, num[i]));
                list.add(String.format("%s.0/%s", num[i], s));
                list.add(String.format("%s/%s.0", s, num[i]));
                
                String[] sa = s.split("\\d+([.]\\d+)?");
                if (! s.startsWith("(")) {
                    if (sa[1].equals("+") || sa[1].equals("-")) {
                        list.add(String.format("%s*(%s)", num[i], s));
                        list.add(String.format("%s.0/(%s)", num[i], s));
                        list.add(String.format("(%s)/%s.0", s, num[i]));
                    } else {
                        list.add(String.format("%s.0/(%s)", num[i], s));
                        int index = s.indexOf(sa[1]);
                        String b = s.substring(0, index);
                        String c = s.substring(index);
                        list.add(String.format("(%s+%s)%s", num[i], b, c));
                        list.add(String.format("(%s-%s)%s", num[i], b, c));
                        list.add(String.format("(%s-%s)%s", b, num[i], c));
                        list.add(String.format("(%s*%s)%s", num[i], b, c));
                        list.add(String.format("(%s.0/%s)%s", num[i], b, c));
                        list.add(String.format("(%s/%s.0)%s", b, num[i], c));
                    }
                }   
            }
        }

        return list;
    }
}