一种有趣的扑克牌游戏--算24
众多的扑克牌游戏中，算24是一种不错的锻炼反应力和计算能力的智力游戏，游戏规则大致是这样：从去掉大小王的一副扑克中任意抽取四张，读取上面的数字（其中A算1，2-10就是2-10，J算11，Q算12，K算13），然后进行加减乘除四则运算，早算出24的结果者为赢家，要求是四个数字必须且只能参与计算一次。
举例来说：得到Q，J，2，A四张牌，对应了12，11，2，1四个数字，那么12+11+2-1可以得到24.
算24的难题
之所以拿24当计算目标是因为这是30以内因数最多的数，从小往大有1，2，3，4，6，8，12等七个，这使得计算出结果相对容易，整幅牌中能计算出24的组合比例较高。游戏时，如果看见其中出现一个因数，然后能把剩下的数凑成对应的一个就可以了。比如有8，9，3，2四个，看见8以后，把9，3，2凑成3就行。因为24的因数高达整体的7/13,以上方法法也是游戏中常用的比较快速有效的得分方法。
但对于一些较难的组合则需要四个数统合考虑，这时就比较费神了，需要用到分数法，如著名的被微软采纳进面试题之一的3，8，3，8和网络上有名的3，7，3，7，下面列出了一些常见的算24难题，如果你有兴趣可以做一做（答案在文后）
8,3,8,3
3,7,3,7
12,12,12,10
10,10,4,4
1,4,5,6
2,2,2,9
3,4,7,8
11,11,1,5
1,2,7,7
7,7,4,4
1,4,5,6
1,3,4,6
5,5,5,1
用程序计算24
我们可以把计算24的算式归纳成A_B_C_D的形式，ABCD是四个操作数，_下划线代表+-*/四种操作符，再加上括号的影响，总的计算次数是有限的，如果用程序都试一遍，自然就得出能计算出24的算式。具体来说ABCD进行全排列有24种情况，+-*/进行四选三有64种情况，加上括号对算式的影响有11种具体形式，需要进行全部的计算次数是24*64*11种。
接下来程序就比较好写了，把这些情况列出来即可，具体请见代码：
Caculator类代码
package com.heyang.caculate24;
import java.util.LinkedHashSet;
import java.util.Set;
/**
* 算24的计算器，传入包含四个数的数组，输出可能的计算组合
* 说明：
* 作者：何杨(heyang78@gmail.com)
* 创建时间：2010-6-22 下午12:56:21
* 修改时间：2010-6-22 下午12:56:21
*/
public class Caculator{
// 传入的四个数的数组
private Integer[] arr;
// 存储四个数所有排列方式的集合
private Set<Integer[]> set;
// 加减乘除四种操作符
private static final char Plus='+';
private static final char Minus='-';
private static final char Multi='*';
private static final char Divide='/';
// 包含加减乘除四种操作符的数组
private static final Character[] ArithOperators={Plus,Minus,Multi,Divide};
// 存储四种算术操作符选出三种进行组合的集合，总计有64个元素
private static Set<Character[]> operatorSet;
/**
* 静态构造子
* 用于初始化四种算术操作符的集合
* 不管此类形成多少实例，operatorSet总是一样的
*/
static{
operatorSet=new LinkedHashSet<Character[]>();
// 四选三，允许重复，用循环即可
int i,j,k;
for(i=0;i<4;i++){
for(j=0;j<4;j++){
for(k=0;k<4;k++){
operatorSet.add(new Character[]{ArithOperators[i],ArithOperators[j],ArithOperators[k]});
}
}
}
}
/**
* 传入一个四位数组，将所有的排列方式放入链表
* @param arr
*/
public Caculator(Integer[] arr){
// 保存
this.arr=arr;
// 得到四个数字可能的排列
set=new LinkedHashSet<Integer[]>();
permutation(arr,0,arr.length);
// 打印出可能的算式
printPossibleCacu();
}
/**
* 进行全排列，将所有的排列放入链表
*
* 说明：
* @param arr
* @param start
* @param end
* 创建时间：2010-6-22 下午01:04:44
* 修改时间：2010-6-22 下午01:04:44
*/
private void permutation(Integer[] arr,int start,int end){
if(start<end+1){
permutation(arr,start+1,end);
for(int i=start+1;i<end;i++){
Integer temp;
temp=arr[start];
arr[start]=arr[i];
arr[i]=temp;
permutation(arr,start+1,end);
temp=arr[i];
arr[i]=arr[start];
arr[start]=temp;
}
}
else{
set.add(new Integer[]{arr[0],arr[1],arr[2],arr[3]});
}
}
/**
* 打印可以得到24的算式
*
* 说明：
* 创建时间：2010-6-22 下午01:19:56
* 修改时间：2010-6-22 下午01:19:56
*/
private void printPossibleCacu(){
// 可以得到24的算式集合
Set<String> formulaSet=new LinkedHashSet<String>();
// 遍历算式
for(Character[] arrOperator:operatorSet){
// 遍历四个数
for(Integer[] arrNumber:set){
BaseFormula fomula=null;
if(isPlusOrMinus(arrOperator[0]) && isPlusOrMinus(arrOperator[1]) && isPlusOrMinus(arrOperator[2])){
// 连加减的情况,公式1
fomula=new Formula1(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
}
else if(isMultiOrDivide(arrOperator[0]) && isMultiOrDivide(arrOperator[1]) && isMultiOrDivide(arrOperator[2])){
// 连乘除的情况，公式1
fomula=new Formula1(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
}
else if(isMultiOrDivide(arrOperator[0]) && isPlusOrMinus(arrOperator[1]) && isMultiOrDivide(arrOperator[2])){
// 中间是加减，两边是乘除的情况。
// 公式2
fomula=new Formula2(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
// 公式3
fomula=new Formula3(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
// 公式3
fomula=new Formula31(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
}
else if(isPlusOrMinus(arrOperator[0]) && isMultiOrDivide(arrOperator[1]) && isMultiOrDivide(arrOperator[2])){
// 第一个是加减，后面是乘除的情况。
// 公式4
fomula=new Formula4(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
// 公式5
fomula=new Formula5(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
}
else if(isMultiOrDivide(arrOperator[0]) && isMultiOrDivide(arrOperator[1]) && isPlusOrMinus(arrOperator[2])){
// 前面是乘除，最后一个是加减的情况。
// 公式1
fomula=new Formula1(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
// 公式5
fomula=new Formula5(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
}
else if(isPlusOrMinus(arrOperator[0]) && isMultiOrDivide(arrOperator[1]) && isPlusOrMinus(arrOperator[2])){
// 两边是加减，中间是乘除的情况。
// 公式6
fomula=new Formula6(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
// 公式5
fomula=new Formula61(arrNumber,arrOperator);
if(fomula.isEaqual24()){
formulaSet.add(fomula.getFormulaString());
}
}
}
}
// 输出
if(formulaSet.size()>0){
// 得到结果
System.out.println("'"+arr[0]+","+arr[1]+","+arr[2]+","+arr[3]+"'有"+formulaSet.size()+"种计算方式得到24的结果，具体如下：");
int index=1;
for(String str:formulaSet){
System.out.println((index++)+":"+str);
}
}
else{
// 得不到结果
System.out.println("通过有限次四则运算,'"+arr[0]+","+arr[1]+","+arr[2]+","+arr[3]+"' 不能得到24的计算结果。");
}
System.out.println();
}
// 判断操作符是加减
private static boolean isPlusOrMinus(char c){
return c==Plus || c==Minus;
}
// 判断操作符是乘除
private static boolean isMultiOrDivide(char c){
return c==Multi || c==Divide;
}
/**
* 测试
*
* 说明：
* @param arr
* 创建时间：2010-6-22 下午06:01:09
* 修改时间：2010-6-22 下午06:01:09
*/
public static void main(String[] arr){
new Caculator(new Integer[]{7,2,3,4});
new Caculator(new Integer[]{8,3,8,3});
new Caculator(new Integer[]{3,7,3,7});
new Caculator(new Integer[]{12,12,12,10});
new Caculator(new Integer[]{12,3,12,5});
new Caculator(new Integer[]{10,10,4,4});
new Caculator(new Integer[]{1,4,5,6});
new Caculator(new Integer[]{2,2,2,9});
new Caculator(new Integer[]{2,7,8,9});
new Caculator(new Integer[]{3,4,7,8});
new Caculator(new Integer[]{11,11,1,5});
new Caculator(new Integer[]{1,2,7,7});
new Caculator(new Integer[]{3,6,10,10});
new Caculator(new Integer[]{5,5,10,2});
new Caculator(new Integer[]{9,9,6,2});
new Caculator(new Integer[]{7,7,4,4});
new Caculator(new Integer[]{1,4,5,6});
new Caculator(new Integer[]{1,3,4,6});
new Caculator(new Integer[]{5,5,7,9});
new Caculator(new Integer[]{5,5,5,1});
new Caculator(new Integer[]{1,1,1,1});
new Caculator(new Integer[]{10,10,10,4});
new Caculator(new Integer[]{1,7,9,10});
}
}
BaseFormula类代码
package com.heyang.caculate24;
/**
* 基本公式类，是八种公式的父类
* 说明：此类不能生成实例
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:16:16
* 修改时间：2010-6-22 下午04:16:16
*/
public abstract class BaseFormula{
// 四种操作符
private static final char Plus='+';
private static final char Minus='-';
private static final char Multi='*';
private static final char Divide='/';
// 传入的数组
protected Integer[] arrNumber;
// 第一个操作数
protected double num1;
// 第二个操作数
protected double num2;
// 第三个操作数
protected double num3;
// 第四个操作数
protected double num4;
// 第一个操作符
protected char op1;
// 第二个操作符
protected char op2;
// 第三个操作符
protected char op3;
/**
* 构造函数,用于给成员变量赋值
* @param arrNumber
* @param arrOperator
*/
public BaseFormula(Integer[] arrNumber,Character[] arrOperator){
// 保存数组
this.arrNumber=arrNumber;
// 给四个操作数存值
this.num1=(double)arrNumber[0];
this.num2=(double)arrNumber[1];
this.num3=(double)arrNumber[2];
this.num4=(double)arrNumber[3];
// 给三个操作符存值
this.op1=arrOperator[0];
this.op2=arrOperator[1];
this.op3=arrOperator[2];
}
/**
* 得到计算的结果
* 以下是默认实现，用于连加减，连乘除的情况以及先乘除两个数再加减一个数的情况
*
* 说明：
* @return
* 创建时间：2010-6-22 下午04:22:40
* 修改时间：2010-6-22 下午04:22:40
*/
protected double getCaculatedResult(){
double retval=caculate(num1,op1,num2);
retval=caculate(retval,op2,num3);
retval=caculate(retval,op3,num4);
return retval;
}
/**
* 获得公式的文本状态
* 以下为默认实现，适用于不需要添加括号的情况
*
* 说明：
* 创建时间：2010-6-22 下午04:28:44
* 修改时间：2010-6-22 下午04:28:44
*/
public String getFormulaString() {
return " "+arrNumber[0]+op1+arrNumber[1]+op2+arrNumber[2]+op3+arrNumber[3];
}
/**
* 判断公式的计算结果是否等于24
*
* 说明：
* @return
* 创建时间：2010-6-22 下午04:23:59
* 修改时间：2010-6-22 下午04:23:59
*/
public boolean isEaqual24(){
return Math.abs(getCaculatedResult()-24)<0.000001;
}
/**
* 计算两个数操作的结果
*
* 说明：
* @param op1
* @param operator
* @param op2
* @return
* 创建时间：2010-6-22 下午04:34:24
* 修改时间：2010-6-22 下午04:34:24
*/
protected static double caculate(double op1,char operator,double op2){
if(operator==Plus){
return op1+op2;
}
else if(operator==Minus){
return op1-op2;
}
else if(operator==Multi){
return op1*op2;
}
else if(operator==Divide){
return op1/op2;
}
else{
throw new IllegalArgumentException("未知的操作符"+operator);
}
}
}
八种公式的代码
/**
* 公式一，用于连续加减，连续乘除的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula1 extends BaseFormula{
public Formula1(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
}
/**
* 公式2，用于A*B+-C*D的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula2 extends BaseFormula{
public Formula2(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
protected double getCaculatedResult() {
double retval1=caculate(num1,op1,num2);
double retval2=caculate(num3,op3,num4);
double retval=caculate(retval1,op2,retval2);
return retval;
}
}
/**
* 公式3，用于A*(B+-C*D)的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula3 extends BaseFormula{
public Formula3(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
@Override
protected double getCaculatedResult() {
double retval1=caculate(num3,op3,num4);
double retval2=caculate(num2,op2,retval1);
double retval=caculate(num1,op1,retval2);
return retval;
}
public String getFormulaString() {
return " "+arrNumber[0]+op1+"("+arrNumber[1]+op2+arrNumber[2]+op3+arrNumber[3]+")";
}
}
/**
* 公式31，用于(A*B+-C)*D的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula31 extends BaseFormula{
public Formula31(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
@Override
protected double getCaculatedResult() {
double retval1=caculate(num1,op1,num2);
double retval2=caculate(retval1,op2,num3);
double retval=caculate(retval2,op3,num4);
return retval;
}
public String getFormulaString() {
return " "+"("+arrNumber[0]+op1+arrNumber[1]+op2+arrNumber[2]+")"+op3+arrNumber[3];
}
}
/**
* 公式4，用于A+-B*C*D的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula4 extends BaseFormula{
public Formula4(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
@Override
protected double getCaculatedResult() {
double retval1=caculate(num2,op2,num3);
double retval2=caculate(retval1,op3,num4);
double retval=caculate(num1,op1,retval2);
return retval;
}
}
/**
* 公式5，用于（A+-B）*C*D的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula5 extends BaseFormula{
public Formula5(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
public String getFormulaString() {
return " ("+arrNumber[0]+op1+arrNumber[1]+")"+op2+arrNumber[2]+op3+arrNumber[3];
}
}
/**
* 公式6，用于A+-B*C+-D的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula6 extends BaseFormula{
public Formula6(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
@Override
protected double getCaculatedResult() {
double retval1=caculate(num2,op2,num3);
double retval2=caculate(retval1,op3,num4);
double retval=caculate(num1,op1,retval2);
return retval;
}
}
/**
* 公式61，用于(A+-B)*C+-D的情况
* 说明：
* 作者：heyang(heyang78@gmail.com)
* 创建时间：2010-6-22 下午04:30:32
* 修改时间：2010-6-22 下午04:30:32
*/
public class Formula61 extends BaseFormula{
public Formula61(Integer[] arrNumber,Character[] arrOperator){
super(arrNumber,arrOperator);
}
@Override
protected double getCaculatedResult() {
double retval1=caculate(num1,op1,num2);
double retval2=caculate(retval1,op2,num3);
double retval=caculate(retval2,op3,num4);
return retval;
}
public String getFormulaString() {
return " "+"("+arrNumber[0]+op1+arrNumber[1]+")"+op2+arrNumber[2]+op3+arrNumber[3];
}
}
输出结果
'7,2,3,4'有2种计算方式得到24的结果，具体如下：
1: (7+3)*2+4
2: (3+7)*2+4
'8,3,8,3'有1种计算方式得到24的结果，具体如下：
1: 8/(3-8/3)
'3,7,3,7'有2种计算方式得到24的结果，具体如下：
1: 7*(3+3/7)
2: (3/7+3)*7
'12,12,12,10'有2种计算方式得到24的结果，具体如下：
1: 12*12-12*10
2: 12*12-10*12
'12,3,12,5'有6种计算方式得到24的结果，具体如下：
1: (12*5+12)/3
2: (5*12+12)/3
3: 12*5-12*3
4: 12*5-3*12
5: 5*12-3*12
6: 5*12-12*3
'10,10,4,4'有1种计算方式得到24的结果，具体如下：
1: (10*10-4)/4
'1,4,5,6'有1种计算方式得到24的结果，具体如下：
1: 4/(1-5/6)
'2,2,2,9'有2种计算方式得到24的结果，具体如下：
1: (2+9)*2+2
2: (9+2)*2+2
'2,7,8,9'有2种计算方式得到24的结果，具体如下：
1: (7+9)*2-8
2: (9+7)*2-8
'3,4,7,8'有1种计算方式得到24的结果，具体如下：
1: (7-3)*4+8
'11,11,1,5'有1种计算方式得到24的结果，具体如下：
1: (11*11-1)/5
'1,2,7,7'有1种计算方式得到24的结果，具体如下：
1: (7*7-1)/2
'3,6,10,10'有3种计算方式得到24的结果，具体如下：
1: 6*(3+10/10)
2: 10*(3-6/10)
3: (10/10+3)*6
'5,5,10,2'有1种计算方式得到24的结果，具体如下：
1: 5*(5-2/10)
'9,9,6,2'有2种计算方式得到24的结果，具体如下：
1: 9*(2+6/9)
2: (6/9+2)*9
'7,7,4,4'有1种计算方式得到24的结果，具体如下：
1: 7*(4-4/7)
'1,4,5,6'有1种计算方式得到24的结果，具体如下：
1: 4/(1-5/6)
'1,3,4,6'有1种计算方式得到24的结果，具体如下：
1: 6/(1-3/4)
通过有限次四则运算,'5,5,7,9' 不能得到24的计算结果。
'5,5,5,1'有1种计算方式得到24的结果，具体如下：
1: 5*(5-1/5)
通过有限次四则运算,'1,1,1,1' 不能得到24的计算结果。
通过有限次四则运算,'10,10,10,4' 不能得到24的计算结果。
通过有限次四则运算,'1,7,9,10' 不能得到24的计算结果。
不足之处：
一.以上解法核心还是穷举，应该更向人类思维靠近一些。
二.排列有冗余现象，如1*2*3*4和2*3*4*1就变成了两种方案，这里有时间还要改改。如果是只得到一个答案即可，可以在等于24后打印出文本然后直接return，这样就没有冗余了。当然这是偷懒的做法。
三.列举的公式中有重复的，也许还有没考虑到的情况，这里有时间还要改改。
感谢您看到这里，如果您有更好的解法不妨指教，先谢谢了。