求解24点游戏问题:PTA 7-8h0115
最编程
2024-01-23 20:43:46
...
一、题目描述
二、解题思路
首先想到的是dfs进行逐个遍历,但是会有两个错
第一个:如果出现不能整除的情况,那么答案就会丢失,因此我们需要设置一个精度,在这个范围内的答案我们都要去接受他。
第二个:如果出现(a + b)* (c + d) == 24的这种情况,我们的dfs逐个遍历就不能做到这种,因此我们就需要每次把进行计算的结果重新放入数组,然后递归下去的时候再拿出来参与计算。
三、代码实现
1 #include <bits/stdc++.h> 2 using namespace std; 3 const double inf = 1e9 + 10; 4 const double eps = 1e-5; 5 bool ok = false; 6 void dfs(int f,double a[]) 7 { 8 if(f == 1){ 9 for(int i = 1;i <= 4;i++) 10 if(fabs(24 - a[i]) <= eps) 11 ok = true; 12 return; 13 } 14 if(ok) 15 return; 16 for(int i = 1;i <= 4;i++){ 17 double sum = a[i]; 18 if(a[i] == inf) 19 continue; 20 a[i] = inf; 21 for(int j = 1;j <= 4;j++){ 22 double sum1 = a[j]; 23 if(a[j] == inf) 24 continue; 25 a[j] = sum1 + sum; 26 dfs(f - 1,a); 27 a[j] = sum1 - sum; 28 dfs(f - 1,a); 29 a[j] = sum - sum1; 30 dfs(f - 1,a); 31 a[j] = sum * sum1; 32 dfs(f - 1,a); 33 if(sum){ 34 a[j] = sum1 / sum; 35 dfs(f - 1,a); 36 } 37 if(sum1){ 38 a[j] = sum / sum1; 39 dfs(f - 1,a); 40 } 41 a[j] = sum1; 42 } 43 a[i] = sum; 44 } 45 } 46 int main() 47 { 48 double a[5]; 49 while(cin >> a[1] >> a[2] >> a[3] >> a[4]){ 50 if(!a[1] && !a[2] && !a[3] && !a[4]) 51 break; 52 ok = false; 53 dfs(4,a); 54 if(ok) 55 cout << "YES" << endl; 56 else 57 cout << "NO" << endl; 58 59 } 60 return 0; 61 }
原文地址:https://www.cnblogs.com/scannerkk/p/15991394.html