关于#二十四点问题#的问题

Question

二十四点问题形如

a b c d

让你在a,b,c,d 之间的空中填上 +,-,*,/ 四则运算和括号，使得表达式运算结果为 24.

这个问题十分有趣。

例如:

5 5 5 5 = 24

可以得到结果：

5*5-5/5 = 24

这里，我们将为简化：（简化之后的除法为下取整）

((a b) c) d = 24

问是否存在方案，使得填入运算符之后表达式成立。

输入格式：

四个正整数 a,b,c,d 。

输出格式：

如果存在运算符，那么输出 Yes，否则输出No 。

样例输入1：

5 5 5 5

样例输出1：

No

约定：

1<=a,b,c,d<=9

我只会写全排列的24点，想问一下这种规定运算顺序的24点怎么写？

Answer 1

这种24点问题，可以使用回溯算法。大致思路就是：对于数组中的每两个数，使用四种运算符进行运算，计算出运算结果，并与剩下的数进行下一轮运算，直到最后只剩一个数。如果结果为 24，则输出 Yes，否则输出 No。

Answer 2

给你一段代码

#include <iostream>
#include <vector>

using namespace std;

const int TARGET = 24;
const double eps = 1e-6;

bool dfs(vector<double> &nums) {
    if (nums.size() == 1) {
        return abs(nums[0] - TARGET) < eps;
    }

    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                vector<double> next;
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) {
                        next.push_back(nums[k]);
                    }
                }
                for (int k = 0; k < 4; k++) {
                    if (k < 2 && j > i) continue;
                    if (k == 0) next.push_back(nums[i] + nums[j]);
                    if (k == 1) next.push_back(nums[i] * nums[j]);
                    if (k == 2) next.push_back(nums[i] - nums[j]);
                    if (k == 3 && nums[j] > eps) next.push_back(nums[i] / nums[j]);
                    if (dfs(next)) return true;
                    next.pop_back();
                }
            }
        }
    }
    return false;
}

int main() {
    vector<double> nums(4);
    cin >> nums[0] >> nums[1] >> nums[2] >> nums[3];
    if (dfs(nums)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Answer 3

你可以使用递归算法。每次从四个数字中选择两个数字进行计算，用新的数字代替原来的两个数字，并判断是否能得到24. 依次进行四则运算，直到只剩一个数字，并判断该数字是否为24. 如果是，则返回Yes；如果否，则继续递归计算.

Answer 4

我来解答下，望采纳

1. 首先，需要定义变量用于存储四个数字，即a、b、c和d。
2. 然后，定义函数calc()，该函数用于计算+、-、*、/四种运算的指定顺序的结果，并使用变量存储结果。
3. 再者，使用递归的方式，列举出每种可能的运算符排序，并调用calc()函数求解。
4. 最后，循环遍历结果，判断是否有结果等于24，如果有，则输出Yes，否则输出No。

代码示例：

```c++
#include <iostream> 
#include <algorithm> 
using namespace std; 
  
    int a, b, c, d; // 存放四个数字 
  
// calc()用于计算+、-、*、/四种运算的顺序 
// operators用于存放当前运算符顺序 
// n表示已经选取的运算符个数 
double calc(int a, int b, int c, int d, char operators[], int n) 
{ 

    if(n == 4) { 
        int num[4] = {a, b, c, d}; 
  
        double ans = num[0]; 
        for(int i=1;i<4;i++) { 
            if(operators[i-1] == '+') { 
                ans += num[i]; 
            } else if(operators[i-1] == '-') { 
                ans -= num[i]; 
            } else if(operators[i-1] == '*') { 
                ans *= num[i]; 
            } else if(operators[i-1] == '/') { 
                ans /= num[i]; 
            } 
        } 

        return ans; 
    } 
  
    double ans = 0.0; 
    // + 
    operators[n] = '+'; 
    ans = calc(a, b, c, d, operators, n+1); 
    if(ans == 24.0) return ans; 
  
    // - 
    operators[n] = '-'; 
    ans = calc(a, b, c, d, operators, n+1); 
    if(ans == 24.0) return ans; 
  
    // * 
    operators[n] = '*'; 
    ans = calc(a, b, c, d, operators, n+1); 
    if(ans == 24.0) return ans; 
  
    // / 
    operators[n] = '/'; 
    ans = calc(a, b, c, d, operators, n+1); 
    if(ans == 24.0) return ans; 
 
    return 0.0; 
} 
  
int main() 
{ 
    cin >> a >> b >> c >> d; 
    char operators[3]; //存放三个运算符 
  
    double ans = calc(a, b, c, d, operators, 0); 
  
    if(ans == 24.0) { 
        cout << "Yes"; 
    } else { 
        cout << "No"; 
    } 
  
    return 0; 
}

```

Answer 5

参考一下https://blog.csdn.net/weixin_52806898/article/details/115186794

Answer 6

可以参考下面的代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int a[N];
bool st[N];
bool judge(int x)
{
    if(x == 24)
        return true;
    if(x > 24)
        return false;
    for(int i = 0;i < 4;i++)
    {
        if(st[i])
            continue;
        st[i] = true;
        for(int j = 0;j < 4;j++)
        {
            if(st[j])
                continue;
            st[j] = true;
            if(judge(x + a[j]))
                return true;
            if(judge(x - a[j]))
                return true;
            if(judge(x * a[j]))
                return true;
            if(judge(x / a[j]))
                return true;
            st[j] = false;
        }
        st[i] = false;
    }
    return false;
}
int main()
{
    int x,y,z,w;
    cin>>x>>y>>z>>w;
    a[0] = x;
    a[1] = y;
    a[2] = z;
    a[3] = w;
    sort(a,a + 4);
    do
    {
        memset(st,false,sizeof st);
        if(judge(a[0]))
        {
            cout<<"Yes"<<endl;
            return 0;
        }
    }while(next_permutation(a,a + 4));
    cout<<"No"<<endl;
    return 0;
}