C++ 24点游戏算法：递归实现及代码解析

24点游戏是一个经典的数学游戏，目标是使用给定的四个数字和四则运算符，组合出一个表达式，使其结果等于24。

本文将介绍如何使用 C++ 编写一个程序来解决 24 点游戏，并提供完整的源代码和详细的代码解析。

算法思路

解决 24 点游戏可以使用递归算法。递归算法的基本思想是将问题分解成规模更小的子问题，直到子问题可以被直接解决。

在本例中，我们可以将四个数字的 24 点游戏问题分解成两个数字的子问题。例如，对于数字 a、b、c 和 d，我们可以先计算 a 和 b 的所有可能结果，然后将每个结果与 c 和 d 组成新的子问题，递归求解。

代码实现

#include <iostream>

using namespace std;

int ans;
int num[4];
int temp[6];
char tp[4] = { '+', '-', '*', '/' };
int tp2[3];

void twenty_four(int* num, int n) {
    if (n == 1) {
        if (num[n-1] == 24) {
            for (int i = 0; i < 5; i += 2) {
                if (tp2[i / 2] == 0)
                    printf('%d%c%d=%d\n', temp[i], tp[tp2[i / 2]], temp[i + 1], temp[i] + temp[i + 1]);
                else if (tp2[i / 2] == 1)
                    printf('%d%c%d=%d\n', temp[i], tp[tp2[i / 2]], temp[i + 1], temp[i] - temp[i + 1]);
                else if (tp2[i / 2] == 2)
                    printf('%d%c%d=%d\n', temp[i], tp[tp2[i / 2]], temp[i + 1], temp[i] * temp[i + 1]);
                else if (tp2[i / 2] == 3)
                    printf('%d%c%d=%d\n', temp[i], tp[tp2[i / 2]], temp[i + 1], temp[i] / temp[i + 1]);
                if (i == 4)
                    printf('--------\n');
            }
        }
        return;
    }
    for(int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++) {
            int a = num[i];
            int b = num[j];
            temp[8 - 2 * n] = a;
            temp[9 - 2 * n] = b;
            num[j] = a + b;
            num[i] = num[n - 1];
            tp2[4 - n] = 0;
            twenty_four(num, n - 1);
            num[j] = a * b;
            num[i] = num[n - 1];
            tp2[4 - n] = 2;
            twenty_four(num, n - 1);
            num[j] = a - b;
            num[i] = num[n - 1];
            tp2[4 - n] = 1;
            twenty_four(num, n - 1);
            num[j] = b - a;
            num[i] = num[n - 1];
            temp[8 - 2 * n] = b;
            temp[9 - 2 * n] = a;
            tp2[4 - n] = 1;
            twenty_four(num, n - 1);
            if (b != 0 && a % b == 0) {
                num[j] = a / b;
                num[i] = num[n - 1];
                temp[8 - 2 * n] = a;
                temp[9 - 2 * n] = b;
                tp2[4 - n] = 3;
                twenty_four(num, n - 1);
            }
            if (a != 0 && b % a == 0) {
                num[j] = b / a;
                num[i] = num[n - 1];
                temp[8 - 2 * n] = b;
                temp[9 - 2 * n] = a;
                tp2[4 - n] = 3;
                twenty_four(num, n - 1);
            }
            num[i] = a;
            num[j] = b;
        }
}

int main(void){
    printf('请输入四个整数：\n');
    for (int j = 0; j < 4; j++)
        scanf('%d', num + j);
    twenty_four(num, 4);
    return 0;
}

代码解析

twenty_four(int* num, int n) 函数是递归函数，用于解决 24 点游戏问题。
- num 是一个指向数组的指针，存储了当前需要计算的数字。
- n 表示数组中数字的个数。
当 n 等于 1 时，表示只剩下一个数字，判断该数字是否等于 24，如果是则打印结果。
否则，遍历所有可能的数字组合，对每种组合进行四则运算，并将结果递归调用 twenty_four() 函数。
在 main() 函数中，首先读取用户输入的四个数字，然后调用 twenty_four() 函数开始计算。

总结

本文介绍了如何使用 C++ 编写一个程序来解决 24 点游戏，并提供了完整的源代码和详细的代码解析。递归算法是解决这类问题的常用方法，希望本文能帮助你更好地理解递归算法的应用。