二十四点算法

package com.onezero;
/**
 * <b>计算24游戏</b>
 * <br/>
 * 给出四张1到13之间的整数，通过+、-、*、/、()组合成合法表达式并使结果等于24；
 * 如给出1、3、4、6，可以组合乘6/(1-(3/4))
 * <br/>
 * 算法仍然是穷举法，不过删除了一些重复的式子。
 * 为了精确表示除法结果，这里实现<code>有理数</code>类。
 * 基本思想：先在四张牌中选出两张，有6种，再计算这两张牌的值，有5种；
 * 剩下两张牌及刚才计算的值可看作三张牌。在选择两张，有3种；
 * 再计算，又有5种，最后剩下两张，在计算，又是5种；最后比较这些值是否等于24即可。
 * 共有6*5*3*5*5=2250
 * <br/>
 * <b>没有除去连乘和连加的重复</b>
 * <br/>
 * <b>使用方法：</b><code>com.onezero.算24.计算二十四(new int[]{1,3,4,6})</code>
 * @see com.onezero.有理数
 * @version 	1.0, 2009年1月18日
 * @author Anguo Wen
 *
 */
public final class 算24 {
	private static int[] 四选二 = { 0, 1, 2, 3,  0, 2, 1, 3,  0, 3, 1, 2,  
		1, 2, 0, 3,  1, 3, 0, 2,  2, 3, 0, 1 };
	private static int[] 三选二 = { 0, 1, 2,  0, 2, 1,  1, 2, 0 };
	private static StringBuilder 表达式;
	
	/**
	 * 计算二十四，如果有解，打印出所有的解(删除部分重复解)
	 * 
	 * @param 四张牌 输入的四张1到13之间的牌
	 * @return 是否可以算的24
	 * @throws  ArithmeticException  如果参数 <code>四张牌</code> 少于四个数.
	 */
	public static boolean 计算二十四(final int[] 四张牌) {
		if(四张牌.length<4)throw new ArithmeticException("必须为四张牌");
		有理数[] 纸牌 = new 有理数[4];
		for(int h=0;h<4;h++)纸牌[h] = new 有理数(四张牌[h]);
		boolean 成功 = false;
		有理数[] 临时 = new 有理数[4];
		String[] 输出 = new String[4];
		有理数 结果;
		四张: for (int i = 0; i < 四选二.length; i += 4) {
			for (int t = 0; t < i; t += 4) {
				if (重复(纸牌[四选二[i]], 纸牌[四选二[i + 1]], 纸牌[四选二[t]], 纸牌[四选二[t + 1]]))
					continue 四张;
			}
			for (int j = 0; j < 5; j++) {
				if (继续(纸牌[四选二[i]], 纸牌[四选二[i + 1]], j))
					continue;
				临时[0] = 计算(纸牌[四选二[i]], 纸牌[四选二[i + 1]], j,
						纸牌[四选二[i]].toString(), 纸牌[四选二[i + 1]].toString());
				输出[0] = 表达式.toString();
				临时[1] = 纸牌[四选二[i + 2]];
				输出[1] = 临时[1].toString();
				临时[2] = 纸牌[四选二[i + 3]];
				输出[2] = 临时[2].toString();

				三张: for (int k = 0; k < 三选二.length; k += 3) {
					for (int s = 0; s < k; s += 3) {
						if (重复(临时[三选二[k]], 临时[三选二[k + 1]], 临时[三选二[s]],
								临时[三选二[s + 1]]))
							continue 三张;
					}

					if (k >= 6)
						for (int r = 0; r < i; r += 4) {
							if (重复(临时[三选二[k]], 临时[三选二[k + 1]], 纸牌[四选二[r]],
									纸牌[四选二[r + 1]]))
								continue 三张;
						}
					for (int l = 0; l < 5; l++) {
						if (继续(临时[三选二[k]], 临时[三选二[k + 1]], l))
							continue;
						临时[3] = 计算(临时[三选二[k]], 临时[三选二[k + 1]], l, 输出[三选二[k]],
								输出[三选二[k + 1]]);
						输出[3] = 表达式.toString();
						for (int m = 0; m < 5; m++) {
							if (继续(临时[三选二[k + 2]], 临时[3], m))
								continue;
							结果 = 计算(临时[三选二[k + 2]], 临时[3], m, 输出[三选二[k + 2]],
									输出[3]);

							if (结果.等于(24)) {
								System.out.print(表达式.substring(1,
										表达式.length() - 1) + "\t");
								成功 = true;
							}
						}

					}
				}
			}
		}
		return 成功;
	}

