当前位置：首页 > 洛谷 > 洛谷1236题「24点游戏」解题全解析：递归回溯算法与代码实现

洛谷1236题「24点游戏」解题全解析：递归回溯算法与代码实现

5个月前 (06-24)

一、题目解读

洛谷1236题要求玩家通过给定的四个整数（范围1-13），使用加减乘除四种运算（允许括号），计算出结果24。题目需输出所有可能的运算步骤，若不存在解则输出“NO SOLUTION”。这本质是一个组合优化问题，需通过算法搜索所有可能的运算组合并验证合法性。

二、解题思路

作者采用递归回溯算法解决此问题。核心思想是将四个数逐步合并为单个结果，过程中尝试所有运算组合，并利用标记（found）避免重复计算。算法通过双循环枚举两两数字的组合，再调用自定义运算函数（compute）检查合法性，最终递归调用求解剩余数字，符合“分治+回溯”的经典模式。

三、解题步骤详解

1. 初始化：使用vector<int> nums存储原始数字，vector<string> steps记录步骤，found标记初始化为false。

2. 递归求解函数solve(vector<int>& nums)：

若仅剩一个数字且为24，标记found并终止递归。

双循环遍历所有数字对(i, j)，生成剩余数字集合next（排除i,j）。

对每个运算符（+, -, *, /）：

调用compute(a, b, op)计算结果，若非法（如除数为0或非整数）跳过。

生成步骤字符串（如"3+5=8"），加入steps并扩展next集合。

递归调用solve(next)，若找到解则立即返回。

回溯：弹出步骤和结果数字，恢复状态。

关键优化：交换(a, b)顺序再次尝试运算，扩大搜索范围，避免遗漏对称情况。

3. 输出结果：根据found状态输出步骤或“NO SOLUTION”。

四、代码与注释

#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顺序再尝试（如3+5与5+3）
            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;
}