|
锁定老帖子 主题：趣味编程：24点算法实现
精华帖 (0) :: 良好帖 (2) :: 新手帖 (2) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-01-15
求一个解就结束的程序。可扩展到5，6，7，...个数求解24，25，....。
public class Calc24 { private String[] ops = new String[]{"+", "a-b", "b-a", "*", "a/b", "b/a"}; private boolean calc(double[] ns) { if (ns.length == 1) { if (Math.abs(ns[0] - 24) < 0.01) return true; } double a, b, c; String op; for (int i = 0; i < ns.length - 1; i++) for (int j = i + 1; j < ns.length; j++) for (int k = 0; k < ops.length; k++) { a = ns[i]; b = ns[j]; op = ops[k]; c = eval(a, b, op); double[] ns1 = new double[ns.length - 1]; for (int m = 0, n = 0; m < ns.length; m++) { if (m != i && m != j) ns1[n++] = ns[m]; } ns1[ns1.length - 1] = c; if (calc(ns1)) { System.out.println(a + " " + op + " " + b); return true; } } return false; } private double eval(double a, double b, String op) { if (op.equals("+")) return a + b; else if (op.equals("a-b")) return a - b; else if (op.equals("b-a")) return b - a; else if (op.equals("*")) return a * b; else if (op.equals("a/b")) { if (b == 0) return Integer.MAX_VALUE * 1.0; else return a / b; } else if (op.equals("b/a")) { if (a == 0) return Integer.MAX_VALUE * 1.0; else return b / a; } else throw new RuntimeException("unknow op:" + op); } private void run(int[] ns) { double[] ns1 = new double[ns.length]; for (int i = 0; i < ns1.length; i++) { ns1[i] = ns[i] * 1.0; } calc(ns1); } public static void main(String[] args) { Calc24 calc24 = new Calc24(); calc24.run(new int[]{3, 4, 7, 9}); System.out.println("*************************"); calc24.run(new int[]{3, 3, 7, 7}); System.out.println("*************************"); calc24.run(new int[]{4, 4, 7, 7,7}); } } |
| 返回顶楼 | |
|
发表时间：2009-01-15
稍微修改一下可求全部解。
public class Calc24New { private String[] ops = new String[]{"+", "a-b", "b-a", "*", "a/b", "b/a"}; private void calc(double[] ns, String expression) { if (ns.length == 1) { if (Math.abs(ns[0] - 24) < 0.01) System.out.println("expression = " + expression); } else { double a, b, c; String op, s; for (int i = 0; i < ns.length - 1; i++) for (int j = i + 1; j < ns.length; j++) for (int k = 0; k < ops.length; k++) { a = ns[i]; b = ns[j]; op = ops[k]; c = eval(a, b, op); s = "(" + exp(a, b, op) + "=" + c + ")"; double[] ns1 = new double[ns.length - 1]; for (int m = 0, n = 0; m < ns.length; m++) { if (m != i && m != j) ns1[n++] = ns[m]; } ns1[ns1.length - 1] = c; calc(ns1, expression + s); } } } private double eval(double a, double b, String op) { if (op.equals("+")) return a + b; else if (op.equals("a-b")) return a - b; else if (op.equals("b-a")) return b - a; else if (op.equals("*")) return a * b; else if (op.equals("a/b")) { if (b == 0) return Integer.MAX_VALUE * 1.0; else return a / b; } else if (op.equals("b/a")) { if (a == 0) return Integer.MAX_VALUE * 1.0; else return b / a; } else throw new RuntimeException("unknow op:" + op); } private String exp(double a, double b, String op) { if (op.equals("+")) return a + "+" + b; else if (op.equals("a-b")) return a + "-" + b; else if (op.equals("b-a")) return b + "-" + a; else if (op.equals("*")) return a + "*" + b; else if (op.equals("a/b")) return a + "/" + b; else if (op.equals("b/a")) return b + "/" + a; else throw new RuntimeException("unknow op:" + op); } private void run(int[] ns) { double[] ns1 = new double[ns.length]; for (int i = 0; i < ns1.length; i++) { ns1[i] = ns[i] * 1.0; } calc(ns1, ""); } public static void main(String[] args) { Calc24New calc24 = new Calc24New(); calc24.run(new int[]{3, 4, 7, 9}); System.out.println("*************************"); calc24.run(new int[]{3, 3, 7, 7}); System.out.println("*************************"); calc24.run(new int[]{4, 4, 7, 7, 7}); } } |
| 返回顶楼 | |
|
发表时间：2009-01-15
抛出异常的爱 写道
public static Integer getSum(LinkedList<Integer> link){
int sum = 0;
int first = link.remove([color=red]new Random()[/color].nextInt(link.size()));
int next = link.remove([color=red]new Random()[/color].nextInt(link.size()));
int symbol = [color=red]new Random()[/color].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;
}
果然算命的善用随机数。该算法唯一的不足就是当输入无解时程序会进入死循环（或者说程序通过这种进入死循环的方式来告诉我们“此题无解”） |
| 返回顶楼 | |
|
发表时间：2009-01-15
我程序还需要再改进。根据题目的要求：任取1－9之间的4个数字，用＋－＊／（）连结成算式，使得式子的计算结果为24
那样，结果应该是这个样子的：（8/4-2+6）*3=24 |
| 返回顶楼 | |
|
发表时间：2009-01-15
不好意思！少打了几个字：
我认为楼主的程序还需要再改进。根据题目的要求：任取1－9之间的4个数字，用＋－＊／（）连结成算式，使得式子的计算结果为24 那样，结果应该是这个样子的：（8/4-2+6）*3=24 |
| 返回顶楼 | |
|
发表时间：2009-01-15
最后修改：2009-01-15
sam.ds.chen 写道 抛出异常的爱 写道 果然算命的善用随机数。该算法唯一的不足就是当输入无解时程序会进入死循环（或者说程序通过这种进入死循环的方式来告诉我们“此题无解”） 下回给你免费算..... 有人说要用20行来写这个.... 所以就不考虑遍历所有的内容了. 主要为好读. 如果遍历所有内容的话.没大可能写的太少了 ----------------------------------------------------- 你 a b c d 原数据 Map map 第一次在adcd中取两个数放到e中(ab)(ba)(ac)(ca)(ad)(da)(bc)(cb)(bd)(db)(cd)(dc)a b c d 第二次 ........ 第三次........ 这样就得出来所有的可能组合了 之后循环4*4次就ok了. |
| 返回顶楼 | |
|
发表时间：2009-01-15
我的方法差不多可以压缩成20行，因为前面一大半代码都是判断4个1--9的数字。后面的js部分查不多是20行
|
| 返回顶楼 | |
|
发表时间：2009-01-16
基本思想是差不多，不过实现有些不同。
基本穷举想法是24点共有3次运算（加减乘除），假如原始数字为A，B，C，D，可得到的3次运算主要是两种， （（H，I）（J，K））或者，（（（H，I），J），K），其中，A，B，C，D和H，I，J，K的映射有24种（4*3*2*1），运算共有6种（加减乘除、反减、反除，这里其实可以做优化，因为映射变了以后，减和反减其实多做了，不过是否可以完全去掉没有做过试验），则穷举的主要步骤是： 按照映射取得数据 第一种，两重循环（6*6） 取H，I的值，6种运算，得到E， 取J，K的值，6种运算，得到F 计算，E，F的6种运算。 第二种，类似的想法。 不过以上代码很长，考虑到这里主要是穷举计算式子的代码，所以，可以考虑把穷举出来的计算式子按照波兰式或者逆波兰式或者你自己喜欢的方式写到一个文件中去，程序在运行的时候读取就可以了。这是一个偏方，因为这个保存了半次结果，xy自己也只做到这一步（20行以内没有太大的问题）。 |
| 返回顶楼 | |
|
发表时间：2009-01-16
这儿的高手很多啊，本来想发个实现表达式计算的例子，不敢现丑啦。
|
| 返回顶楼 | |
|
发表时间：2009-01-16
gbb21 写道 sdh5724 写道 谁能把代码控制在20行之内， 又有一定可读性。
比赛开始， 楼下继续。 把我python代码里面的记忆处理/或者表达式输出 去掉就20行以内了～ 看来你python很不错哦！ |
| 返回顶楼 | |
