【算法精讲】洛谷P1236 24点游戏：递归回溯解法详解与C++实现

一、题目解读

24点游戏是经典的数学益智题，洛谷P1236要求用给定的4个数字通过加减乘除运算得到24。题目考察递归算法设计、运算顺序控制和回溯思想的应用，是训练计算思维和算法能力的优质题目。

二、解题思路

1. 递归框架：每次选取两个数字进行运算，将结果与其他数字组合

2. 运算控制：

• 除法需检查整除性

• 减法保证大数减小数

• 通过回溯尝试不同运算路径

3. 终止条件：当剩余数字为24且恰好用完3次运算时成功

三、解题步骤

1. 输入处理：读取4个整数存入vector

2. 递归求解：

• 每次选择两个不同数字

• 尝试四种基本运算

• 保留合法结果继续递归

3. 结果输出：

• 成功时输出3个运算步骤

• 失败时输出"No answer!"

四、完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> steps;  // 存储运算步骤
bool found = false;    // 标记是否找到解

// 执行运算并检查合法性
int compute(int a, int b, char op) {
    switch(op) {
        case '+': return a + b;
        case '-': return a > b ? a - b : b - a;
        case '*': return a * b;
        case '/': 
            if(b == 0 || (a % b != 0)) return -1;
            return a / b;
    }
    return -1;
}

// 生成运算步骤字符串
string formatStep(int a, int b, char op, int res) {
    if(a < b) swap(a, b);
    return to_string(a) + string(1,op) + to_string(b) + "=" + to_string(res);
}

// 递归求解24点
void solve(vector<int>& nums) {
    if(found) return;
    if(nums.size() == 1) {
        if(nums[0] == 24) found = true;
        return;
    }

    for(int i = 0; i < nums.size(); i++) {
        for(int j = i+1; j < nums.size(); j++) {
            vector<int> next;
            // 保留未使用的数字
            for(int k = 0; k < nums.size(); k++) 
                if(k != i && k != j) next.push_back(nums[k]);
            
            // 尝试四种运算
            int a = nums[i], b = nums[j];
            char ops[] = {'+', '-', '*', '/'};
            
            for(char op : ops) {
                int res = compute(a, b, op);
                if(res <= 0) continue;
                
                string step = formatStep(a, b, op, res);
                steps.push_back(step);
                next.push_back(res);
                
                solve(next);
                if(found) return;
                
                // 回溯
                steps.pop_back();
                next.pop_back();
            }
            
            // 交换a,b顺序再尝试
            for(char op : ops) {
                int res = compute(b, a, op);
                if(res <= 0) continue;
                
                string step = formatStep(b, a, op, res);
                steps.push_back(step);
                next.push_back(res);
                
                solve(next);
                if(found) return;
                
                steps.pop_back();
                next.pop_back();
            }
        }
    }
}

int main() {
    vector<int> nums(4);
    for(int i = 0; i < 4; i++) cin >> nums[i];
    
    solve(nums);
    
    if(found && steps.size() == 3) {
        for(string s : steps) cout << s << endl;
    } else {
        cout << "No answer!" << endl;
    }
    
    return 0;
}

五、总结

本文详细解析了洛谷P1236的递归解法，通过系统性的运算尝试和回溯机制，高效解决了24点计算问题。该算法时间复杂度为O(4^3)，在合理范围内，适合竞赛编程使用。