贤鱼刷题日常1789:算24【c++】

简介: 算24详细题解

@TOC

题目描述

描述
给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。

这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。

比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。
输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。
样例输入
5 5 5 1
1 1 4 2
0 0 0 0
样例输出
YES
NO
这道题我们将+-*/全部扔到函数中,深搜处理即可

AC代码

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
double a[8]={1,1,1,1},b[10087];
int f=0;
void dfs(int n){
    if(n==4){
        if(a[1]>23.9999&&a[1]<24.000001)
            f++;
            return;
    }
    if(f==0){
        for(int i=1;i<=4;i++){
            if(b[i]==1) continue;
            for(int j=i+1;j<=4;j++){
                if(b[j]==1) continue;//去重
                b[j]=1;
                double x=a[i],y=a[j];
                a[i]=x+y;dfs(n+1);
                a[i]=x/y;dfs(n+1);
                a[i]=x-y;dfs(n+1);
                a[i]=x*y;dfs(n+1);
                a[i]=y-x;dfs(n+1);
                a[i]=y/x;dfs(n+1);
                b[j]=0;//这里记得清零
                a[i]=x;a[j]=y;
            }
        }
    }
}
int main(){
    while(a[1]+a[2]+a[3]+a[4]!=0){
        for(int i=1;i<=4;i++){
            cin>>a[i];
        }
        if(a[1]+a[2]+a[3]+a[4]==0){
            break;
        }
        memset(b,0,sizeof(b));
        dfs(1);
        if(f!=0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        f=0;
    }
}

@^ _ ^@

相关文章
|
算法 C语言 C++
从C语言的使用转换到C++(上篇)——刷题、竞赛篇
从C语言的使用转换到C++(上篇)——刷题、竞赛篇
270 0
|
存储 C++
【五一创作】C++刷题 【入门4】数组
【五一创作】C++刷题 【入门4】数组
108 0
|
机器学习/深度学习 存储 人工智能
【c++百日刷题计划】 ———— DAY12,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY12,奋战百天,带你熟练掌握基本算法
210 0
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6月前
|
C语言 C++
【C语言/C++】牛客网刷题训练-12
【C语言/C++】牛客网刷题训练-12
|
6月前
|
存储 自然语言处理 C++
刷题用到的非常有用的函数c++(持续更新)
刷题用到的非常有用的函数c++(持续更新)
84 1
|
存储 C语言 C++
【C/C++刷题——leetcode】查找字符串中最大的子串
【C/C++刷题——leetcode】查找字符串中最大的子串
302 0
|
机器学习/深度学习 人工智能 C++
【c++百日刷题计划】 ———— DAY16,刷题百天,养成刷题好习惯
【c++百日刷题计划】 ———— DAY16,刷题百天,养成刷题好习惯
189 0
【c++百日刷题计划】 ———— DAY16,刷题百天,养成刷题好习惯
|
存储 算法 C++
【c++百日刷题计划】 ———— DAY13,奋战百天,带你熟练掌握基本算法
【c++百日刷题计划】 ———— DAY13,奋战百天,带你熟练掌握基本算法
336 0