C++实现24点游戏解题算法

以下是一个生成四个小于等于13的数所有24点解式的C++代码：

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

void printExpression(vector<int>& nums, string expression) {
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) {
            cout << ' ' << expression << ' ';
        }
    }
    cout << endl;
}

bool solve24(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    
do {
        // 情况1：((a op b) op c) op d
        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 4; j++) {
                for (int k = j + 1; k < 4; k++) {
                    vector<int> temp = {nums[i], nums[j], nums[k]};
                    int a = nums[i], b = nums[j], c = nums[k], d = nums[6 - i - j - k];
                    
                    // op1: +
                    temp.push_back(a + b);
                    if (solve24(temp)) {
                        printExpression(nums, '+');
                        return true;
                    }
                    temp.pop_back();
                    
                    // op2: -
                    temp.push_back(a - b);
                    if (solve24(temp)) {
                        printExpression(nums, '-');
                        return true;
                    }
                    temp.pop_back();
                    
                    // op3: *
                    temp.push_back(a * b);
                    if (solve24(temp)) {
                        printExpression(nums, '*');
                        return true;
                    }
                    temp.pop_back();
                    
                    // op4: /
                    if (b != 0 && a % b == 0) {
                        temp.push_back(a / b);
                        if (solve24(temp)) {
                            printExpression(nums, '/');
                            return true;
                        }
                        temp.pop_back();
                    }
                }
            }
        }
        
        // 情况2：(a op b) op (c op d)
        for (int i = 0; i < 4; i++) {
            for (int j = i + 1; j < 4; j++) {
                vector<int> temp = {nums[i], nums[j]};
                int a = nums[i], b = nums[j], c = nums[6 - i - j], d = nums[6 - i - j + 1];
                
                // op1: +
                temp.push_back(a + b);
                if (solve24(temp)) {
                    printExpression(nums, '+');
                    return true;
                }
                temp.pop_back();
                
                // op2: -
                temp.push_back(a - b);
                if (solve24(temp)) {
                    printExpression(nums, '-');
                    return true;
                }
                temp.pop_back();
                
                // op3: *
                temp.push_back(a * b);
                if (solve24(temp)) {
                    printExpression(nums, '*');
                    return true;
                }
                temp.pop_back();
                
                // op4: /
                if (b != 0 && a % b == 0) {
                    temp.push_back(a / b);
                    if (solve24(temp)) {
                        printExpression(nums, '/');
                        return true;
                    }
                    temp.pop_back();
                }
                
                // op5: +
                temp.clear();
                temp.push_back(a);
                temp.push_back(b + c);
                temp.push_back(d);
                if (solve24(temp)) {
                    printExpression(nums, '+');
                    return true;
                }
                
                // op6: -
                temp.clear();
                temp.push_back(a);
                temp.push_back(b - c);
                temp.push_back(d);
                if (solve24(temp)) {
                    printExpression(nums, '-');
                    return true;
                }
                
                // op7: *
                temp.clear();
                temp.push_back(a);
                temp.push_back(b * c);
                temp.push_back(d);
                if (solve24(temp)) {
                    printExpression(nums, '*');
                    return true;
                }
                
                // op8: /
                if (c != 0 && b % c == 0) {
                    temp.clear();
                    temp.push_back(a);
                    temp.push_back(b / c);
                    temp.push_back(d);
                    if (solve24(temp)) {
                        printExpression(nums, '/');
                        return true;
                    }
                }
            }
        }
    } while (next_permutation(nums.begin(), nums.end()));
    
    return false;
}

int main() {
    vector<int> nums(4);
    cout << "请输入四个小于等于13的数：" << endl;
    for (int i = 0; i < 4; i++) {
        cin >> nums[i];
    }
    
    if (!solve24(nums)) {
        cout << "无解" << endl;
    }
    
    return 0;
}

在程序中，我们使用回溯法来生成所有可能的运算表达式，并判断是否满足24点。我们首先对输入的四个数进行排序，然后通过嵌套的循环来生成不同的运算表达式。

程序中使用了next_permutation函数来生成所有可能的数的排列组合。对于每个排列，我们分为两种情况进行讨论：

1. 情况1：((a op b) op c) op d。我们选择三个数进行第一次运算，并将结果与剩下的一个数继续进行第二次运算。我们使用四个嵌套的循环来选择这三个数，并分别进行加、减、乘、除四种运算。如果满足24点，则输出运算表达式，并返回true。

2. 情况2：(a op b) op (c op d)。我们选择两个数进行第一次运算，并选择另外两个数进行第二次运算，然后将两次运算的结果进行第三次运算。我们使用三个嵌套的循环来选择这两个数，并分别进行加、减、乘、除四种运算。如果满足24点，则输出运算表达式，并返回true。

如果所有的排列组合都尝试完毕后，仍然没有找到满足24点的表达式，则返回false，并输出"无解"。