蓝桥杯 试题 算法训练 24点（dfs）_dfs实现24点游戏

题目链接

按照题目意思是4个数字可以任意排列，数字之间的运算符可以任意，括号可以任意添加，换句话说就是这些数据可以两两按照4种运算自由组合，当两个数字运算组合成为一个中间结果后，此结果又能和未组合的数据进行任意组合，直到只剩一个数字，递归找到所有组合方案，保存最接近24的答案即可。

需要注意的是组合的中间结果可能出现0，因此做除法时需要加上除数不为0的条件。

import java.util.*;
public class Main{
	public static int[] nums=new int[4];
	public static int ans=-0x3f3f3f3f;
	public static void dfs(int[] arr,int cnt) {
		//递归的时候应该对于这三个数一视同仁，也能自由组合
		if(cnt==1) {
			if(arr[0]<=24) {
				ans=Math.max(arr[0], ans);
			}
			return ;
		}
		boolean[] vis=new boolean[cnt];
		Arrays.fill(vis, false);
		for(int i=0;i<cnt;i++) {//双重循环保证arr中任意两个数据可以组合
			vis[i]=true;
			for(int j=0;j<cnt;j++) {
				if(!vis[j]) {
					vis[j]=true;
					int[] newarr=new int[cnt-1];//新组合结果和剩余没组合的数形成一个新数组dfs
					int k=0;
					for(int m=0;m<cnt;m++) {
						if(!vis[m]) {
							newarr[k++]=arr[m];
						}
					}
					newarr[k]=arr[i]+arr[j];
					dfs(newarr,cnt-1);//递归不会修改newarr，所以后面能接着用
					newarr[k]=arr[i]-arr[j];
					dfs(newarr,cnt-1);//递归不会修改newarr，所以后面能接着用
					newarr[k]=arr[i]*arr[j];
					dfs(newarr,cnt-1);//递归不会修改newarr，所以后面能接着用
					if(arr[j]!=0 && arr[i]%arr[j]==0) {
						//因为经过自由组合 arr[j]作为某次组合的中间结果可能为0
						newarr[k]=arr[i]/arr[j];
						dfs(newarr,cnt-1);//递归不会修改newarr，所以后面能接着用
					}
					vis[j]=false;
					
				}
			}
			vis[i]=false;
		}
	}
	public static void main(String[] Agrs) {
		Scanner sc=new Scanner(System.in);
		
		int N;
		N=sc.nextInt();
		for(int t=0;t<N;t++) {
			//Arrays.fill(vis, false);
			ans=-0x3f3f3f3f;
			for(int i=0;i<4;i++) {
				nums[i]=sc.nextInt();
			}
			//对任意两数进行+-*/的组合
			dfs(nums,4);
			System.out.println(ans);
		}
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62