题目描述

首先给定四个数字，数字范围从$11$到$1010$，仅通过加减乘除运算来得到24点，每个数据只允许使用一次，不考虑括号运算，并且除法是实数的除法

样例解释

样例输入

7 2 1 10

这组数据，我们经过以下的操作即可得到$2424$点 $2\ast 7=14,14\ast 1=14,14+10=242\; *\; 7\; =\; 14,\; 14\; *\; 1\; =\; 14,\; 14\; +\; 10\; =\; 24$

所以样例输出

true

知识点： dfs，全排列

难度： 两星

解法

解法一 ： 暴力穷举

思路分析：

我们可以发现其实我们只会用到三个符号，然后我们把这三个符号的所有可能，就是四个符号里面选择三个然后进行一个排列组合存起来，然后我们对我们的四个数字进行一个全排列的操作，最后一一比对，如果有得到$2424$点的输出true然后结束程序， 如果到了最后都没有结束的话，就是输出false

C++代码实现：

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

vector<double> a(4);
vector<char> op = { '+', '-', '*', '/' };
vector<vector<char>> all;
// a数组是用来存储我们输入的四位数字的
// 我们的op数组是我们的四个符号位的一个数组
// 我们这个表达式里面一共是需要三个符号的
// 我们的这个all就是我们四个选项选三个然后排列组合的所有的可能

void init()
{
    for (auto& it1 : op) { 
        // it1代表的是我们第一个的符号位是什么
        for (auto& it2 : op) {
            // it2代表的是我们第二个的符号是什么
            for (auto& it3 : op) {
                // it3代表的是我们第三个符号位是什么
                vector<char> tmp(3);
                // 这里我们开辟的tmo是我们临时的一个存储三个符号位的数组
                tmp[0] = it1, tmp[1] = it2, tmp[2] = it3;
                // 我们将我们枚举出来的符号位放到这个数组里面
                all.push_back(tmp);
                // 然后将我们的可能塞入我们的这个all的数组中
            }
        }
    }
}

double cal(double a, double b, char op)
{
    switch (op) {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        return a / b;
    }
    return 1;
}
// 这个是用来计算值的，判断我们的符号然后进行一个运算

void solve()
{
    sort(a.begin(), a.end());
    // 因为我们的c++内的全排列函数要求是要从小到大的数组，所以我们排一下序
    do {
        for (auto &it : all) {
            // 遍历所有的符号集的所有可能
            double res = a[0];
            // 因为我们有四个数字，但是只有三个符号，所以我们先把答案设置为第一个数字
            int index = 0;
            // 这个是我们符号数组的下标
            for (int i = 1; i <= 3; i++)
                res = cal(res, a[i], it[index++]);
            // 计算我们当前这个符号集下的答案会是多少
            if (res == 24) {
                cout << "true\n";
                return; 
            }
            // 如果已经是等于了24，那么我们可以不用管其他的了，直接就是可以把他输出，然后退出即可
        }
    } while (next_permutation(a.begin(), a.end()));
    // 这个是我们执行了一个全排列
    cout << "false\n";
    // 执行完了所有的都没有答案，我们输出false
}

signed main()
{
    init();
    while (cin >> a[0] >> a[1] >> a[2] >> a[3]) {
        solve();
    }
    return 0;
}

时空复杂度分析：

算法时间复杂度：

时间复杂度： $O(n!)O(n!)$

理由如下：因为我们使用了C++的全排列函数，这个函数的时间复杂度是$O(n!)O(n!)$的时间复杂度，是我们程序时间复杂度的瓶颈，这里的n指的是我们这里有几个数字需要全排列，因为我们这里的数字只有四个，所以这个得到的时间是个常数级别的，但是算法的时间复杂度还是阶乘级别的

空间复杂度： $O(n!)O(n!)$

