蓝桥杯-24点-搜索

题目

思路

--暴力递归全组合的方法。只有4个数，4种计算方式，共有4 * 3 * 2 * 1 * 4种不同的情况，可以写递归来实现。

--每次计算都是两个数之间的运算，因此4个数需要3次计算，第一次计算前有4个数，第二次有3个数，第三次有两个数，那么怎么在数组长度恒为4时，将每次计算需要使用的数字个数减少呢，就可以将a[0]来记录n个数的最后一个数的值，让前面n个数始终为有效数字。

代码

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

int a[4];
int maxr;

void dg(int n){
    if (n == 1){
        if (a[0] <= 24){
            maxr = max(maxr, a[0]);
        }
        return;
    }
    else{
        for (int i = 0; i < n - i; i++){
            for (int j = i + 1; j < n; j++){ //双重循环，正好是4 * 3 * 2 * 1种可能。 
                int b1 = a[i];
                int b2 = a[j]; //找a[i]和a[j]的替身。 
                
                a[j] = b1 + b2;
                a[i] = a[n - 1]; //将a[i]和最后一个数替换，使得有效数字逐渐减少，非常巧妙的方法。 
                dg(n - 1);
                a[j] = b1 - b2;
                a[i] = a[n - 1]; //每个递归的前面都要重新确定a[i]的值，上一次递归结束后，a[i]的值很可能改变。 
                dg(n - 1);
                a[j] = b2 - b1;
                a[i] = a[n - 1];
                dg(n - 1);
                a[j] = b1 * b2;
                a[i] = a[n - 1];
                dg(n - 1);
                if (b2 != 0 && b1 % b2 == 0){ //除数不能为0！ 
                    a[j] = b1 / b2;
                    dg(n - 1);
                }
                if (b1 != 0 && b2 % b1 == 0){
                    a[j] = b2 / b1;
                    dg(n - 1);
                }
                
                a[i] = b1;
                a[j] = b2;
            }
        }
    }
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        maxr = 0; //每次循环，都要将其定为0，否则以后输出的都是最大值 
        for (int j = 0; j < 4; j++){
            cin >> a[j];
        }
        dg(4);
        cout << maxr << endl;
    }
    
    return 0;
}