- 浏览: 3013658 次
- 性别:
- 来自: 海外
文章分类
- 全部博客 (430)
- Programming Languages (23)
- Compiler (20)
- Virtual Machine (57)
- Garbage Collection (4)
- HotSpot VM (26)
- Mono (2)
- SSCLI Rotor (1)
- Harmony (0)
- DLR (19)
- Ruby (28)
- C# (38)
- F# (3)
- Haskell (0)
- Scheme (1)
- Regular Expression (5)
- Python (4)
- ECMAScript (2)
- JavaScript (18)
- ActionScript (7)
- Squirrel (2)
- C (6)
- C++ (10)
- D (2)
- .NET (13)
- Java (86)
- Scala (1)
- Groovy (3)
- Optimization (6)
- Data Structure and Algorithm (3)
- Books (4)
- WPF (1)
- Game Engines (7)
- 吉里吉里 (12)
- UML (1)
- Reverse Engineering (11)
- NSIS (4)
- Utilities (3)
- Design Patterns (1)
- Visual Studio (9)
- Windows 7 (3)
- x86 Assembler (1)
- Android (2)
- School Assignment / Test (6)
- Anti-virus (1)
- REST (1)
- Profiling (1)
- misc (39)
- NetOA (12)
- rant (6)
- anime (5)
- Links (12)
- CLR (7)
- GC (1)
- OpenJDK (2)
- JVM (4)
- KVM (0)
- Rhino (1)
- LINQ (2)
- JScript (0)
- Nashorn (0)
- Dalvik (1)
- DTrace (0)
- LLVM (0)
- MSIL (0)
最新评论
-
mldxs:
虽然很多还是看不懂,写的很好!
虚拟机随谈(一):解释器,树遍历解释器,基于栈与基于寄存器,大杂烩 -
HanyuKing:
Java的多维数组 -
funnyone:
Java 8的default method与method resolution -
ljs_nogard:
Xamarin workbook - .Net Core 中不 ...
LINQ的恶搞…… -
txm119161336:
allocatestlye1 顺序为 // Fields o ...
最近做的两次Java/JVM分享的概要
呵呵,最近面试某公司的同学真多。早就听说他们上机考试要考24点的实现了,不过没想到那么多个同学都遇到了这一题。这不,对面宿舍有同学又要去面那公司了,找我问这24点怎么写。考虑到也不能写太难得方法不然同学记起来麻烦,干脆就写了个超直观超naive的穷举实现。哈哈。
首先是24点问题的定义。我采纳的定义是用户可以输入4个数字,每个数字可接受的范围是1-13的整数;对这4个数字做4则混合运算得到的结果是24时,则这个表达式被认为符合题目条件。
然后考虑一下如何穷举。如果把四个数字固定顺序,则有时候需要插入括号来改变运算优先级来得到符合条件的表达式,但这样挺麻烦的。这里取个巧,不是插入括号,而是改变4个输入参数的前后顺序来改变运算的先后顺序。
可是加减与乘除的优先级不同,怎么办呢?再取个巧,使用后缀表达式来处理一切与运算优先级相关的问题。用了后缀表达式就不必为括号而头疼了。
所以我们得到的表达式的形式会是类似:
或者:
或者:
例如说,1 2 + 3 + 4 ×就是(1 + 2 + 3) * 4。
于是我们对4个输入的数字的顺序做一个全排列,为每种排列情况再对其中3个间隔上的运算符做穷举。
然后来看看代码。为了让同学有足够东西可以说,我用了Java 5里的3种新特性:泛型、enum和for-each。
不过当前的实现下,会漏掉一些情况。下面的代码只实现了上面列举的3种可能的第一种。
hmm,那倒也不太算个问题,因为反正是他们面试嘛诶……呵呵,明天再把不会漏掉运算情况的穷举的代码发出来。
Calc24.java:
TupleOfFour.java:
Operator.java:
首先是24点问题的定义。我采纳的定义是用户可以输入4个数字,每个数字可接受的范围是1-13的整数;对这4个数字做4则混合运算得到的结果是24时,则这个表达式被认为符合题目条件。
然后考虑一下如何穷举。如果把四个数字固定顺序,则有时候需要插入括号来改变运算优先级来得到符合条件的表达式,但这样挺麻烦的。这里取个巧,不是插入括号,而是改变4个输入参数的前后顺序来改变运算的先后顺序。
可是加减与乘除的优先级不同,怎么办呢?再取个巧,使用后缀表达式来处理一切与运算优先级相关的问题。用了后缀表达式就不必为括号而头疼了。
所以我们得到的表达式的形式会是类似:
num1 num2 op1 num3 op2 num4 op3
或者:
num1 num2 op1 num3 num4 op2 op3
或者:
num1 num2 num3 op1 num4 op2 op3
例如说,1 2 + 3 + 4 ×就是(1 + 2 + 3) * 4。
于是我们对4个输入的数字的顺序做一个全排列,为每种排列情况再对其中3个间隔上的运算符做穷举。
然后来看看代码。为了让同学有足够东西可以说,我用了Java 5里的3种新特性:泛型、enum和for-each。
不过当前的实现下,会漏掉一些情况。下面的代码只实现了上面列举的3种可能的第一种。
hmm,那倒也不太算个问题,因为反正是他们面试嘛诶……呵呵,明天再把不会漏掉运算情况的穷举的代码发出来。
Calc24.java:
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; public class Calc24 { public static void main(String[] args) throws Exception { int[] input = promptInput(); int length = input.length; ArrayList<TupleOfFour> permutation = new ArrayList<TupleOfFour>(); // get permutation of the four operands for (int i = 0; i < length; ++i) { for (int j = 0; j < length; ++j) { if (i == j) continue; for (int k = 0; k < length; ++k) { if (i == k || j == k) continue; int l = 6 - i - j - k; permutation.add(new TupleOfFour( input[i], input[j], input[k], input[l])); } } } // enumerate the operators, and evaluate the postfix expression for (TupleOfFour tuple : permutation) { int first = tuple.getFirst(); int second = tuple.getSecond(); int third = tuple.getThird(); int fourth = tuple.getFourth(); for (Operator op1 : Operator.values()) { if ((op1 == Operator.Divide) && !(Operator.canDivide(first, second))) continue; int result1 = op1.calculate(first, second); for (Operator op2 : Operator.values()) { if ((op2 == Operator.Divide) && !(Operator.canDivide(result1, third))) continue; int result2 = op2.calculate(result1, third); for (Operator op3 : Operator.values()) { if ((op3 == Operator.Divide) && !(Operator.canDivide(result2, fourth))) continue; int result3 = op3.calculate(result2, fourth); if (result3 == 24) { // build a string representation // of the postfix expression StringBuilder builder = new StringBuilder(); builder.append(first); builder.append(" "); builder.append(second); builder.append(" "); builder.append(op1.getOpChar()); builder.append(" "); builder.append(third); builder.append(" "); builder.append(op2.getOpChar()); builder.append(" "); builder.append(fourth); builder.append(" "); builder.append(op3.getOpChar()); System.out.println(builder.toString()); } // end if } // end of for-each op3 } // end of for-each op2 } // end of for-each op1 } // end of for-each permutation } // end of main() private static int[] promptInput() throws Exception { int[] input = new int[4]; BufferedReader reader = new BufferedReader( new InputStreamReader(System.in)); String line = null; for (int i = 0; i < 4; ++i) { System.out.print("Enter a number (1 to 13): "); line = reader.readLine(); try { input[i] = Integer.parseInt(line); if (input[i] < 1 || input[i] > 13) throw new IllegalArgumentException(); } catch (IllegalArgumentException e) { System.out.println("The input is invalid. Please re-enter."); --i; } } return input; } }
TupleOfFour.java:
public class TupleOfFour { private int first; private int second; private int third; private int fourth; public TupleOfFour(int first, int second, int third, int fourth) { this.first = first; this.second = second; this.third = third; this.fourth = fourth; } public int getFirst() { return first; } public int getSecond() { return second; } public int getThird() { return third; } public int getFourth() { return fourth; } }
Operator.java:
public enum Operator { Add('+') { int calculate(int first, int second) { return first + second; } }, Minus('-') { int calculate(int first, int second) { return first - second; } }, Multiply('*') { int calculate(int first, int second) { return first * second; } }, Divide('/') { int calculate(int first, int second) { return first / second; } }; private char opChar; Operator(char c) { this.opChar = c; } abstract int calculate(int first, int second); public char getOpChar() { return this.opChar; } public static boolean canDivide(int first, int second) { return (first % second) == 0; } }
发表评论
-
The Prehistory of Java, HotSpot and Train
2014-06-02 08:18 0http://cs.gmu.edu/cne/itcore/vi ... -
MSJVM and Sun 1.0.x/1.1.x
2014-05-20 18:50 0当年的survey paper: http://www.sym ... -
Sun JDK1.4.2_28有TieredCompilation
2014-05-12 08:48 0原来以前Sun的JDK 1.4.2 update 28就已经有 ... -
IBM JVM notes (2014 ver)
2014-05-11 07:16 0Sovereign JIT http://publib.bou ... -
class data sharing by Apple
2014-03-28 05:17 0class data sharing is implement ... -
Java 8与静态工具类
2014-03-19 08:43 16125以前要在Java里实现所谓“静态工具类”(static uti ... -
Java 8的default method与method resolution
2014-03-19 02:23 10324先看看下面这个代码例子, interface IFoo { ... -
HotSpot Server VM与Server Class Machine
2014-02-18 13:21 0HotSpot VM历来有Client VM与Server V ... -
Java 8的lambda表达式在OpenJDK8中的实现
2014-02-04 12:08 0三月份JDK8就要发布首发了,现在JDK8 release c ... -
GC stack map与deopt stack map的异同
2014-01-08 09:56 0两者之间不并存在包含关系。它们有交集,但也各自有特别的地方。 ... -
HotSpot Server Compiler与data-flow analysis
2014-01-07 17:41 0http://en.wikipedia.org/wiki/Da ... -
字符串的一般封装方式的内存布局 (1): 元数据与字符串内容,整体还是分离?
2013-11-07 17:44 22244(Disclaimer:未经许可请 ... -
字符串的一般封装方式的内存布局
2013-11-01 12:55 0(Disclaimer:未经许可请 ... -
关于string,内存布局,C++ std::string,CoW
2013-10-30 20:45 0(Disclaimer:未经许可请 ... -
对C语义的for循环的基本代码生成模式
2013-10-19 23:12 21729之前有同学在做龙书(第二版)题目,做到8.4的练习,跟我对答案 ... -
Java的instanceof是如何实现的
2013-09-22 16:57 0Java语言规范,Java SE 7版 http://docs ... -
oop、klass、handle的关系
2013-07-30 17:34 0oopDesc及其子类的实例 oop : oopDesc* ... -
Nashorn各种笔记
2013-07-15 17:03 0http://bits.netbeans.org/netbea ... -
《深入理解Java虚拟机(第二版)》书评
2013-07-08 19:19 0值得推荐的中文Java虚拟机入门书 感谢作者赠与的样书,以下 ... -
豆列:从表到里学习JVM实现
2013-06-13 14:13 48099刚写了个学习JVM用的豆列跟大家分享。 豆列地址:http: ...
相关推荐
还是不要资源分的下载,本次是使用递归穷举的方式解答24点问题,具体参看里面的txt说明,诸位如果有效率更高的算法,麻烦在论坛里告诉我一声。
穷举穷举的几个C/C++例子,欢迎下载…………………………………………………………………………
15.6 应用…………………………………………………………………………………………………………227 〖案例l〗果园篱笆………………………………………………………………227 〖案例2〗巨人和鬼………………...
C语言24点游戏穷举法
穷举算法经典案例及其C语言实现.穷举算法经典案例及其C语言实现.
设计一个程序,输入4个数字(1-10),则列出所有可能计算结果为24的方案。
自己用粗暴的穷举法实现的八皇后,代码浅显易懂,对初学者应该有帮助。
穷举破解24点游戏
用穷举法求解n皇后问题
MATLAB优化算法案例分析与应用(进阶篇)1-10章程序下载
matlab解决tsp问题,穷举法,不错的
这个穷举法计算三八二十四,有C#和C++两者计算方法, NET2008可以直接打开使用,也可以用文本文档直接读看。
VC 穷举子目录以及子目录下文件的东东,非原创.
给定4个整数,其中每个数字只能使用一次;任意使用 + - * / ( ) ,构造出一个表达式,使得最终结果为24,这就是常见的算24点的游戏。这方面的程序很多,一般都是穷举求解。本程序通过递归算法实现实现24点计算,
RAR穷举解密.rar
穷举法代码解析带注释(学习穷举法代码好资料)
0-1整数规划有很广泛的应用背景,比如指派问题,背包问题等等,实际上TSP问题也是一个0-1问题,当然这些问题都是NP问题,对于规模较大的问题用穷举法是没有办法在可接受的时间内求得最优解的,本程序只不过是一个...
WebCrack4 无线路由登录密码穷举工具.
了对其穷举算法的编程,快速验证了 24 位以内的巴克码序列只有目前已搜索到的 10 组。该方法是以线性代数的基本理论为 基础,借助 LabVIEW 平台强大的矩阵运算功能来实现的。鉴于自相关函数的计算方法与穷举算法实现...
用堆栈做的24点程序,里面用到了后缀表达式求值。