搜索算法I:二十四点

搜索算法I:二十四点

使用四个正整数,添加一些运算符以将四个数字组成运算结果等于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预设为intdouble,定义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;
}

本题VJudge链接:https://vjudge.net/problem/OpenJ_Bailian-2787

发表评论

电子邮件地址不会被公开。 必填项已用*标注