CSU 1600 Twenty：24 點遊戲 DFS 暴力搜索解法

題目描述

給定 4 個整數（1~13），判斷能否通過加減乘除運算（每個數恰好用一次）得到 24。多組測試用例，輸出 "Yes" 或 "No"。

解題思路：全排列 + 運算符組合枚舉

數字只有 4 個，搜索空間極小，直接暴力 DFS 即可：

1. 對 4 個數進行全排列（24 種）。
2. 對 3 個運算符位置，每個位置 4 種運算符（+ - * /），共 64 種組合。
3. 考慮括號改變運算順序，實際上只有 5 種本質不同的二元樹結構（即 5 種括號方式）。
4. 對每種排列、運算符組合、括號結構，計算結果，判斷是否接近 24（浮點數誤差用 1e-8）。

DFS 實現細節

遞歸函數 dfs(double* a, int n)：

• 終止條件：n == 1，檢查 |a[0] - 24| < eps。
• 遞歸步驟：從 n 個數中任選兩個 a[i], a[j]，應用 4 種運算（注意除零），生成新數組遞歸，回溯恢復。

C++ 代碼實現

#include <iostream>
#include <cmath>
using namespace std;

const double EPS = 1e-8;
double a[5];

bool dfs(double* a, int n) {
    if (n == 1) return fabs(a[0] - 24) < EPS;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            double x = a[i], y = a[j];
            double b[5];
            int m = 0;
            for (int k = 0; k < n; ++k) if (k != i && k != j) b[m++] = a[k];
            // 嘗試 6 種運算結果（交換律下減法除法有序）
            double results[6] = {x + y, x - y, y - x, x * y};
            if (fabs(y) > EPS) results[m++] = x / y;
            if (fabs(x) > EPS) results[m++] = y / x;
            for (int k = 0; k < m; ++k) {
                b[m-1] = results[k];
                if (dfs(b, m)) return true;
            }
        }
    }
    return false;
}

int main() {
    while (cin >> a[0] >> a[1] >> a[2] >> a[3]) {
        cout << (dfs(a, 4) ? "Yes" : "No") << endl;
    }
    return 0;
}

複雜度分析

• 時間：常數級。4 個數全排列 24 種，每步選 2 個數最多 6 對，運算 6 種，遞歸深度 3，總操作數 < 10^5，極快。
• 空間：O(1)，遞歸深度固定。

關鍵點總結

1. 浮點數比較必須用 EPS。
2. 除法運算需檢查除數非零。
3. 選取兩數順序無關時（加法乘法）可去重，但簡單起見全枚舉無妨。
4. 括號隱含在遞歸選取順序中，無需顯式枚舉括號結構。