大家帮个帮，设计一个棋牌 21点的 算法。

Question

   题目入下：   
  
 计算21是流行的扑克游戏。其方法是任意取出4张牌，A J Q K 王牌 算 1，其它牌按点数计算，花色不计。目标是通过加、减、乘、除和括号最终算出24。设计一个程序，输入4个数字（1~10），则列出所有可能计算结果为24的方案。要求：
方案不能重复（加法乘法交换律等算不同方案）。
计算中局部可以为分数，结果为整数即可（如 3 3 7 7 算法： (3 + 3/7)*7）
如果没有找到方案输出：无解。请大家给个思路

Answer 1

昨天有空做了下，所有可行解是列出来了，基本一半的代码都在判断括号了....
问题是出来很多计算机认为不重复，但是在人看来应该算是重复的可行解
基本思路就是用map存储所有解的表达式和结果值，最后判断输出可行解
import java.util.HashMap;/*
 * 任意四个数 1~10 输出他们运算结果为24的所有结果
 * 如：3 3 7 7  (3+3/7)*7 = 24
 */
public class Test24 {
//定义最终结果集，key为操作数字的字符串(去重)，value为结果
private static HashMap<String, Double> result = new HashMap<String, Double>(); public static void main(String[] args) {
double[] nums = { 3, 9, 5, 10 };
/*
 * 运算分为两种情况： （2个数运算）运算（2个数运算） 和（3个数运算）运算（最后一个数）
 * 
 * 烦人的括号啊...大多数代码都是判断括号    很雷人=。=
 */
//第一种：任选两个数(3种情况)和剩下两个数操作 
// 1: 12 对 34
HashMap<String, Double> res1 = result(nums[0], nums[1]);
HashMap<String, Double> res2 = result(nums[2], nums[3]);
result.putAll(result(res1, res2));
// 2: 13 对24
HashMap<String, Double> res3 = result(nums[0], nums[2]);
HashMap<String, Double> res4 = result(nums[1], nums[3]);
result.putAll(result(res3, res4));
// 3: 14 对23
HashMap<String, Double> res5 = result(nums[0], nums[3]);
HashMap<String, Double> res6 = result(nums[1], nums[2]);
result.putAll(result(res5, res6));
/*
 * 第二种：任选1个数(4种情况)和剩下三个数操作 
 * 可以转化为：任选2个数，操作完和第三个数操作，然后再和第四个数操作
 * 总共十二种情况(下面就简写了)
 *  12——3——4
 *  12——4——3
 *  13——2——4
 *  13——4——2
 *  14——2——3
 *  14——3——2
 *  23——1——4
 *  23——4——1
 *  24——1——3
 *  24——3——1
 *  34——1——2
 *  34——2——1
 */
result.putAll(result(result(result(nums[0], nums[1]), nums[2]), nums[3]));
result.putAll(result(result(result(nums[0], nums[1]), nums[3]), nums[2]));
result.putAll(result(result(result(nums[0], nums[2]), nums[1]), nums[3]));
result.putAll(result(result(result(nums[0], nums[2]), nums[3]), nums[1]));
result.putAll(result(result(result(nums[0], nums[3]), nums[1]), nums[2]));
result.putAll(result(result(result(nums[0], nums[3]), nums[2]), nums[1]));
result.putAll(result(result(result(nums[1], nums[2]), nums[0]), nums[3]));
result.putAll(result(result(result(nums[1], nums[2]), nums[3]), nums[0]));
result.putAll(result(result(result(nums[1], nums[3]), nums[0]), nums[2]));
result.putAll(result(result(result(nums[1], nums[3]), nums[2]), nums[0]));
result.putAll(result(result(result(nums[2], nums[3]), nums[0]), nums[1]));
result.putAll(result(result(result(nums[2], nums[3]), nums[1]), nums[0]));
boolean fail = true;
for (String str : result.keySet()) {
//一般来说浮点数计算可以得到24.0的，怕意外就......
if (Math.abs(result.get(str) - 24)<0.0001) {
//去掉所有烦人的 double值后面的".0"
System.out.println(str.replaceAll("\\.0", "") + "=" + 24);
fail=false;
}
}
if(fail){
System.out.println("无可行解哦~~");
}
}

//判断一个操作串是否是加法或减法
public static boolean isAddOrDel(String str){
if(str.contains("+")||str.contains("-")){
return true;
}
return false;
} // 任意两个数运算的结果集,对于任何两个数运算结果为六种（减法和除法有两种结果）
public static HashMap<String, Double> result(double num1, double num2) {
HashMap<String, Double> map = new HashMap<String, Double>();
map.put(num1 + "+" + num2, num1 + num2);
map.put(num1 + "-" + num2, num1 - num2);
map.put(num2 + "-" + num1, num2 - num1);
map.put(num1 + "*" + num2, num1 * num2);
map.put(num1 + "/" + num2, num1 / num2);
map.put(num2 + "/" + num1, num2 / num1);
return map;
} // 对一个结果集和一个数操作得到新的结果集
public static HashMap<String, Double> result(HashMap<String, Double> map1,
double num2) {
HashMap<String, Double> map = new HashMap<String, Double>();
for (String str1 : map1.keySet()) {
//如果上一次做的是+或者-操作，那么仅有*和/需要加括号
if(isAddOrDel(str1)){
map.put( str1  + "+" + num2, map1.get(str1) + num2);
map.put( str1 +  "-" + num2, map1.get(str1) - num2);
map.put(num2 + "-" + "(" + str1 + ")", num2 - map1.get(str1));
map.put("(" + str1 + ")" + "*" + num2, map1.get(str1) * num2);
map.put("(" + str1 + ")" + "/" + num2, map1.get(str1) / num2);
map.put(num2 + "/" + "(" + str1 + ")", num2 / map1.get(str1));
}else{ //上一次是乘除操作那么仅有作为被除数需要加括号
map.put( str1  + "+" + num2, map1.get(str1) + num2);
map.put( str1 +  "-" + num2, map1.get(str1) - num2);
map.put(num2 + "-"  + str1 , num2 - map1.get(str1));
map.put( str1  + "*" + num2, map1.get(str1) * num2);
map.put( str1  + "/" + num2, map1.get(str1) / num2);
map.put(num2 + "/" + "(" + str1 + ")", num2 / map1.get(str1));
}
}
return map;
} // 对两个结果集操作得到新的结果集
public static HashMap<String, Double> result(HashMap<String, Double> map1,
HashMap<String, Double> map2) {
HashMap<String, Double> map = new HashMap<String, Double>();
for (String str1 : map1.keySet()) {
for (String str2 : map2.keySet()) {
if(isAddOrDel(str1)&&isAddOrDel(str2)){
//两个都是加、减
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + "(" + str2 + ")", map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + "(" + str1 + ")", map2.get(str2) - map1.get(str1));
map.put("(" + str1 + ")" + "*" + "(" + str2 + ")", map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}else if(isAddOrDel(str1)&&!isAddOrDel(str2)){
//第一个是加、减
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + str2 , map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + "(" + str1 + ")", map2.get(str2) - map1.get(str1));
map.put("(" + str1 + ")" + "*" + str2, map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}else if(!isAddOrDel(str1)&&isAddOrDel(str2)){
//第二个是加、减
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + "(" + str2 + ")", map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + str1 , map2.get(str2) - map1.get(str1));
map.put(str1 + "*" + "(" + str2 + ")", map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}else{
//两个都是乘、除
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + str2 , map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + str1 , map2.get(str2) - map1.get(str1));
map.put(str1 + "*" + "(" + str2 + ")", map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}
}
}
return map;
}
}输出：
(3+9)*10/5=24
(10-5)*3+9=24
10/(5/(3+9))=24
((3+9)/5)*10=24
9-((5-10)*3)=24
(3+9)/(5/10)=24
((3+9)*10)/5=24

