C++算24点代码穷举实现

问题：给定4个整数，其中每个数字只能使用一次；任意使用 + - * / ( ) ，构造出一个表达式，使得最终结果为24，这就是常见的算24点的游戏。这方面的程序很多，一般都是穷举求解。 表达式的定义： expression = (expression|number) operator (expression|number) 因为能使用的4种运算符 + - * / 都是2元运算符，所以本文中只考虑2元运算符。2元运算符接收两个参数，输出计算结果，输出的结果参与后续的计算。 由上所述，构造所有可能的表达式的算法如下： (1) 将4个整数放入数组中 (2) 在数组中取两个数字的排列，共有 P(4,2) 种排列。对每一个排列， (2.1) 对 + - * / 每一个运算符， (2.1.1) 根据此排列的两个数字和运算符，计算结果 (2.1.2) 改表数组：将此排列的两个数字从数组中去除掉，将 2.1.1 计算的结果放入数组中 (2.1.3) 对新的数组，重复步骤 2 (2.1.4) 恢复数组：将此排列的两个数字加入数组中，将 2.1.1 计算的结果从数组中去除掉 可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。 在程序中，一定要注意递归的现场保护和恢复，也就是递归调用之前与之后，现场状态应该保持一致。在上述算法中，递归现场就是指数组，2.1.2 改变数组以进行下一层递归调用，2.1.3 则恢复数组，以确保当前递归调用获得下一个正确的排列。 这个程序的算法与 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 返回并输出结果，然后程序结束，也就是说，当有多个解法时，根据输入顺序不同，解法不同。 例：8 3 1 4 输出（8-3+1）*4 而1 3 4 8 输出（1+3）*4+8。 (5) 以 double 来进行求解，定义精度，用以判断是否为 24 。考虑 (5-1/5)*5 这个表达式就知道这么做的原因了。 (6) 输出时，为每个表达式都添加了括号。