算24点措施：面向进程与面向工具的C++
副标题#e#
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 则规复数组，以确保当前递归挪用得到下一个正确的分列。
括号 () 的浸染只是改变运算符的优先级，也就是运算符的计较顺序。所以在以上算法中，无需思量括号。括号只是在输出时需加以思量。
#p#副标题#e#
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++ 编译器编译即可。
#p#分页标题#e#
这个措施的算法与 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个元素的分列 |
完整的源代码请看 http://www.ch2000.com.cn/~ganxc/expression.zip 。这是一个简朴的24点计较措施和表达式理会求值措施，利用要领请参阅个中的 ReadMe.txt
从中可以看到许多面向工具设计的长处：
#p#分页标题#e#
(1) 在输出表达式时，只要改写 Number.toString() 和 Expression.toString() 即可。为了输出须要的括号，去掉不须要的括号，只要改写 Expression.toString() 即可。
(2) Permutor 分列生成器使得流程布局大大简化。
(3) 封装性好，生成3个数的分列，理论上只需窜改 Permutor 的内部实现代码
(4) 重用性好，Number, Expression 可以在其它处所，如表达式理会措施中重用。
虽然这只是一个示例性的代码，内部尚有许多可以封装、简化的处所。在类的框架上作修改其实是很利便的工作。
