1.题目呈现

问题描述

　　24点游戏是一个非常有意思的游戏，很流行，玩法很简单：给你4张牌，每张牌上有数字（其中A代表1，J代表11，Q代表12，K代表13），你可以利用数学中的加、减、乘、除以及括号想办法得到24，例如：
　　((A*K)-J)*Q等价于((1*13)-11)*12=24
　　加减乘不用多说了，但除法必须满足能整除才能除！这样有一些是得不到24点的，所以这里只要求求出不超过24的最大值。

输入格式

　　输入第一行N(1<=N<=5)表示有N组测试数据。每组测试数据输入4行，每行一个整数(1到13)表示牌值。

输出格式

　　每组测试数据输出一个整数，表示所能得到的最大的不超过24的值。

样例输入

3
3
3
3
3
1
1
1
1
12
5
13
1

样例输出

24
4
21

2.思路剖析

这又是一道关于搜索的题目

我们的前面已经做过一些搜索的题目的

例如

跳马：蓝桥杯算法训练 跳马 C++实现-CSDN博客

无聊的逗：蓝桥杯算法训练 无聊的逗 C++实现-CSDN博客

数字游戏：蓝桥杯算法训练 数字游戏 C++实现-CSDN博客

其中大部分的题目我们都可以采用DFS即暴力递归来完成

这道题也不例外

可能很多小伙伴在看到这道题的时候有点手忙脚乱，不知如何下手

我们可以看到，本题的1<N<5所以数据量并不是很大，此时我们可以采用暴力DFS的思路来完成

即 两两一组 枚举全部的情况 省的咱们还要考虑优先级的问题

3.代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int a[5];
int maxnum;

void dfs(int n){
	if(n==1){//最终的数组在收缩的过程中会收缩成a[1]的一个数组，此时只有a[0]有数据 
		if(a[n-1]>24) return ;
		else maxnum = max(maxnum,a[n-1]);
		return ;
	}
	else {
		for(int i=0;i<n-1;i++)
		   for(int j=i+1;j<n;j++){//两两一组 进行暴力搜索 
		   	   int n1 = a[i];
		   	   int n2 = a[j];
		   	   
		   	   a[j]=n1+n2;//使用j来存储已经计算的结果 
		   	   a[i]=a[n-1];//缩短长度,因为第一位已经计算过了，所以最后一位赋值给第一位 
			   dfs(n-1);
			    
			   a[j]=n1-n2;
			   a[i]=a[n-1];
			   dfs(n-1);
			   
			   a[j]=n2-n1;
			   a[i]=a[n-1];
			   dfs(n-1);
			   
			   a[j]=n1*n2;
			   a[i]=a[n-1];
			   dfs(n-1);
			   
			   if(n2!=0&&n1%n2==0){
			   	 a[j]=n1/n2;
			   	 a[i]=a[n-1];
			   	 dfs(n-1);
			   }
			   if(n1!=0&&n2%n1==0){
			   	  a[j]=n2/n1;
			   	  a[i]=a[n-1];
			   	  dfs(n-1);
			   }
			   
			   a[i]=n1;
			   a[j]=n2;//回溯，并恢复原来的数值 方便下次搜索 
		   }
	}
}

int main(){
	int n;
	cin >> n;
	vector<int> v;
	for(int i=0;i<n;i++){
		for(int i=0;i<4;i++) cin >> a[i];
		maxnum=-1;
		dfs(4);
		v.push_back(maxnum);
	}
	for(int i=0;i<n;i++){
		cout << v[i] << endl;
	}
	return 0;
}