一種有趣的撲克牌游戲--算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，這樣就沒有冗余了。當然這是偷懶的做法。
三.列舉的公式中有重復的，也許還有沒考慮到的情況，這里有時間還要改改。
感謝您看到這里，如果您有更好的解法不妨指教，先謝謝了。