回顧

之前寫(xiě)的版本[深搜回溯]24點(diǎn)，沒(méi)有考慮到中間數(shù)值的可能性，是對(duì)數(shù)值進(jìn)行深搜遍歷，而不是對(duì)數(shù)值對(duì)進(jìn)行深搜數(shù)值遍歷，使得較為復(fù)雜的24點(diǎn)運(yùn)算中有部分?jǐn)?shù)據(jù)沒(méi)辦法得到解決。這次的改進(jìn)將圍繞著這個(gè)進(jìn)行。

這個(gè)項(xiàng)目也被我放到了Github上關(guān)于算法的Repository上
https://github.com/Sean16SYSU/Algorithms4N

算法思路

• 當(dāng)數(shù)組長(zhǎng)度為1的時(shí)候輸出，判斷是否為24點(diǎn)，如果是24點(diǎn)，就輸出對(duì)應(yīng)的數(shù)學(xué)表達(dá)。
• 如果數(shù)組長(zhǎng)度大于等于2，則進(jìn)行深度搜索
  • 在數(shù)組中任意選擇兩個(gè)數(shù)值，再選擇加法，左減，右減（減法有順序），左除，右除，乘法。（只有加法和乘法具有交換律）

測(cè)試數(shù)據(jù)

1 1 5 5 5 (5*(5-(1/5)))

• 第一個(gè)數(shù)值為算式數(shù)量，
• 第二行的輸入為數(shù)值
• 第三行為輸出

這個(gè)數(shù)據(jù)，只有在考慮數(shù)值對(duì)的時(shí)候，才會(huì)被解決。是一個(gè)不錯(cuò)的數(shù)據(jù)。

代碼

#include <iostream> #include <stack> #include <string> #include <cmath> #include <vector> using namespace std;double arr[4];bool DFS(double *tmp, string* formulas, int size) {if (size == 1) {// cout << tmp[0] << " " << formulas[0] << endl;if (tmp[0] == 24) {cout << formulas[0] << endl;return true;}return false;}double *new_tmp = new double[size - 1];string *new_formulas = new string[size - 1];for (int i = 0; i < size; ++i) {for (int j = i + 1; j < size; ++j) {int tot = 0;for (int p = 0; p < size; ++p) {if (p != i && p != j) {new_tmp[tot++] = tmp[p];}}tot = 0;for (int p = 0; p < size; ++p) {if (p != i && p != j) {new_formulas[tot++] = formulas[p];}}// op:0, temp + valuenew_tmp[size - 2] = tmp[i] + tmp[j];new_formulas[size - 2] = (string("(") + formulas[i] + string("+") + formulas[j] + string(")"));if (DFS(new_tmp, new_formulas, size - 1))return true;// op:1, temp - valuenew_tmp[size - 2] = tmp[i] - tmp[j];new_formulas[size - 2] = (string("(") + formulas[i] + string("-") + formulas[j] + string(")"));if (DFS(new_tmp, new_formulas, size - 1))return true;// op:2, value - temp new_tmp[size - 2] = tmp[j] - tmp[i];new_formulas[size - 2] = (string("(") + formulas[j] + string("-") + formulas[i] + string(")"));if (DFS(new_tmp, new_formulas, size - 1))return true;// op:3, temp / valuenew_tmp[size - 2] = tmp[i] / tmp[j];new_formulas[size - 2] = (string("(") + formulas[i] + string("/") + formulas[j] + string(")"));if (DFS(new_tmp, new_formulas, size - 1))return true;// op:4, value / temp new_tmp[size - 2] = tmp[j] / tmp[i];new_formulas[size - 2] = (string("(") + formulas[j] + string("/") + formulas[i] + string(")"));if (DFS(new_tmp, new_formulas, size - 1))return true;// op:5, temp * valuenew_tmp[size - 2] = tmp[i] * tmp[j];new_formulas[size - 2] = (string("(") + formulas[i] + string("*") + formulas[j] + string(")"));if (DFS(new_tmp, new_formulas, size - 1))return true;}}delete[] new_tmp;delete[] new_formulas;return false; }int main() {int time;cin >> time;while (time--) {for (int i = 0; i < 4; ++i) {cin >> arr[i];}string formula[4];for (int i = 0; i < 4; ++i) formula[i] = to_string(int(arr[i]));if (DFS(arr, formula, 4)) {continue;}else {cout << "None\n";}}system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的[深搜]24点--改进版本的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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