一種有趣的撲克牌游戲--算24
眾多的撲克牌游戲中，算24是一種不錯(cuò)的鍛煉反應(yīng)力和計(jì)算能力的智力游戲，游戲規(guī)則大致是這樣：從去掉大小王的一副撲克中任意抽取四張，讀取上面的數(shù)字（其中A算1，2-10就是2-10，J算11，Q算12，K算13），然后進(jìn)行加減乘除四則運(yùn)算，早算出24的結(jié)果者為贏家，要求是四個(gè)數(shù)字必須且只能參與計(jì)算一次。
舉例來(lái)說(shuō)：得到Q，J，2，A四張牌，對(duì)應(yīng)了12，11，2，1四個(gè)數(shù)字，那么12+11+2-1可以得到24.
算24的難題
之所以拿24當(dāng)計(jì)算目標(biāo)是因?yàn)檫@是30以內(nèi)因數(shù)最多的數(shù)，從小往大有1，2，3，4，6，8，12等七個(gè)，這使得計(jì)算出結(jié)果相對(duì)容易，整幅牌中能計(jì)算出24的組合比例較高。游戲時(shí)，如果看見(jiàn)其中出現(xiàn)一個(gè)因數(shù)，然后能把剩下的數(shù)湊成對(duì)應(yīng)的一個(gè)就可以了。比如有8，9，3，2四個(gè)，看見(jiàn)8以后，把9，3，2湊成3就行。因?yàn)?4的因數(shù)高達(dá)整體的7/13,以上方法法也是游戲中常用的比較快速有效的得分方法。
但對(duì)于一些較難的組合則需要四個(gè)數(shù)統(tǒng)合考慮，這時(shí)就比較費(fèi)神了，需要用到分?jǐn)?shù)法，如著名的被微軟采納進(jìn)面試題之一的3，8，3，8和網(wǎng)絡(luò)上有名的3，7，3，7，下面列出了一些常見(jiàn)的算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
用程序計(jì)算24
我們可以把計(jì)算24的算式歸納成A_B_C_D的形式，ABCD是四個(gè)操作數(shù)，_下劃線代表+-*/四種操作符，再加上括號(hào)的影響，總的計(jì)算次數(shù)是有限的，如果用程序都試一遍，自然就得出能計(jì)算出24的算式。具體來(lái)說(shuō)ABCD進(jìn)行全排列有24種情況，+-*/進(jìn)行四選三有64種情況，加上括號(hào)對(duì)算式的影響有11種具體形式，需要進(jìn)行全部的計(jì)算次數(shù)是24*64*11種。
接下來(lái)程序就比較好寫了，把這些情況列出來(lái)即可，具體請(qǐng)見(jiàn)代碼：
Caculator類代碼
package com.heyang.caculate24;
import java.util.LinkedHashSet;
import java.util.Set;
/**
* 算24的計(jì)算器，傳入包含四個(gè)數(shù)的數(shù)組，輸出可能的計(jì)算組合
* 說(shuō)明：
* 作者：何楊(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午12:56:21
* 修改時(shí)間：2010-6-22 下午12:56:21
*/
public class Caculator{
// 傳入的四個(gè)數(shù)的數(shù)組
private Integer[] arr;
// 存儲(chǔ)四個(gè)數(shù)所有排列方式的集合
private Set<Integer[]> set;
// 加減乘除四種操作符
private static final char Plus='+';
private static final char Minus='-';
private static final char Multi='*';
private static final char Divide='/';
// 包含加減乘除四種操作符的數(shù)組
private static final Character[] ArithOperators={Plus,Minus,Multi,Divide};
// 存儲(chǔ)四種算術(shù)操作符選出三種進(jìn)行組合的集合，總計(jì)有64個(gè)元素
private static Set<Character[]> operatorSet;
/**
* 靜態(tài)構(gòu)造子
* 用于初始化四種算術(shù)操作符的集合
* 不管此類形成多少實(shí)例，operatorSet總是一樣的
*/
static{
operatorSet=new LinkedHashSet<Character[]>();
// 四選三，允許重復(fù)，用循環(huán)即可
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]});
}
}
}
}
/**
* 傳入一個(gè)四位數(shù)組，將所有的排列方式放入鏈表
* @param arr
*/
public Caculator(Integer[] arr){
// 保存
this.arr=arr;
// 得到四個(gè)數(shù)字可能的排列
set=new LinkedHashSet<Integer[]>();
permutation(arr,0,arr.length);
// 打印出可能的算式
printPossibleCacu();
}
/**
* 進(jìn)行全排列，將所有的排列放入鏈表
*
* 說(shuō)明：
* @param arr
* @param start
* @param end
* 創(chuàng)建時(shí)間：2010-6-22 下午01:04:44
* 修改時(shí)間：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的算式
*
* 說(shuō)明：
* 創(chuàng)建時(shí)間：2010-6-22 下午01:19:56
* 修改時(shí)間：2010-6-22 下午01:19:56
*/
private void printPossibleCacu(){
// 可以得到24的算式集合
Set<String> formulaSet=new LinkedHashSet<String>();
// 遍歷算式
for(Character[] arrOperator:operatorSet){
// 遍歷四個(gè)數(shù)
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])){
// 第一個(gè)是加減，后面是乘除的情況。
// 公式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])){
// 前面是乘除，最后一個(gè)是加減的情況。
// 公式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){
// 得到結(jié)果
System.out.println("'"+arr[0]+","+arr[1]+","+arr[2]+","+arr[3]+"'有"+formulaSet.size()+"種計(jì)算方式得到24的結(jié)果，具體如下：");
int index=1;
for(String str:formulaSet){
System.out.println((index++)+":"+str);
}
}
else{
// 得不到結(jié)果
System.out.println("通過(guò)有限次四則運(yùn)算,'"+arr[0]+","+arr[1]+","+arr[2]+","+arr[3]+"' 不能得到24的計(jì)算結(jié)果。");
}
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;
}
/**
* 測(cè)試
*
* 說(shuō)明：
* @param arr
* 創(chuàng)建時(shí)間：2010-6-22 下午06:01:09
* 修改時(shí)間：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;
/**
* 基本公式類，是八種公式的父類
* 說(shuō)明：此類不能生成實(shí)例
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:16:16
* 修改時(shí)間：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='/';
// 傳入的數(shù)組
protected Integer[] arrNumber;
// 第一個(gè)操作數(shù)
protected double num1;
// 第二個(gè)操作數(shù)
protected double num2;
// 第三個(gè)操作數(shù)
protected double num3;
// 第四個(gè)操作數(shù)
protected double num4;
// 第一個(gè)操作符
protected char op1;
// 第二個(gè)操作符
protected char op2;
// 第三個(gè)操作符
protected char op3;
/**
* 構(gòu)造函數(shù),用于給成員變量賦值
* @param arrNumber
* @param arrOperator
*/
public BaseFormula(Integer[] arrNumber,Character[] arrOperator){
// 保存數(shù)組
this.arrNumber=arrNumber;
// 給四個(gè)操作數(shù)存值
this.num1=(double)arrNumber[0];
this.num2=(double)arrNumber[1];
this.num3=(double)arrNumber[2];
this.num4=(double)arrNumber[3];
// 給三個(gè)操作符存值
this.op1=arrOperator[0];
this.op2=arrOperator[1];
this.op3=arrOperator[2];
}
/**
* 得到計(jì)算的結(jié)果
* 以下是默認(rèn)實(shí)現(xiàn)，用于連加減，連乘除的情況以及先乘除兩個(gè)數(shù)再加減一個(gè)數(shù)的情況
*
* 說(shuō)明：
* @return
* 創(chuàng)建時(shí)間：2010-6-22 下午04:22:40
* 修改時(shí)間：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;
}
/**
* 獲得公式的文本狀態(tài)
* 以下為默認(rèn)實(shí)現(xiàn)，適用于不需要添加括號(hào)的情況
*
* 說(shuō)明：
* 創(chuàng)建時(shí)間：2010-6-22 下午04:28:44
* 修改時(shí)間：2010-6-22 下午04:28:44
*/
public String getFormulaString() {
return " "+arrNumber[0]+op1+arrNumber[1]+op2+arrNumber[2]+op3+arrNumber[3];
}
/**
* 判斷公式的計(jì)算結(jié)果是否等于24
*
* 說(shuō)明：
* @return
* 創(chuàng)建時(shí)間：2010-6-22 下午04:23:59
* 修改時(shí)間：2010-6-22 下午04:23:59
*/
public boolean isEaqual24(){
return Math.abs(getCaculatedResult()-24)<0.000001;
}
/**
* 計(jì)算兩個(gè)數(shù)操作的結(jié)果
*
* 說(shuō)明：
* @param op1
* @param operator
* @param op2
* @return
* 創(chuàng)建時(shí)間：2010-6-22 下午04:34:24
* 修改時(shí)間：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);
}
}
}
八種公式的代碼
/**
* 公式一，用于連續(xù)加減，連續(xù)乘除的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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)的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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的情況
* 說(shuō)明：
* 作者：heyang(heyang78@gmail.com)
* 創(chuàng)建時(shí)間：2010-6-22 下午04:30:32
* 修改時(shí)間：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];
}
}
輸出結(jié)果
'7,2,3,4'有2種計(jì)算方式得到24的結(jié)果，具體如下：
1: (7+3)*2+4
2: (3+7)*2+4
'8,3,8,3'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: 8/(3-8/3)
'3,7,3,7'有2種計(jì)算方式得到24的結(jié)果，具體如下：
1: 7*(3+3/7)
2: (3/7+3)*7
'12,12,12,10'有2種計(jì)算方式得到24的結(jié)果，具體如下：
1: 12*12-12*10
2: 12*12-10*12
'12,3,12,5'有6種計(jì)算方式得到24的結(jié)果，具體如下：
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種計(jì)算方式得到24的結(jié)果，具體如下：
1: (10*10-4)/4
'1,4,5,6'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: 4/(1-5/6)
'2,2,2,9'有2種計(jì)算方式得到24的結(jié)果，具體如下：
1: (2+9)*2+2
2: (9+2)*2+2
'2,7,8,9'有2種計(jì)算方式得到24的結(jié)果，具體如下：
1: (7+9)*2-8
2: (9+7)*2-8
'3,4,7,8'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: (7-3)*4+8
'11,11,1,5'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: (11*11-1)/5
'1,2,7,7'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: (7*7-1)/2
'3,6,10,10'有3種計(jì)算方式得到24的結(jié)果，具體如下：
1: 6*(3+10/10)
2: 10*(3-6/10)
3: (10/10+3)*6
'5,5,10,2'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: 5*(5-2/10)
'9,9,6,2'有2種計(jì)算方式得到24的結(jié)果，具體如下：
1: 9*(2+6/9)
2: (6/9+2)*9
'7,7,4,4'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: 7*(4-4/7)
'1,4,5,6'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: 4/(1-5/6)
'1,3,4,6'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: 6/(1-3/4)
通過(guò)有限次四則運(yùn)算,'5,5,7,9' 不能得到24的計(jì)算結(jié)果。
'5,5,5,1'有1種計(jì)算方式得到24的結(jié)果，具體如下：
1: 5*(5-1/5)
通過(guò)有限次四則運(yùn)算,'1,1,1,1' 不能得到24的計(jì)算結(jié)果。
通過(guò)有限次四則運(yùn)算,'10,10,10,4' 不能得到24的計(jì)算結(jié)果。
通過(guò)有限次四則運(yùn)算,'1,7,9,10' 不能得到24的計(jì)算結(jié)果。
不足之處：
一.以上解法核心還是窮舉，應(yīng)該更向人類思維靠近一些。
二.排列有冗余現(xiàn)象，如1*2*3*4和2*3*4*1就變成了兩種方案，這里有時(shí)間還要改改。如果是只得到一個(gè)答案即可，可以在等于24后打印出文本然后直接return，這樣就沒(méi)有冗余了。當(dāng)然這是偷懶的做法。
三.列舉的公式中有重復(fù)的，也許還有沒(méi)考慮到的情況，這里有時(shí)間還要改改。
感謝您看到這里，如果您有更好的解法不妨指教，先謝謝了。