1、概述
给定4个整数，当中每一个数字仅仅能使用一次；随意使用 + - * / ( ) ，构造出一个表达式，使得终于结果为24，这就是常见的算24点的游戏。这方面的程序非常多，一般都是穷举求解。本文介绍一种典型的算24点的程序算法，并给出两个详细的算24点的程序：一个是面向过程的C实现，一个是面向对象的java实现。
2、基本原理
基本原理是穷举4个整数全部可能的表达式，然后对表达式求值。
表达式的定义： 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 则恢复数组，以确保当前递归调用获得下一个正确的排列。
括号 () 的作用仅仅是改变运算符的优先级，也就是运算符的计算顺序。所以在以上算法中，无需考虑括号。括号仅仅是在输出时需加以考虑。
3、面向过程的C实现
这是 csdn 算法论坛前版主海星的代码，程序很简练、精致：
#include #include #include using namespace std; const double PRECISION = 1E-6; const int COUNT_OF_NUMBER = 4; const int NUMBER_TO_BE_CAL = 24; double number[COUNT_OF_NUMBER]; string expression[COUNT_OF_NUMBER]; bool Search(int n) { if (n == 1) { if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) { cout << expression[0] << endl; return true; } else { return false; } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double a, b; string expa, expb; a = number[i]; b = number[j]; number[j] = number[n - 1]; expa = expression[i]; expb = expression[j]; expression[j] = expression[n - 1]; expression[i] = '(' + expa + '+' + expb + ')'; number[i] = a + b; if ( Search(n - 1) ) return true; expression[i] = '(' + expa + '-' + expb + ')'; number[i] = a - b; if ( Search(n - 1) ) return true; expression[i] = '(' + expb + '-' + expa + ')'; number[i] = b - a; if ( Search(n - 1) ) return true; expression[i] = '(' + expa + '*' + expb + ')'; number[i] = a * b; if ( Search(n - 1) ) return true; if (b != 0) { expression[i] = '(' + expa + '/' + expb + ')'; number[i] = a / b; if ( Search(n - 1) ) return true; } if (a != 0) { expression[i] = '(' + expb + '/' + expa + ')'; number[i] = b / a; if ( Search(n - 1) ) return true; } number[i] = a; number[j] = b; expression[i] = expa; expression[j] = expb; } } return false; } void main() { for (int i = 0; i < COUNT_OF_NUMBER; i++) { char buffer[20]; int x; cin >> x; number[i] = x; itoa(x, buffer, 10); expression[i] = buffer; } if ( Search(COUNT_OF_NUMBER) ) { cout << "Success." << endl; } else { cout << "Fail." << endl; } }
使用任一个 c++ 编译器编译就可以。
这个程序的算法与 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) 输出时，为每一个表达式都加入了括号。
转载于:https://www.cnblogs.com/mengfanrong/p/4296642.html
