24点游戏

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/problem/show/1252

Description

24点就是给你一串数字，问你是否通过加减乘除括号构成24点。

沈爷觉得这个很好玩，就决定考考你，给你4个数，可以交换位置，可以用加减乘除和括号，是否能构成24点呢？

注意哦~这里的除法并不是整数除法，比如样例

Input

第一行T，表示有多少组测试数据，1≤T≤50

接下来T行，每行4个正整数a1, a2, a3, a4，表示每个数都是多少，1≤ai≤13

Output

对于每一次询问，如果能够凑成24点，输出yes，否则输出no

Sample Input

23 3 8 81 1 1 1

Sample Output

yesno

HINT

 

题意

 

题解：

1.递归处理，深度优先搜索

dfs(int n) 表示我现在还剩下多少个数，没有处理

由于有括号的原因，我们每次就直接暴力枚举n个数中的两个数，然后进行加减乘除就好了，然后将这两个数变成新的一个数，然后dfs(n-1)就好了，这样不停的递归下去。

关于有理数除法的问题，我们有2种方法可以解决

(1)自己手写一个分数的类（比较麻烦），然后进行分数的加减乘除去解决这一道题

(2)由于只有4个数，而且每个数最大才13，所以我们直接全部用小数去处理就好了，最后的答案能够得到24的话，那么最后我们剩下的那个小数x，必定满足fabs(x-24)<Y，其中Y是一个接近于0的数。在本题，eps 只要小于0.01就能过

2.直接暴力写出所有情况即可

a[1]+a[2]+a[3]+a[4]

a[1]+a[2]+a[3]*a[4]

......

一直写下去就好

大概应该只有600多个

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;double a[5];bool fun(int n){    if(n==1){        if(fabs(a[0]-24)<1e-6)return true;        else return false;    }    for(int i=0;i
         
          >T;    while(T--){        cin>>a[0]>>a[1]>>a[2]>>a[3];        if(fun(4))cout<<"yes\n";        else cout<<"no\n";    }    return 0;}