题解 | #24点游戏算法#
24点游戏算法
https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
//注意输入为double类型
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
double cal(double a, double b, int op) {
if (op == 0) return a + b;
else if (op == 1) return a - b;
else if (op == 2) return a * b;
else return a / b;
}
bool dfs(vector<double>& nums, int op, double sum, int index, vector<int>& ops) {
sum = cal(sum, nums[index], op);
if (index == 3 && sum == 24) {
return true;
} else if (index == 3) {
return false;
}
for (int i = 0; i < 4; ++i) {
ops.push_back(i);
if (dfs(nums, i, sum, index + 1, ops)) {
return true;
}
ops.pop_back();
}
return false;
}
int main() {
vector<double> nums(4);
for (int i = 0; i < 4; ++i) {
cin >> nums[i];
}
vector<int> ops;
sort(nums.begin(), nums.end());
while (next_permutation(nums.begin(), nums.end())) {
for (int i = 0; i < 4; ++i) {
ops.push_back(i);
if (dfs(nums, i, nums[0], 1, ops)) {
cout<<"true"<<endl;
return 0;
}
ops.pop_back();
}
}
cout<<"false"<<endl;
return 0;
}