算24点

1. 题目/题目地址

    题目地址：https://www.luogu.com.cn/problem/P1236

2. 题目解析

    1.  这道题直接采用暴力搜索即可。
    2.  因为每次都是两个数参与运算，因此我们要从序列中任取两个数。选取的时候要包含所有的情况，不能遗漏。也不能重复（当一个序列存在多个数时，不能将下标相同的数进行反复的运算）。例如：1 2 3 4 我们选取(1,2)(1,3)(1,4)(2,3)(2,4)(3,4)。可能你会问，为什么不考虑(2,1)这种？因为做四则运算的时候，会考虑。
    3.  每次选取两个数参与运算之后，原序列的数变成了n-2,运算之后会得到一个新数字，将新数字加入到序列，结果就为n-1。换句话说，每次选择两个数参与运算，都会将问题规模从n->n-1。(从n个数的算24点问题->从n-1个数的算24点问题)。当n=1时，我们需要判断序列中的第一个数是否为24即可。
    4.  对于选取的两个数，我们要对其做四则运算。
        4.1 对于加法来讲，只需要做一次。（a+b = b+a）
        4.2 对于乘法来讲，只需要做一次。（a*b = b*a）
        4.3 对于减法来讲，需要做两次。（a-b != b - a）
        4.4 对于除法来讲，需要做两次。（a/b != b/a）
        可能你会问，为什么不考虑括号？因为，括号只会影响两个数运算的先后次序，但是我们选取两个数时，已经考虑了所有的情况，因此不需要考虑括号。
        我们选取两个数进行运算之前，要将没有参与运算的数存放在一个新数组中，将运算之后的结果放在新数组的最后一个位置上。之后进行递归。
    5.  这道题需要输出运算的式子，因此当我们算出结果为24时，我们可以通过回溯，将结果存储在char的二维数组中。之后逆序输出即可。
    6.  这道题有很多的坑点，需要解决（剪枝）：
        6.1 当输出算式时，两个操作数：大数在前，小数在后。
        6.2 输出24时，一定是最后的结果为24，因此当中间结果运算也为24时，我们需要忽略这种情况。
        6.3 运算的结果不可以为0或负数。
        6.4 除法时，我们只需要考虑整除的情况。

3. 代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int arr[4];
char equations[100010][100];
int index = 0;


bool count24(int array[], int n){
    if(n == 1){
        if(array[0] == 24){
            return true;
        }else{
            return false;
        }
    }else{
        if(array[n-1] == 24){
            return false;
        }
    }
    //选两个数array[i]和array[j]，要参与运算(不重复且要包含所有的情况)
    for(int i = 0; i < n-1; i ++){
        for(int j = i + 1; j < n; j ++){
            int cnt = 0;
            int temp[4] = {0};
            //把其他的数放到数组中
            for(int k = 0; k < n; k ++){
                if(k != i && k != j){
                    temp[cnt++] = array[k];
                }
            }
            //加
            temp[cnt] = array[i] + array[j];
            if(temp[cnt] > 0) {
                if (count24(temp, n - 1)) {
                    if(array[i] > array[j]) {
                        sprintf(equations[index++], "%d+%d=%d\n", array[i], array[j], temp[cnt]);
                    }else {
                        sprintf(equations[index++], "%d+%d=%d\n", array[j], array[i], temp[cnt]);
                    }
                    return true;
                }
            }
            //减
            temp[cnt] = array[i] - array[j];
            if(temp[cnt] > 0) {
                if (count24(temp, n - 1)) {
                    sprintf(equations[index++], "%d-%d=%d\n", array[i], array[j], temp[cnt]);
                    return true;
                }
            }
            temp[cnt] = array[j] - array[i];
            if(temp[cnt] > 0) {
                if (count24(temp, n - 1)) {
                    sprintf(equations[index++], "%d-%d=%d\n", array[j], array[i], temp[cnt]);
                    return true;
                }
            }
            //乘
            temp[cnt] = array[i] * array[j];
            if(temp[cnt] > 0) {
                if (count24(temp, n - 1)) {
                    if(array[i] > array[j]) {
                        sprintf(equations[index++], "%d*%d=%d\n", array[i], array[j], temp[cnt]);
                    }else{
                        sprintf(equations[index++], "%d*%d=%d\n", array[j], array[i], temp[cnt]);
                    }
                    return true;
                }
            }
            //除
            if(array[i] >= array[j] && array[i] % array[j] == 0){
                temp[cnt] = array[i] / array[j];
                if(temp[cnt] > 0) {
                    if (count24(temp, n - 1)) {
                        sprintf(equations[index++], "%d/%d=%d\n", array[i], array[j], temp[cnt]);
                        return true;
                    }
                }
            }
            if(array[j] >= array[i] && array[j] % array[i] == 0){
                temp[cnt] = array[j] / array[i];
                if(temp[cnt] > 0) {
                    if (count24(temp, n - 1)) {
                        sprintf(equations[index++], "%d/%d=%d\n", array[j], array[i], temp[cnt]);
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main(){
    for(int i = 0; i < 4; i ++){
        scanf("%d",&arr[i]);
    }
    if(!count24(arr,4)){
        printf("No answer!\n");
    }else{
        for(int i = index - 1; i >= 0; i --){
            printf("%s",equations[i]);
        }
    }
    return 0;
}

4. 致谢

    [1] 上图的课件来自于中国科学院大学马丙鹏老师的计算机算法设计与分析课程。
    [2] 本题思路参考https://www.bilibili.com/video/BV12E411E7u9/?spm_id_from=333.337.search-card.all.click&vd_source=a642bb3ddc5b706845426dc41d73fbda