算24点程序：面向过程与面向对象的C++ （3）

     来源：51vb    作者：ben

这个程序的算法与 2、基本原理 所述的算法基本相同。其中 bool Search(int n) 就是递归函数，double number[] 就是数组。程序中比较重要的地方解释如下：

　　(1) string expression[] 存放每一步产生的表达式，最后的输出中要用到。expression[] 与 number[] 类似，也是递归调用的现场，必须在下一层递归调用前改变、在下一层递归调用后恢复。

　　(2) number[] 数组长度只有4。在 search() 中，每次取出两个数后，使用局部变量 a, b 保存这两个数，同时数组中加入运算结果，并调整数组使得有效的数字都排列在数组前面。在下一层递归调用后，利用局部变量 a, b 恢复整个数组。对 expression[] 的处理与 number[] 类似。

　　(3) 因为 + * 满足交换率而 - / 不满足，所以程序中，从数组生成两个数的排列，
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
　　其内层循环 j 是从 i+1 -> n，而非从 0->n ，因为对于交换率来说，两个数字的顺序是无所谓的。当然，循环内部对 - / 做了特殊处理，计算了 a-b b-a a/b b/a 四种情况。

　　(4) 此程序只求出第一个解。当求出第一个解时，通过层层 return true 返回并输出结果，然后程序结束。

　　(5) 以 double 来进行求解，定义精度，用以判断是否为 24 。考虑 (5-1/5)*5 这个表达式就知道这么做的原因了。

　　(6) 输出时，为每个表达式都添加了括号。

　　4、面向对象的java实现

　　算法依然同 2、基本原理 。使用对象的好处是程序的结构更清晰，功能的扩充更方便。当然效率会比结构化程序低。对象设计如下：

类	类含有的变量	类含有的方法	说明
Number	double value	String toString()	这样可以清晰地表达出 expression 的递归定义
Expression extends Number	Number left Number right char operator	String toString()
Calculator	Number[] numbers Expression[] expressions	add() clear() //操作 numbers calculate() Permutor permutor()	java 程序的主类，实现算法
Permutor	int i,j	boolean next()	排列生成器，类似 iterator，从一个指定的数组中生成2个元素的排列

　　完整的源代码请看 ~ganxc/expression.zip 。这是一个简单的24点计算程序和表达式解析求值程序，使用方法请参阅其中的 ReadMe.txt

　　从中可以看到很多面向对象设计的好处：

　　(1) 在输出表达式时，只要改写 Number.toString() 和 Expression.toString() 即可。为了输出必要的括号，去掉不必要的括号，只要改写 Expression.toString() 即可。

　　(2) Permutor 排列生成器使得流程结构大大简化。

　　(3) 封装性好，生成3个数的排列，理论上只需改动 Permutor 的内部实现代码

　　(4) 重用性好，Number, Expression 可以在其它地方，如表达式解析程序中重用。

　　当然这只是一个示例性的代码，内部还有很多可以封装、简化的地方。在类的框架上作修改其实是很方便的事情。