题目1 : 搜索一·24点
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
周末，小Hi和小Ho都在家待着。
在收拾完房间时，小Ho偶然发现了一副扑克，于是两人考虑用这副扑克来打发时间。
小Ho：玩点什么好呢？
小Hi：两个人啊，不如来玩24点怎么样，不靠运气就靠实力的游戏。
小Ho：好啊，好啊。
<经过若干局游戏之后>
小Ho：小Hi，你说如果要写个程序来玩24点会不会很复杂啊？
小Hi：让我想想。
<过了几分钟>
小Hi：我知道了！其实很简单嘛。
输入
第1行：1个正整数, t，表示数据组数，2≤t≤100。
第2..t+1行：4个正整数, a,b,c,d，1≤a,b,c,d≤10。
输出
第1..t行：每行一个字符串，第i行表示第i组能否计算出24点。若能够输出"Yes"，否则输出"No"。
- 样例输入
-
2 5 5 5 1 9 9 9 9
- 样例输出
-
Yes No
解题思路
数据量不大，所以可以直接暴力枚举，4个数字，3个操作运算符，4个数字共有4！=24中可能，3个操作符共有4^3 共64种，因为有多种优先级次序，一次枚举。
(A#B)#(C#D)
((A#B)#C)#D
A#(B#(C#D))
(A#(B#C))#D
A#((B#C)#D)代码：
1 #include<iostream> 2 3 using namespace std; 4 5 double number[4]; 6 double nowNumber[4]; 7 char ops[3]; 8 char opType[4] = { '+', '-', '*', '/' }; 9 bool used[4]={false}; 10 int num; 11 12 double calc(double a, double b, char c){ 13 double s = 0.0; 14 switch (c) 15 { 16 case '+': s = a + b;break; 17 case '-': s = a - b;break; 18 case '*': s = a*b;break; 19 case '/': if (b != 0) s = b / a;break; 20 default: break; 21 } 22 return s; 23 } 24 25 bool makeOperation(int depth){ 26 if(depth>=3){ 27 if ( calc(calc(number[0], number[1],ops[0]), calc(number[2], number[3],ops[1]),ops[2]) == 24 //(A#B)#(C#D) 28 || calc(calc(calc(number[0],number[1],ops[0]),number[2],ops[1]),number[3],ops[2]) == 24 //((A#B)#C)#D 29 || calc(number[0], calc(number[1], calc(number[2], number[3], ops[2]), ops[1]), ops[0]) == 24 //A#(B#(C#D)) 30 || calc(calc(number[0], calc(number[1], number[2], ops[1]), ops[0]), number[3], ops[2]) == 24 //(A#(B#C))#D 31 || calc(number[0], calc(calc(number[1], number[2], ops[1]), number[3], ops[2]), ops[0]) == 24 //A#((B#C)#D) 32 ) 33 34 return true; 35 else 36 return false; 37 } 38 39 for(int i=0;i<4;i++){ 40 ops[depth] = opType[i]; 41 if (makeOperation(depth + 1)) 42 return true; 43 } 44 return false; 45 } 46 47 bool makeNumber(int depth){ 48 if(depth>=4) 49 return makeOperation(0); 50 51 for(int i=0;i<4;i++){ 52 if(!used[i]){ 53 nowNumber[depth]=number[i]; 54 used[i]=false; 55 56 if(makeNumber(depth+1)) 57 return true; 58 59 used[i]=false; 60 } 61 } 62 return false; 63 } 64 65 int main(){ 66 int n; 67 cin>>n; 68 69 while(n--){ 70 for (int i = 0; i < 4; i++) 71 cin >> number[i]; 72 73 if (makeNumber(0)) 74 cout << "Yes" << endl; 75 else 76 cout << "No" << endl; 77 } 78 return 0; 79 }
题解中给的思路是，引入“反-”和“反/”，运算符增加2种，优先级结合次序可以减少3中，效率更优。