本文主要是介绍蓝桥杯练习系统(算法训练)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),所以其中最后一个数取不到,但是已经将它存到了最前面
这篇关于蓝桥杯练习系统(算法训练)ALGO-995 24点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!