PTA - 用扑克牌计算24点|C语言|代码详解

题目描述

一副扑克牌的每张牌表示一个数（J、Q、K 分别表示 11、12、13，两个司令都表示 6）。任取4 张牌，即得到 4 个 1~13 的数，请添加运算符（规定为加+ 减- 乘* 除/ 四种）使之成为一个运算式。每个数只能参与一次运算，4 个数顺序可以任意组合，4 个运算符任意取 3 个且可以重复取。运算遵从一定优先级别，可加括号控制，最终使运算结果为 24。请输出一种解决方案的表达式，用括号表示运算优先。如果没有一种解决方案，则输出 -1 表示无解。

输入格式：

输入在一行中给出 4 个整数，每个整数取值在 [1, 13]。

输出格式：

输出任一种解决方案的表达式，用括号表示运算优先。如果没有解决方案，请输出 -1。

输入样例：

2 3 12 12

输出样例：

((3-2)*12)+12

题目分析

本题通过分析输入样例和输出样例可知，实现本题无非是一个不断尝试组合的过程，对于任何给定的四个数字，用两组括号来控制运算运算顺序有且只有五种有效形式：（图中用输入示例表示任意给出的四个数字，“？”表示填入的运算符）

这可以启发我们先用一个一维数组读入用户给出的任意4个数，然后用一个行大小为64（4*4*4*4）的二维数组存放四种运算符的所有排列可能。接下来我们构建循环去遍历每一种排列下的每一种可能，找到一个正确解法后退出循环，若在遍历所有的排列可能后也没有找到一个解法，输出 “-1”

具体来说，我们先定义函数operation和games。前者用于接收两个数，一个运算符，返回这两个数在对应运算符下的结果；后者接收将要尝试组合的4个数和1种字符组合，尝试每一种可能，找到可行解

float operation(float a, float b, char c);

int games(float a[], char c[]);

在main函数中，先读入四个数在数组num中，然后用四个运算符生成所有可能的运算符组合，储存在combination中，combination的每一行代表每一种字符组合。

接下来我们将combination的每一行的字符组合以及4个数字传给games函数，开始尝试寻找解法。

在games函数中，我们定义rst1，rst2，rst3分别用于存放第一个括号算出的值、第二个括号算出的值、最终该表达式算出的值。构建一个四层循环，在第四层循环中，进入时先检查当前正在尝试的数是否有重复（对应题给要求每个数字只能使用一次）。通过检查后，分别尝试五种括号形式，每次都通过调用operation函数算出最终该形式对应表达式的解（rst3）并与24进行比较，若找到了一个解法先打印输出，然后返回1给main函数，使main函数中的if语句为真，正常结束程序；若没找到解法，则尝试下一种括号形式或尝试下一种运算符组合。若尝试完所有可能也没有找到一个可行解则返回0给main函数，使main函数中的if语句为假。

代码实现

#include<stdio.h>
 
float operation(float a, float b, char c);
 
int games(float a[], char c[]);
 
int main()
{
	float num[4] = {0};
	int i, j, k, l = 0;
	
	for(i = 0; i < 4; i ++)
	{
		scanf("%f", &num[i]);
	}
	
	char operators[6] = {"+-*/"};
	
	char combination[64][5];
	
	//生成所有可能的运算符组合
	for(i = 0; i < 4; i ++)
	{
		for(j = 0; j < 4; j ++)
		{
			for(k = 0; k < 4; k ++)
			{
				combination[l][0] = operators[i];
				combination[l][1] = operators[j];
				combination[l][2] = operators[k];
				l ++;
			}
		} 
	}
	
	for(i = 0; i < 64; i ++)
	{
		if(games(num, combination[i]))
		{
			return 0;
		}
	}
	printf("-1");
	
	return 0;
}
 
int games(float a[], char c[])
{
	int i, j, k, l;
	float rst1 = 0, rst2 = 0, rst3 = 0;
	
	for(i = 0; i < 4; i ++)
		for(j = 0; j < 4; j ++)
			for(k = 0; k < 4; k ++)
				for(l = 0; l < 4; l ++)
					{
						if(i != j && i != k && i != l && j != k && j != l && k != l)
						{
							//[1] ((3-2)*12)+12形式
							rst1 = operation(a[i], a[j], c[0]);
							rst2 = operation(rst1, a[k], c[1]);
							rst3 = operation(rst2, a[l], c[2]);
							if(rst3 == 24)
							{
								printf("((%.0f%c%.0f)%c%.0f)%c%.0f", a[i], c[0], a[j], c[1], a[k], c[2], a[l]);
								return 1;
							}
							
							//[2] (3-(2*12))+12形式
							rst1 = operation(a[j], a[k], c[1]);
							rst2 = operation(a[i], rst1, c[0]);
							rst3 = operation(rst2, a[l], c[2]);
							if(rst3 == 24) 
							{
								printf("(%.0f%c(%.0f%c%.0f))%c%.0f", a[i], c[0], a[j], c[1], a[k], c[2], a[l]);
								return 1;
							}
							
							//[3] (3-2)*(12+12)形式
							rst1 = operation(a[i], a[j], c[0]);
							rst2 = operation(a[k], a[l], c[2]);
							rst3 = operation(rst1, rst2, c[1]);
							if(rst3 == 24)
							{
								printf("(%.0f%c%.0f)%c(%.0f%c%.0f)", a[i], c[0], a[j], c[1], a[k], c[2], a[l]);
								return 1;
							}
							
							//[4] 3-(2*(12+12))形式
							rst1 = operation(a[k], a[l], c[2]);
							rst2 = operation(a[j], rst1, c[1]);
							rst3 = operation(a[i], rst2, c[0]);
							if(rst3 == 24)
							{
								printf("%.0f%c(%.0f%c(%.0f%c%.0f))", a[i], c[0], a[j], c[1], a[k], c[2], a[l]);
								return 1;
							}
							
							//[5] 3-((2*12)+12)形式
							rst1 = operation(a[j], a[k], c[1]);
							rst2 = operation(rst1, a[l], c[2]);
							rst3 = operation(a[i], rst2, c[0]);
							if(rst3 == 24)
							{
								printf("%.0f%c((%.0f%c%.0f)%c%.0f)", a[i], c[0], a[j], c[1], a[k], c[2], a[l]);
								return 1;
							}
						}
					}
	return 0; 
}
 
float operation(float a, float b, char c)
{
	switch(c)
	{
		case '+':
			return a + b;
			
		case '-':
			return a - b;
			
		case '*':
			return a * b;
			
		case '/':
			return a / b;
	}
}

PTA测试结果：