C ++中的24游戏
假设我们有四张牌;这些卡的编号从1到9。我们必须检查它们是否可以通过+,-,*,/之类的运算符进行运算以获得24。因此,如果我们有一些数字[4,9,2,6],则可以通过(4*9)–(2*6)得到24,答案将是正确的。
为了解决这个问题,我们将遵循以下步骤-
epsilon:=10.0^-5
定义一个函数solve()
,它将采用数组v,
如果v的大小等于1,则-
|v[0]-24.0|时返回true<=epsilon
对于初始化i:=0,当i<v的大小时,更新(将i增加1),执行-
如果i与j相同,则:忽略以下部分,跳至下一个迭代
定义数组res
对于初始化k:=0,当k<v的大小时,更新(将k增加1),执行-
对于初始化k:=0,当k<4时,更新(将k增加1),执行-
在res的末尾插入v[k]
如果i不等于k并且j不等于k,则-
返回真
在res的末尾插入v[i]/v[j]
在res的末尾插入v[i]*v[j]
在res的末尾插入v[i]-v[j]
在res的末尾插入v[i]+v[j]
如果operator[k]与'+'相同,则-
否则,如果operator[k]与'-'相同,则-
否则,如果operator[k]与'*'相同,则-
除此以外
如果solve(res),则-
从res删除最后一个元素
对于初始化j:=0,当j<v的大小时,更新(将j增加1),执行-
返回假
从主要方法执行以下步骤-
定义数组v
对于初始化i:=0,当i<nums大小时,更新(将i增加1),执行-
在v的末尾插入nums[i]
返回solve(v)
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h> using namespace std; class Solution { public: char operators[4] = {'+', '-', '/', '*'}; double epsilon = pow(10.0, -5); bool judgePoint24(vector<int>& nums) { vector <double> v; for(int i = 0; i < nums.size(); i++){ v.push_back(nums[i]); } return solve(v); } bool solve(vector <double> v){ if(v.size() == 1){ return abs(v[0] - 24.0) <= epsilon; } for(int i = 0; i < v.size(); i++){ for(int j = 0; j < v.size(); j++){ if(i == j) continue; vector <double> res; for(int k = 0; k < v.size(); k++){ if(i != k && j != k){ res.push_back(v[k]); } } for(int k = 0; k < 4; k++){ if(operators[k] == '+'){ res.push_back(v[i] + v[j]); }else if(operators[k] == '-'){ res.push_back(v[i] - v[j]); }else if(operators[k] == '*'){ res.push_back(v[i] * v[j]); }else{ res.push_back(v[i] / v[j]); } if(solve(res)) return true; res.pop_back(); } } } return false; } }; main(){ Solution ob; vector<int> v = {4,9,2,6}; cout << (ob.judgePoint24(v)); }
输入值
{4,9,2,6}
输出结果
1