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; }
注意除法
注意牌可以重复
注意输出牌面符号