搜索算法I：二十四点
[TABS_R id=2260]
使用四个正整数，添加一些运算符以将四个数字组成运算结果等于24的表达式。最经典的二十四点是从1到13的正整数以及+,-,*,/,括号。而不同的规则下可能包括：是否支持括号、是否按四则运算优先级、是否允许将数字调整顺序、是否允许分数（对于5*(5-1/5)如果支持分数那么这将能够得到5*(24/5) = 24，不允许分数的情况下1/5视为整除得到结果为0）、是否按四则运算优先级等变体。不过，不论如何变形，二十四点都是对四个数字和三个运算符进行搜索。本文将以最基本的：允许括号、允许调整数字顺序、允许使用分数的规则进行探讨。
首先，我们先定义我们的运算：加、减、乘、除、减于、除于。对于“减于”运算，a减于b即b减a，除于类似，a除于b即b除a，加入这样两个运算之后，我们就可以将所有二十四点的算式抽象成以下两种模式，假定运算数为a,b,c,d,运算符用#表示：
((a # b) # c) # d(a # b) # (c # d)
那么，我们所需要的就是将4个数字与6个运算符分别填入a,b,c,d与三个#。本问题允许调整数字顺序，所以先使用递归把a,b,c,d的全排列分别放置到四个数字上，然后对6个符号逐个枚举。虽然存在a+b与b+a这样的等价情况，但我们估计一下，将四个数字的全排列以及三个符号全部枚举出来的运算量仅有\( 2 \times 4! \times 6^3 = 10368 \)，所以即使不需要对等价情况再做处理运算量也完全可以接受。
将我们的数字定义为Number类型，根据题目是否支持小数的规则我们将Number预设为int或double，定义Number类型的数组numberBucket[4]，分别用来做运算，运算符号用char类型进行抽象，用0,1,2,3,4,5分别表示我们定义的6种运算。先生成四个数字的全排列，并列出运算符号的所有情况。我们编写makeNumber()来生成全排列，当生成排列的数字已经是4个，再列举运算符，当运算符也列举出3个，此时就可以进行运算了，我们用expressionMode1()和expressionMode2()分别表示上边列的两种形式的运算，将列出来的数字与运算符逐一代入算式判断运算结果是否为24即可。由于规则支持分数，所以判断数字相等就不能使用==，而是使用浮点误差的fabs()<epsilon。
// -std=c++11 or higher
using Number = double;
int num[4]; // input
Number numberBucket[4];
int used[4];
int symbols[4];
Number expressionMode1();
Number expressionMode2();
int isZero(Number x)
{
const double epsilon = 1e-6;
return fabs(x)<epsilon;
}
int makeOperator(int depth)
{
if (depth==3){
return (isZero(expressionMode1()-24) || isZero(expressionMode2()-24));
}
for (int i=0;i<6;i++){
symbols[depth] = i;
if ( makeOperator(depth+1) ){
return 1;
}
}
return 0;
}
int makeNumber(int depth)
{
if (depth==4){
return makeOperator(0);
}
for (int i=0;i<4;i++){
if (used[i]==0){
numberBucket[depth] = num[i];
used[i]=1;
if (makeNumber(depth+1)){
return 1;
}
used[i]=0;
}
}
return 0;
}有了基本的搜索结构，剩下的便是编写expressionMode()以及主函数。在编写运算函数expressionMode的时候，要注意可能出现的除0问题，可以预定义一个较大的数字作为无限大的标记INF，一旦除0则返回值为INF。
#define INF 0x7FFFFF
Number calculate(Number a,Number b,int opIdx)
{
if(opIdx==0){
return a+b;
} else if (opIdx==1){
return a-b;
} else if (opIdx==2){
return a*b;
} else if (opIdx==3){
return isZero(b)? INF: a/b;
} else if (opIdx==4){
return b-a;
} else{
return isZero(a)? INF: b/a;
}
}
Number expressionMode1(){
Number s= calculate(numberBucket[0],numberBucket[1],symbols[0]);
s = calculate(s,numberBucket[2],symbols[1]);
return calculate(s,numberBucket[3],symbols[2]);
}
Number expressionMode2(){
Number a1 = calculate(numberBucket[0],numberBucket[1],symbols[0]);
Number a2 = calculate(numberBucket[2],numberBucket[3],symbols[2]);
return calculate(a1,a2,symbols[1]);
}
int main(void)
{
while(1){
for (int i=0;i<4;i++){
scanf("%d",num+i);
}
if(num[0]==0 && num[1]==0 &&
num[2]==0 && num[3]==0 ){
break;
}
memset(used,0,sizeof(used));
printf("%s\n",makeNumber(0)?"YES":"NO");
}
return 0;
}