24点的三种算法思路及代码(1)

昨天晚上在寝室里觉得无聊，于是就玩这个24点游戏，上网搜了半天，就一个代码是正确的，而且只能给出一个解，于是只好自己写咯，参考了网上现有的一些算法^_^

先简单介绍一下24点游戏：
给出4个1-9之间的自然数，其中每个数字只能使用一次；任意使用 + – * / ( ) ，构造出一个表达式，使得最终结果为24，这就是常见的算24点的游戏。比如两道比较经典的题目：1，5，5，5和3，3，8，8，先自己试试，答案贴在文章最后^_^

此文所贴代码均为面向过程的C(++)代码，在VC6下编译通过。

解决这个问题一般使用穷举法，即穷举4个整数所有可能的表达式，然后对表达式求值。下面的两种思路（三种算法）均是基于穷举法，各有优劣。

第一种思路：
把多元运算转化为两元运算，先从四个数中取出两个数进行运算，然后把运算结果和第三个数进行运算，再把结果与第四个数进行运算。在求表达式的过程中，最难处理的就是对括号的处理，而这种思路很好的避免了对括号的处理。基于这种思路有两种算法：

第一种算法：
(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是一个递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。

这个是程序代码，源代码为csdn 算法论坛前版主海星所作，我修改了部分变量。此程序只能求出第一个解，无法求出全解。
[quote]
#include
#include
#include

using namespace std;

const double PRECISION = 1E-6;
const int COUNT = 4;
const int RESULT = 24;

double number[COUNT]; //这里一定要用double,看看第一题的答案就知道为什么了
string expression[COUNT]; //保存表达式

bool Test(int n){
//递归结束
if(n==1){
if(fabs(number[0]-RESULT) cout< return true;
}
else
return false;
}

//递归过程
for(int i=0;i for(int j=i+1;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(Test(n-1))
return true;

//减号有两种情况,a-b与b-a
expression[i]='(‘+expa+’-‘+expb+’)’;
number[i]=a-b;
if(Test(n-1))
return true;

expression[i]='(‘+expb+’-‘+expa+’)’;
number[i]=b-a;
if(Test(n-1))
return true;

expression[i]='(‘+expa+’*’+expb+’)’;
number[i]=a*b;
if(Test(n-1))
return true;

//除法也有两种情况,a/b与b/a
if(b!=0){
expression[i]='(‘+expa+’/’+expb+’)’;
number[i]=a/b;
if(Test(n-1))
return true;
}

if(a!=0){
expression[i]='(‘+expb+’/’+expa+’)’;
number[i]=b/a;
if(Test(n-1))
return true;
}

//恢复数组
number[i]=a;
number[j]=b;
expression[i]=expa;
expression[j]=expb;
}
}
return false;
}

void main(void){
for(int i=0;i char buffer[20];
int x;
cin >> x;
number[i]=x;
itoa(x,buffer,10);
expression[i]=buffer;
}

if(Test(COUNT))
co t ” cc s” < dl
se ut < ai < en ; /quote]

系列文章：
24点的三种算法思路及代码(1)
24点的三种算法思路及代码(2)
24点的三种算法思路及代码(3)