如果你是移動端，我推薦點(diǎn)擊這個看鏈接看推送版的
推送版的鏈接

題目描述：
24點(diǎn)是一個有趣的撲克牌游戲。發(fā)4張牌，然后計算是否能夠算出24點(diǎn)來。（不考慮有括號的算式，輸出計算式將從左到有進(jìn)行計算）
如果可以，輸出算數(shù)表達(dá)式；
如果不可以，輸出NONE
如果表達(dá)式中，有錯誤輸入，輸出“ERROR”
輸入實(shí)例：
2
AAAA
Q3J8
輸出實(shí)例：
NONE
Q-J*3*8

代碼解析：
下面解析，將以對其中一組數(shù)據(jù)（4個字符）為例

main函數(shù)中讀入字符串

先選擇第一個數(shù)

開始深搜，一直到搜了四個數(shù)之后，判斷是否為24，是就將更新答案，并返回True

進(jìn)行選擇，每一次深搜，都是選擇一個運(yùn)算符和一個數(shù)字（字符）。用tempAns來記錄表達(dá)式。

注意要對深搜部分進(jìn)行恢復(fù)，避免影響下一次深搜。同時用visited記錄訪問過的點(diǎn)，避免重復(fù)使用，并進(jìn)入死循環(huán)。（答案錯了就檢查是不是沒有深搜恢復(fù)好；出現(xiàn)死循環(huán)，很有可能是因?yàn)闆]有標(biāo)記訪問過的點(diǎn)）

#include <iostream> #include <cstring> #include <cmath> using namespace std;char cards[4]; bool visited[4]; char cal[] = {'+', '-', '*', '/'}; string ans, tempAns; double tempNum; int charToNum(char c) {if (c <= '9' && c>= '0') {return c - '0';} else if (c == 'J') {return 11;} else if (c == 'Q') {return 12;} else if (c == 'K') {return 13;} else if (c == 'A') {return 1;}return -1; } bool DFS(int now) { // now From 1if(now == 4) {if (abs(tempNum - 24) < 1e-6) {ans = tempAns;return true;} return false;}// choose a calfor (int i = 0; i < 4; ++i) {for (int j = 0; j < 4; ++j) {if (!visited[j]) {if (i == 0) {tempNum += charToNum(cards[j]);visited[j] = true;tempAns.push_back(cal[i]);tempAns.push_back(cards[j]);} else if (i == 1) {tempNum -= charToNum(cards[j]);visited[j] = true;tempAns.push_back(cal[i]);tempAns.push_back(cards[j]);} else if (i == 2) {tempNum *= charToNum(cards[j]);visited[j] = true;tempAns.push_back(cal[i]);tempAns.push_back(cards[j]);} else if (i == 3) {tempNum /= charToNum(cards[j]);visited[j] = true;tempAns.push_back(cal[i]);tempAns.push_back(cards[j]);}if(DFS(now + 1)) {return true;}if (i == 0) {tempNum -= charToNum(cards[j]);visited[j] = false;tempAns = tempAns.substr(0, tempAns.length() - 2);} else if (i == 1) {tempNum += charToNum(cards[j]);visited[j] = false;tempAns = tempAns.substr(0, tempAns.length() - 2);} else if (i == 2) {tempNum /= charToNum(cards[j]);visited[j] = false;tempAns = tempAns.substr(0, tempAns.length() - 2);} else if (i == 3) {tempNum *= charToNum(cards[j]);visited[j] = false;tempAns = tempAns.substr(0, tempAns.length() - 2);}}}}return false; }int main(){int time, fa;cin >> time;while(time--) {char c;fa = true;for (int i = 0; i < 4; ++i){cin >> c;if (c <= '9' && c>= '0' || c == 'J' || c == 'Q' || c == 'K' || c == 'A') {cards[i] = c;} else {fa = false;}}if (!fa) {cout << "Error!\n"; continue;}memset(visited, false, sizeof(visited));bool ok = false;for (int i = 0; i < 4; ++i) {tempAns.clear();visited[i] = true;tempAns.push_back(cards[i]);tempNum = charToNum(cards[i]);if (DFS(1)){cout<< ans<< endl;ok = true;break;}visited[i] = false;}if (!ok) {cout << "NONE\n";}} }

類似需求的一個改進(jìn)版本

• 但任然不完善，沒辦法解決 1 5 5 5 這個數(shù)學(xué)式子的24點(diǎn)問題。

#include <iostream> #include <stack> #include <string> #include <cmath> using namespace std;double arr[4]; struct pi{int v, op;/* l: temp valuer: each number in arrop:0: l + r1: l - r2: r - l3: l / r4: r / l5: l * r*/pi(int v_ = 0, int op_ = 0) {v = v_;op = op_;} }; stack< pi > tmp_path; bool visited[4];bool DFS(int temp, int time) {if (time == 4) { return abs(temp - 24) < 1e-6; }double value;for (int i = 1; i < 4; ++i) {if (visited[i]) continue;else visited[i] = true;value = arr[i];// op:0, temp + valuetmp_path.push(pi(value, 0));if (DFS(temp + value, time + 1))return true;tmp_path.pop();// op:1, temp - valuetmp_path.push(pi(value, 1));if (DFS(temp - value, time + 1))return true;tmp_path.pop();// op:2, value - temp tmp_path.push(pi(value, 2));if (DFS(value - temp, time + 1))return true;tmp_path.pop();// op:3, temp / valuetmp_path.push(pi(value, 3));if (DFS(temp / value, time + 1))return true;tmp_path.pop();// op:4, value - temp tmp_path.push(pi(value, 4));if (DFS(value / temp, time + 1)) return true;tmp_path.pop();// op:5, temp * valuetmp_path.push(pi(value, 5));if (DFS(temp * value, time + 1)) return true;tmp_path.pop();visited[i] = false;}return false; }string returnCalStr(int time) {string s;string op_str;if (time == 3) {s = to_string(int(arr[0]));return s;}else {pi t_pi = tmp_path.top();s = to_string(int(t_pi.v));tmp_path.pop();string tmp = returnCalStr(time+1);if (t_pi.op == 0) {op_str = string("+");}else if (t_pi.op == 1 || t_pi.op == 2) {op_str = string("-");}else if (t_pi.op == 3 || t_pi.op == 4) {op_str = string("/");}else op_str = string("*");if (t_pi.op == 2 || t_pi.op == 4) {return string("(") + s + op_str + tmp + string(")");}else {return string("(") + tmp + op_str + s + string(")");} } }void print_path() {cout << returnCalStr(0) << endl; }int main() {int time;cin >> time;while (time--) {for (int i = 0; i < 4; ++i) {cin >> arr[i];}for (int i = 0; i < 4; ++i) visited[i] = false;visited[0] = true;if (DFS(arr[0], 1)) {print_path();}else {cout << "None\n";}}system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的[深搜回溯]24点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。