	private static boolean 重复(有理数 数一, 有理数 数二, 有理数 数三, 有理数 数四) {
		return (数一.equals(数三) && 数二.equals(数四))
				|| (数一.equals(数四) && 数二.equals(数三));
	}

	private static boolean 继续(有理数 数一, 有理数 数二, int 运算符) {
		switch (运算符) {
		case 1:
			return 数一.equals(数二);
		case 2:
			return 数一.等于(2) && 数二.等于(2);
		case 3:
			return 数二.等于(1);
		case 4:
			return 数一.等于(1) || 数一.equals(数二);
		default:
			return false;
		}
	}

	private static 有理数 计算(有理数 分数一, 有理数 分数二, int 运算符, String 式一, String 式二) {
		表达式 = new StringBuilder("(");
		switch (运算符) {
		case 0:// 分数一+分数二
			表达式.append(式一).append("+").append(式二).append(")");
			return 分数一.加(分数二);
		case 1:// |分数一-分数二|
			有理数 结果 = 分数一.减(分数二);
			if (结果.小于零()) {
				结果.负();
				表达式.append(式二).append("-").append(式一).append(")");
			} else 
				表达式.append(式一).append("-").append(式二).append(")");
			return 结果;
		case 2:// 分数一*分数二
			表达式.append(式一).append("*").append(式二).append(")");
			return 分数一.乘(分数二);
		case 3:// 分数一/分数二
			表达式.append(式一).append("/").append(式二).append(")");
			return 分数一.除(分数二);
		default:// 分数二/分数一
			表达式.append(式二).append("/").append(式一).append(")");
			return 分数二.除(分数一);
		}
	}
	
	/**
	 * 主函数 测试用
	 * 打印出所有的可能组合的解及有解组合的总数
	 * 输入命令java -cp 24点游戏.jar com.onezero.算24
	 * @param args
	 */
	public static void main(String[] args) {
		int 有解 = 0;
		for (int i = 1; i < 14; i++)
			for (int j = i; j < 14; j++)
				for (int k = j; k < 14; k++)
					for (int l = k; l < 14; l++)
						if (计算二十四(new int[] { i, j, k, l })) {
							System.out.println();
							有解++;
						}
		System.out.println(有解);
	}
}

class 有理数 {
	private int 分子;
	private int 分母 = 1;

	有理数(int 分子) {
		this.分子 = 分子;
	}

	有理数(int 分子, int 分母) {
		if (分母 <= 0)
			throw new ArithmeticException("分母不可小于等于零！");
		int 公约数 = 最大公约数(分子 < 0 ? -分子 : 分子, 分母);
		this.分子 = 分子 / 公约数;
		this.分母 = 分母 / 公约数;
	}

	public boolean 等于(int 整数) {
		return 整数 == this.分子 && 1 == this.分母;
	}

	private int 最大公约数(int 数一, int 数二) {
		if (数一 == 数二) {
			if (数一 == 0)
				throw new ArithmeticException("求最大公约数不可同时为零！");
			return 数一;
		}
		if (数一 == 0)
			return 数二;
		if (数二 == 0)
			return 数一;
		else if (数一 > 数二)
			return 最大公约数(数二, 数一 % 数二);
		else
			return 最大公约数(数一, 数二 % 数一);
	}

	public 有理数 加(有理数 分数二) {
		return new 有理数(this.分子 * 分数二.分母 + this.分母 * 分数二.分子, this.分母 * 分数二.分母);
	}

	public 有理数 减(有理数 分数二) {
		return new 有理数(this.分子 * 分数二.分母 - this.分母 * 分数二.分子, this.分母 * 分数二.分母);
	}

	public 有理数 乘(有理数 分数二) {
		return new 有理数(this.分子 * 分数二.分子, this.分母 * 分数二.分母);
	}

	public 有理数 除(有理数 分数二) {
		if (分数二.分子 == 0)
			throw new ArithmeticException("不可除零！");
		return new 有理数(this.分子 * 分数二.分母, this.分母 * 分数二.分子);
	}

	public boolean 小于零() {
		return this.分子 < 0;
	}

	public void 负() {
		this.分子 = -this.分子;
	}

	public String toString() {
		if (this.分母 == 1)
			return Integer.toString(this.分子);
		return this.分子 + "/" + this.分母;
	}

	public boolean equals(Object 数) {
		if (!(数 instanceof 有理数))
			return false;
		有理数 数二 = (有理数) 数;
		return this.分子 == 数二.分子 && this.分母 == 数二.分母;
	}
}