24点计算

  package org.qinghua.dispatcher.test;

import java.util.Stack;

public class Gift {
	static String[] oprs = { "+", "-", "*", "/" };
	static Stack<Integer> numStack = new Stack<Integer>();
	static Stack<String> oprStack = new Stack<String>();

	public static void main(String[] args) {
		int num = 0;
		for (int i = 1; i < 10; i++) {
			for (int x = 0; x < 4; x++) {
				for (int j = 1; j < 10; j++) {
					for (int y = 0; y < 4; y++) {
						for (int m = 1; m < 10; m++) {
							for (int z = 0; z < 4; z++) {
								for (int n = 1 ; n < 10; n++) {
									numStack.push(i);
									numStack.push(j);
									numStack.push(m);
									numStack.push(n);
									oprStack.push(oprs[x]);
									oprStack.push(oprs[y]);
									oprStack.push(oprs[z]);
									// printStack(numStack);
									// System.out.print(",");
									// printStack(oprStack);
									if (cal24(numStack, oprStack)) {
										//printStack(numStack);
										//System.out.print(",");
										///printStack(oprStack);
										//;
										System.out.print(
												new StringBuffer(i+oprs[x]+j+oprs[y]+m+oprs[z]+n).reverse().toString()+" = 24 "
										 +(++num)+"\n");
									}
									// System.out.print(i+oprs[x]+j+oprs[y]+m+oprs[u]+n+"
									// ");

								}
							}
						}
					}
				}
			}
		}
		System.out.println("Number : " + num);
	}

	static void printStack(Stack stack) {
		System.out.print(stack);
		stack.clear();
	}

	static boolean cal24(Stack<Integer> ints, Stack<String> oprs) {
		int r = 0;
		while (!oprs.empty()) {
			String opr = oprs.pop();
			int a = ints.pop();
			int b = ints.pop();
			r = oprtwo(opr, a, b);
			ints.push(r);
			if (r == 0) {
				ints.clear();
				oprs.clear();
				return false;
			}
			
		}

		if ((r = ints.pop()) == 24) {
			ints.clear();
			oprs.clear();
			return true;
		}
		return false;
	}

	static int oprtwo(String opr, int a, int b) {
		if (opr.equals("+"))
			return a + b;
		if (opr.equals("-"))
			return a - b<0?0:a-b;
		if (opr.equals("*"))
			return a * b;
		if (opr.equals("/") && b != 0 && a > b && isIntegerRst(a, b)) {
			return a / b;
		} else
			return 0;
	}

	static boolean gyouxian(String opr1, String opr2) {
		if (opr1.equals(opr2))
			return false;
		if (opr1.equals("+") && (opr2.equals("/") || opr2.equals("*")))
			return false;
		if (opr1.equals("-") && (opr2.equals("/") || opr2.equals("*")))
			return false;
		return true;

	}

	static boolean isIntegerRst(int ai, int bi) {
		Integer a = ai;
		Integer b = bi;
		Float an = Float.valueOf(a.toString());
		Float bn = Float.valueOf(b.toString());
		//System.out.println(an/bn);
		return (String.valueOf((an / bn)).endsWith(".0"));
	}
}

评论

3 楼 andyjojo 2009-01-15  

java的double经常会不精确，试试BigDecimal

2 楼 kjj 2009-01-15  

你说得很对，我当初考虑的时候特地排除了小数的，稍微修改一下，应该没问题，可以处理小数

1 楼 andyjojo 2009-01-15  

算法有个问题是处理不了需要小数时的解，如1 5 5 5、 1 3 4 6等。
你的算法对于这些值是无解的。可以考虑使用分数。而不是像你的程序那样，必须可以整除才行。
static boolean isIntegerRst(int ai, int bi)