U - 速算24点

简单搜索&&进阶搜索 - Virtual Judge (vjudge.net)

【题目描述】

随机给你四张牌，包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用'+','-','*','/'运算符以及括号改变运算顺序，使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌，判断是否有解。我们另外规定，整个计算过程中都不能出现小数。

【输入】

每组输入数据占一行，给定四张牌。

【输出】

每一组输入数据对应一行输出。如果有解则输出"Yes"，无解则输出"No"。

解题思路：

我用的是深搜，这个题的深搜次数是三次，因为四个数，进行三次加减乘除的运算。

首先用一个数组存储数据，但是在存储之前要把输入的数转化为数字，因为转换的次数较多，所以可以用一个函数转化，在输入这里，接收字符 %c 和 getchar (); 吸收空格和换行一直过不了，最后用的 %s 接收字符串，所以一组数据要接收四次。

接下来的深搜，首先确定结束的条件是：深搜三次如果满足 a [ 3 ]==24 或 a [ 3 ]== - 24 就结束。

在此之前用两层循环遍历这四个数的运算，每两个数都可以进行四种运算，其中对于减法和除法数字的先后顺序对运算结果有影响，所以对于两数减法和除法的搜索分别都要进行两次，然后题目另外一个条件是：不能出现小数，所以每次除法运算时，要先判断除数是否为 0，而且两数取余后的结果是否为 0,（也就是 c%d==0）.

循环大致是这样：(每次深搜传入的数字是 x）

for(int i=x;i<4;i++){

        for(int j=i+1;j<4;j++){

                遍历四种运算；

        }

}

然后还要思考的一点是：对于当前运算后的值，怎么样判断该数用过？

其实是不用判断的。

首先说说遍历的过程：当在一个循环内，也就是变量 j 的那层循环，每次先用两个变量记录要进行运算的数字（因为运算方法有多次，且在一个循环内，若是改变数组里面的值，在该条件不满足时，还需要将刚刚的运算进行逆运算，再进行后面的运算）。

然后将 a [x] 的值记录在 a [i] 中，因为 a[x] 是之前运算计算出的结果，把它当成一个整体，再进行后面的计算，然后每次运算的结果存放在 a [j] 中，运算后进入 dfs（x+1）。

当 j 循环结束时，也就是 j==4 了，就要把 先前存储 a [i] 和 a [j] 值的变量重新赋值给 a [i] 和 a [j].

对于上面那个问题，应该可以解决了，因为每两个数进行计算，其结果是返回到较后的那个数字（j）为下标的数组元素了，下次进行计算时，直接两数的计算结果当成整体在运算即可，至于较前的那个数（i），已经不会遍历到了。

代码如下：

#include<stdio.h>
#include<string.h>
char ch[5];
int a[10];
int fun(char x)
{
	if (x == 'A')
		return 1;
	if (x == 'J')
		return 11;
	if (x == 'Q')
		return 12;
	if (x == 'K')
		return 13;
	if (x == '1')
		return 10;
	else
		return (x - '0');
}
int dfs(int x)
{
	int i, j;
	if (x == 3)
	{
		if (a[x] == 24 || a[x] == -24)
		{	
			return 1;
		}
		else
			return 0;
	}
	for (i = x; i < 4; i++)
	{
		for (j = i+1; j < 4; j++)
		{
			int c = a[i];
			int d = a[j];
			a[i] = a[x];
			a[j] = c + d;
			if(dfs(x+1))
				return 1;
			a[j] = c - d;
			if(dfs(x+1))
				return 1;
			a[j] = d - c;
			if (dfs(x + 1))
				return 1;
			a[j] = c * d;
			if (dfs(x + 1))
				return 1;
			if (d != 0 && c % d == 0)
			{
				a[j] = c / d;
				if (dfs(x + 1))
					return 1;
			}
			if (c != 0 && d%c == 0)
			{
				a[j] = d / c;
				if (dfs(x + 1))
					return 1;
			}
			a[i] = c;
			a[j] = d;
		}
	}
	return 0;
}
char ch1[10], ch2[10], ch3[10], ch4[10];
int main()
{
	int i=0;
	while (scanf("%s%s%s%s", ch1,ch2,ch3,ch4) != EOF)
	{
		a[0] = fun(ch1[0]);
		a[1] = fun(ch2[0]);
		a[2] = fun(ch3[0]);
		a[3] = fun(ch4[0]);
		if (dfs(0))
			printf("Yes\n");
		else
			printf("No\n");
	}
}