C语言实现经典24点算法
本文实例为大家分享了C语言经典24点算法的具体实现代码，供大家参考，具体内容如下
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
usingnamespacestd;
constdoublePRECISION=1E-6;
constintCOUNT_OF_NUMBER=4;
constintNUMBER_TO_BE_CAL=24;
doublenumber[COUNT_OF_NUMBER];
stringexpression[COUNT_OF_NUMBER];
boolSearch(intn)
{
if(n==1){
if(fabs(number[0]-NUMBER_TO_BE_CAL)>x;
number[i]=x;
itoa(x,buffer,10);
expression[i]=buffer;
}
if(Search(COUNT_OF_NUMBER)){
cout<<"Success."<
使用任一个c++编译器编译即可。
这个程序的算法与2、基本原理所述的算法基本相同。其中boolSearch(intn)就是递归函数，doublenumber[]就是数组。程序中比较重要的地方解释如下：
(1)stringexpression[]存放每一步产生的表达式，最后的输出中要用到。expression[]与number[]类似，也是递归调用的现场，必须在下一层递归调用前改变、在下一层递归调用后恢复。
(2)number[]数组长度只有4。在search()中，每次取出两个数后，使用局部变量a,b保存这两个数，同时数组中加入运算结果，并调整数组使得有效的数字都排列在数组前面。在下一层递归调用后，利用局部变量a,b恢复整个数组。对expression[]的处理与number[]类似。
(3)因为+*满足交换率而-/不满足，所以程序中，从数组生成两个数的排列，
for(inti=0;i
for(intj=i+1;j
其内层循环j是从i+1->n，而非从0->n，因为对于交换率来说，两个数字的顺序是无所谓的。当然，循环内部对-/做了特殊处理，计算了a-bb-aa/bb/a四种情况。
(4)此程序只求出第一个解。当求出第一个解时，通过层层returntrue返回并输出结果，然后程序结束。
(5)以double来进行求解，定义精度，用以判断是否为24。考虑(5-1/5)*5这个表达式就知道这么做的原因了。
(6)输出时，为每个表达式都添加了括号。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。