|
锁定老帖子 主题：趣味编程：24点算法实现
精华帖 (0) :: 良好帖 (2) :: 新手帖 (2) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-01-11
最后修改：2009-01-12
恰好我前两天也做了一个，没有考虑优先级，只是把所有的组合和运算符组合了一下，拿上来大家研究研究
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]); if (cal24(numStack, oprStack)) { System.out.print(new StringBuffer(i+oprs[x]+j+oprs[y]+m+oprs[z]+n).reverse().toString()+" = 24 " +(++num)+"\n");
}
}
}
}
}
}
}
}
}
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 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"));
}
}
就是说，1-9 任意给出四个数字，计算24点，可以重复，运算符任意的合法结果是 2870 out Number : 2870 |
| 返回顶楼 | |
|
发表时间：2009-01-11
这是求解空间问题，和迷宫走法什么没有什么本质区别吧。
可以用递归求解，求的过程可以配合附加条件适当做剪枝。最后把整个解空间树求出来。 |
| 返回顶楼 | |
|
发表时间：2009-01-11
楼上是否可以给个递归的算法学习学习
|
| 返回顶楼 | |
|
发表时间：2009-01-11
最后修改：2009-01-11
谁能把代码控制在20行之内， 又有一定可读性。
比赛开始， 楼下继续。 |
| 返回顶楼 | |
|
发表时间：2009-01-12
sdh5724 写道 谁能把代码控制在20行之内， 又有一定可读性。
比赛开始， 楼下继续。 把我python代码里面的记忆处理/或者表达式输出 去掉就20行以内了～ |
| 返回顶楼 | |
|
发表时间：2009-01-12
sdh5724 写道 谁能把代码控制在20行之内， 又有一定可读性。
比赛开始， 楼下继续。 看来这位仁兄可以在20行之内写出如此可读的代码，能否那出来，让我等学习学习呢 |
| 返回顶楼 | |
|
发表时间：2009-01-12
最后修改：2009-01-14
用 Lysee 实现一个穷尽的：
public varlist help(varlist list, bool loose)
{
for [int a in 4 : int b in 4 : int c in 4 : int d in 4]
if (loose or ((1 << a) + (1 << b) + (1 << c) + (1<< d) == 14))
return [list[a], list[b], list[c], list[d]];
}
public strlist evaluate(int a b c d)
{
strlist result = strlist();
for [varlist v in yield(help, [[a, b, c, d], 0]) if (v):
varlist o in yield(help, [['+', '-', '*', '\\'], 1]) if (o):
string x in ["(%[0]%[4]%[1])%[5](%[2]%[6]%[3])",
"((%[0]%[4]%[1])%[5]%[2])%[6]%[3]",
"(%[0]%[4](%[1]%[5]%[2]))%[6]%[3]",
"%[0]%[4]((%[1]%[5]%[2])%[6]%[3])",
"%[0]%[4](%[1]%[5](%[2]%[6]%[3]))"]] {
x = format(x, v + o).trim();
result.add(x) if (eval("return " + x) == 24);
}
result.unique();
return result;
}
= evaluate(3, 6, 1, 9);
|
| 返回顶楼 | |
|
发表时间：2009-01-12
算法不优化,代码过长
|
| 返回顶楼 | |
|
发表时间：2009-01-12
建立数据字典，优先字典组合，其次才是穷举
|
| 返回顶楼 | |
|
发表时间：2009-01-12
最后修改：2009-01-12
qamer 写道 建立数据字典，优先字典组合，其次才是穷举
如果声明了返回类应该能少几行,还有些代码能少几行....用异常也可以少几行. public class My24Point {
static LinkedList<Integer> link = new LinkedList<Integer>();
static StringBuffer buffer ;
public static void main(String[] args) {
Integer[] array = {3,2,5,4};
myRodem( array);
}
private static void myRodem( Integer[] array) {
Integer tmp = 0 ;
while(tmp!=24){
tmp =0 ;
link.clear();
for(Object o :array){
link.add((Integer) o);
}
for(int i =0 ; i<3;i++){
tmp = My24Point.getSum(link);
if(tmp==null){
tmp =0;
break;
}
link.add(tmp);
}
System.out.println("\t\t|"+tmp);
}
}
public static Integer getSum(LinkedList<Integer> link){
int sum = 0;
int first = link.remove(new Random().nextInt(link.size()));
int next = link.remove(new Random().nextInt(link.size()));
int symbol = new Random().nextInt(4);
if(symbol == 0){
sum = first +next;
System.out.print("sum:"+first+"+"+next +"="+sum);
}else if(symbol==1){
sum = first -next;
System.out.print("sum:"+first+"-"+next +"="+sum);
}else if(symbol==2){
sum = first *next;
System.out.print("sum:"+first+"*"+next +"="+sum);
}else if(symbol==3&&next!=0 &&first%next==0){
sum = first / next;
System.out.print("sum:"+first+"+"+next +"="+sum);
}else if(symbol==3&&first!=0&& next/first==0){
sum = next / first;
System.out.print("sum:"+next+"/"+first +"="+sum);
}else{
return null;
}
return sum;
}
}
public class My24Point {
static LinkedList<Integer> link = new LinkedList<Integer>();
static StringBuffer buffer ;
public static void main(String[] args) {
Integer[] array = {3,2,5,4};
myRodem( array,24);
}
private static void myRodem( Integer[] array,int max) {
Integer tmp = 0 ;
while(tmp!=max){
tmp =0 ;link.clear();buffer = new StringBuffer();
for(Object o :array){link.add((Integer) o); }
while(link.size()>=2){
tmp = My24Point.getSum(link);
if(tmp==null){ tmp =0; break;}
link.add(tmp);buffer.append("|");
}
System.out.println(buffer.toString()+"\t\t|"+tmp);
}
}
public static Integer getSum(LinkedList<Integer> link){
int sum = 0;
int first = link.remove(new Random().nextInt(link.size()));
int next = link.remove(new Random().nextInt(link.size()));
int symbol = new Random().nextInt(4);
if(symbol == 0){
sum = first +next;buffer.append(first+"+"+next +"="+sum);
}else if(symbol==1){
sum = first -next;buffer.append(first+"-"+next +"="+sum);
}else if(symbol==2){
sum = first *next;buffer.append(first+"*"+next +"="+sum);
}else if(symbol==3&&next!=0 &&first%next==0){
sum = first / next;buffer.append(first+"+"+next +"="+sum);
}else if(symbol==3&&first!=0&& next/first==0){
sum = next / first;buffer.append(next+"/"+first +"="+sum);
}else{return null;}
return sum;
}
}
|
| 返回顶楼 | |