Answer 2

把判断上一个运算的方法改成：//判断上一个操作串是否是加法或减法
public static boolean isAddOrDel(String str){
char sign1 = str.charAt(str.length()-4);//一般操作字符串的操作符
char sign2 = str.charAt(str.length()-5);//最后一位是10.0的操作符
if(sign1=='+'||sign2=='+'||sign1=='-'||sign2=='-'){
return true;
}
return false;
}可以去掉一些重复的，剩下的继续想。。也等高人指点

Answer 3

写了一个递归穷举算法，就是把4个数字的任何两个进行加减乘除，然后一直递归下去。代码不长，
package hr.test;import java.util.*;public class game24 {
//记录结算的中间过程
public ArrayList<String> queue=new ArrayList<String>();
//24点计算
public void compute(int[] data){
if(data.length==1){
if(data[0]==24){
print(); //打印正确结果
}
return ;
}

sort(data); //逆序排序，为了使得运算中总是大数减去或除以小数
//枚举数据组中的任何两个数，进行加减乘除计算
for(int i=0;i<data.length-1;i++)
for(int j=i+1;j<data.length;j++){

//进行加法计算，将计算结果构成一个新的数据组
int[] newData=new int[data.length-1];
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]+data[j];
queue.add(data[i]+"+"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);

//进行减法计算，将计算结果构成一个新的数据组
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]-data[j];
queue.add(data[i]+"-"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);

//进行乘法计算，将计算结果构成一个新的数据组
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]*data[j];
queue.add(data[i]+"*"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);

//进行除法计算(条件，除的尽且不除以0)，将计算结果构成一个新的数据组
if(data[i]%data[j]==0&&data[j]!=0){
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]/data[j];
queue.add(data[i]+"/"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);
}
}


}
//所有数据逆序排序
public void sort(int[] data){
for(int i=1;i<data.length;i++){
int temp=data[i];
int j=i-1;
for(;j>=0;j--){
if(temp>data[j])data[j+1]=data[j];
else break;
}
data[j+1]=temp;
}
}
//打印中间过程
private void print(){
for(String q:queue)
System.out.print(q+"\t");
System.out.println();
}
//测试
public static void main(String[] args) {
game24 g=new game24();
int[] data={5,6,7,8};
g.compute(data);
}
}