蓝桥杯练习系统（算法训练）ALGO-995 24点

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　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

#include<iostream>
using namespace std;
int a[4];
int ans;
//在有n个数的数组a中，寻找最大的不超过24的数 
void dfs(int* a,int n){if(n==1){if(a[0]<=24){ans=max(ans,a[0]);}return ;} for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){int x=a[i],y=a[j];a[j]=x+y;//加法 a[i]=a[n-1];dfs(a,n-1);a[j]=x*y;//乘法 a[i]=a[n-1];dfs(a,n-1);a[j]=x-y;//减法 a[i]=a[n-1];dfs(a,n-1);a[j]=y-x;a[i]=a[n-1];dfs(a,n-1);if(y!=0&&x%y==0){//除法 a[j]=x/y;a[i]=a[n-1];dfs(a,n-1);}if(x!=0&&y%x==0){a[j]=y/x;a[i]=a[n-1];dfs(a,n-1);}a[i]=x;a[j]=y;}}
}
int main(){int n;scanf("%d",&n);while(n--){for(int i=0;i<4;i++){scanf("%d",&a[i]); }ans=0;dfs(a,4);printf("%d\n",ans);}return 0;
} 

 思路：dfs深搜。先取两个数进行运算，将运算后的结果看成是一个数，所以现在相当于有3个数进行24点。再在这3个数中取两个数进行运算，运算后相当于只有2个数，将这2个数进行24点，得到1个数，即结果a[0]。取a[0]的最大值，即答案。

int x=a[i],y=a[j];a[j]=x+y;//加法 
a[i]=a[n-1];
dfs(a,n-1);

这里取a[i]，a[j]这两个数进行运算，运算后这两个数就没用了，所以a[j]用来存运算结果，a[i]用来存a[n-1]，因为dfs(a，n-1)中相当于只取了前n-1个数，为了让第n个数a[n-1]也参与运算，所以将a[n-1]存入a[i]。

如:1 4 6 8

一轮后有效数字：5 6 8

数组中表示：8 5 6 8

因为dfs(a，n-1)，所以其中最后一个数取不到，但是已经将它存到了最前面