import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;
public class Point24Dnaymic {
/**
* @author 张伟
*
* 24点游戏 原题链接
*
* http://www.ieee.org.cn/dispbbs.asp?boardID=60&ID=15720
*
* 动态规划解法
*
*/
private static final double MAX = 700;
private static final double KEY = 573;
private static final double n = 6;
double[] num = new double[] { 1, 2, 3, 4, 7, 25 };
private TreeSet<Double>[] all = new TreeSet[(int) Math.pow(2, n)];
private HashMap<Double, String>[] map = (HashMap<Double, String>[]) new HashMap[(int) Math
.pow(2, n)];
public void printTrace(int a, double key) {
/**
* 注意要转义小数点 .
* %.0f小数位0输出
*/
String s = map[a].get(new Double(key)).replaceAll("\\.0", "");
// String s = map[a].get(new Double(key));
String[] tmp = s.split(":");
if (tmp[0].equals("#"))
System.out.printf("%.0f", key);
else {
System.out.print("(");
printTrace(new Integer(tmp[1]).intValue(), new Double(tmp[2])
.intValue());
System.out.print(tmp[0]);
printTrace(new Integer(tmp[3]).intValue(), new Double(tmp[4])
.intValue());
System.out.print(")");
}
// for(String s1:tmp)
// System.out.println(s1);
}
public void search() {
// 单个的存值
for (int i = 0; i < n; i++) {
int j = (int) Math.pow(2, i);
all[j].add(num[i]);
map[j].put(num[i], "#:");
}
for (int x = 1; x <= (int) Math.pow(2, n) - 1; x++)
for (int j = 1; j < x; j++) {
// if(!all[j].isEmpty())continue;
if ((x & j) == j) {
int k = x - j;
if (j < k)
comp(all[j], all[k], x, j, k);
}
}
}
public static void main(String[] args) {
Point24Dnaymic s = new Point24Dnaymic();
for (int i = 0; i < s.all.length; i++) {
s.all[i] = new TreeSet<Double>();
}
for (int i = 0; i < s.map.length; i++) {
s.map[i] = new HashMap<Double, String>();
}
s.search();
s.printTrace((int) Math.pow(2, n) - 1, KEY);
}
public void comp(TreeSet<Double> a, TreeSet<Double> b, int serial,
int start, int end) {
Iterator<Double> ita = a.iterator();
Iterator<Double> itb = b.iterator();
while (ita.hasNext()) {
double x = ita.next().doubleValue();
while (itb.hasNext()) {
double y = itb.next().doubleValue();
all[serial].add(x + y);
map[serial].put(x + y, "+" + ":" + start + ":" + x + ":" + end
+ ":" + y);
if (x * y < MAX)
{
all[serial].add(x * y);
map[serial].put(x * y, "*" + ":" + start + ":" + x + ":"
+ end + ":" + y);
}
if (x > y) {
all[serial].add(x - y);
map[serial].put(x - y, "-" + ":" + start + ":" + x + ":"
+ end + ":" + y);
if (y != 0 && (x % y == 0)) {
all[serial].add(x / y);
map[serial].put(x / y, "/" + ":" + start + ":" + x
+ ":" + end + ":" + y);
}
} else if (x != y) {
all[serial].add(y - x);
map[serial].put(y - x, "-" + ":" + end + ":" + y + ":"
+ start + ":" + x);
if (x != 0 && (x % y == 0))
all[serial].add(y / x);
map[serial].put(y / x, "/" + ":" + end + ":" + y + ":"
+ start + ":" + x);
}
}
}
}
}
- 1
- 2
- 3
前往页