c++ 回溯算法,回溯的是一个map,用来记录用过的牌
24点运算
http://www.nowcoder.com/questionTerminal/7e124483271e4c979a82eb2956544f9d
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
string pukef(int x) {
if (x >= 2 && x <= 10) {
return to_string(x);
}
switch (x) {
case 1:
return "A";
break;
case 11:
return "J";
break;
case 12:
return "Q";
break;
case 13:
return "K";
break;
default:
break;
}
}
int puke(string x) {
if (x.size() == 1) {
if (x.front() >= '2' && x.front() <= '9') {
return stoi(x);
}
switch (x.front()) {
case 'A':
return 1;
break;
case 'J':
return 11;
break;
case 'Q':
return 12;
break;
case 'K':
return 13;
break;
default:
break;
}
} else if (x == "10") {
return 10;
} else
return 0;
}
bool ok;
void dfs(string &s, int &ans, unordered_map<int, int> &us, vector<int> &v,
unordered_map<int, int> &vs) {
int ci = 0;
for (auto &i : us) {
ci += i.second;
}
if (ci == 4) {
if (ans == 24) {
cout << s.substr(1) << endl;
ok = 1;
return;
}
return;
}
s.push_back('+');
for (int var = 0; var < v.size(); ++var) {
if (us[v.at(var)] < vs[v.at(var)]) {
string n = pukef(v.at(var));
s += n;
ans += v.at(var);
us[v.at(var)]++;
dfs(s, ans, us, v, vs);
if (ok) {
return;
}
ans -= v.at(var);
us[v.at(var)]--;
s.erase(s.size() - n.size());
}
}
s.pop_back();
s.push_back('-');
for (int var = 0; var < v.size(); ++var) {
if (us[v.at(var)] < vs[v.at(var)]) {
string n = pukef(v.at(var));
s += n;
ans -= v.at(var);
us[v.at(var)]++;
dfs(s, ans, us, v, vs);
if (ok) {
return;
}
ans += v.at(var);
us[v.at(var)]--;
s.erase(s.size() - n.size());
}
}
s.pop_back();
s.push_back('*');
for (int var = 0; var < v.size(); ++var) {
if (us[v.at(var)] < vs[v.at(var)]) {
string n = pukef(v.at(var));
s += n;
ans *= v.at(var);
us[v.at(var)]++;
dfs(s, ans, us, v, vs);
if (ok) {
return;
}
ans /= v.at(var);
us[v.at(var)]--;
s.erase(s.size() - n.size());
}
}
s.pop_back();
s.push_back('/');
for (int var = 0; var < v.size(); ++var) {
if (us[v.at(var)] < vs[v.at(var)] && ans / v.at(var) >= 2
&& ans % v.at(var) == 0) {
string n = pukef(v.at(var));
s += n;
ans /= v.at(var);
us[v.at(var)]++;
dfs(s, ans, us, v, vs);
if (ok) {
return;
}
ans *= v.at(var);
us[v.at(var)]--;
s.erase(s.size() - n.size());
}
}
s.pop_back();
}
int main() {
string a, b, c, d;
while (cin >> a >> b >> c >> d) {
int ai = puke(a);
int bi = puke(b);
int ci = puke(c);
int di = puke(d);
if (ai && bi && ci && di) {
string s { "" };
int ans = 0;
unordered_map<int, int> us;
vector<int> v { ai, bi, ci, di };
unordered_map<int, int> vs;
for (auto &i : v) {
vs[i]++;
}
dfs(s, ans, us, v, vs);
if (!ok) {
cout << "NONE" << endl;
}
} else {
cout << "ERROR" << endl;
}
}
return 0;
} 注意除法
注意牌可以重复
注意输出牌面符号


腾讯成长空间 5958人发布