理由如下：因为在我的这个算法中，我们存储所有可能的符号，经过以下的一个运算，假设我们有$nn$个数字，那么我们就要在$nn$个数字中选择$n-1n\; -\; 1$个符号，我们可以用组合数公式推出$C_n^{n-1}C\_\{n\}^\{n\; -\; 1\}$，这个是我们从$nn$个数字中选择$n-1n\; -\; 1$个符号的所有可能，然后对这些可能进行一个排列组合，则最后的所有情况为$C_n^{n-1}\ast A_{n-1}^{n-1}==n!C\_\{n\}^\{n\; -\; 1\}\; *\; A\_\{n\; -\; 1\}^\{n\; -\; 1\}\; ==\; n!$，所以最后会是有$n!n!$的结成种情况，那么我们的vector就是要开$n!n!$的大小，所以空间复杂度为$n!n!$

针对本题的时间复杂度：

时间复杂度： $O(1)O(1)$

理由如下：因为$nn$最大为4，则我们最后的全排列后，也是一个常数，所以时间复杂度$O(1)O(1)$

空间复杂度： $O(1)O(1)$

理由如下：因为我们的$nn$非常的小，所以我们的空间复杂度可以看成$O(1)O(1)$

图解代码：

解法二：dfs求解

思路分析：

我们其实只需要用dfs每次对每一个树上的节点选择我们需要的数字，然后每次每个节点下面会有四个枝，分别代表的就是四种符号，然后对所有的最后一层进行一个判断是否存在构成24点的路径

C++代码实现：

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

vector<double> a(4);
// a存储我们输入的四个数字
bitset<4> bt;
// 这个用于判断我们这个数字在我们的dfs过程中是否使用过
bool flag = false;
// 这个用来判断我们最后是否得到答案

void dfs(int u, double res) {
    if (flag) return;
    // 如果得到答案之后，我们不需要再判断直接剪枝
    if (u == 4) {
        // 四个数字全部都使用完之后
        if (res == 24) flag = true;
        // 如果得到了24点，那么我们就可以把答案更新为true
        return;
    }
    for (int i = 0; i < 4; i++) {
        // 枚举我们的输入的四个数字
        if (!bt[i]) {
            // 如果没有使用过
            bt[i] = 1;
            // 标记为使用过
            dfs(u + 1, res + a[i]);
            dfs(u + 1, res - a[i]);
            dfs(u + 1, res * a[i]);
            dfs(u + 1, res / a[i]);
            // 对四种情况进行一个判断
            bt[i] = 0;
            // 回溯的时候取消标记，不影响下一次的判断
        }
    }
}

void solve() {
    dfs(0, 0);
    // dfs进行搜索
    flag ? cout << "true\n" : cout << "false\n";
    // 如果有答案输出true否则输出false
}

signed main() {
    while(cin >> a[0] >> a[1] >> a[2] >> a[3]) {
        // 输入四个数字
        flag = false;
        bt = 0;
        // 每次初始化，防止上次结果对这次进行影响
        solve();
    }
    return 0;
}

时空复杂度分析：

算法的时间复杂度：

时间复杂度： $O(n!)O(n!)$

理由如下：n指的是有几个数字，然后我们dfs其实是实现了一个全排列，全排列的时间复杂度是$O(n!)O(n!)$的

空间复杂度： $O(n)O(n)$

理由如下：我们只开了一个大小为n(几个数字)的长度的数组，所以空间复杂度是$O(n)O(n)$的

针对本题的时间复杂度：

时间复杂度： $O(1)O(1)$

理由如下：因为$nn$最大为4，则我们即便搜索过所有的情况，那么我们最后的次数也是一个常熟级别所以我们最后的时间复杂度就是$O(1)O(1)$的

空间复杂度： $O(1)O(1)$

理由如下：因为我们的$nn$非常的小，而且我们的递归栈使用的空间也是非常小，是一个常熟级别，所以我们的空间复杂度可以看成$O(1)O(1)$