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

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<bits/stdc++.h>
using namespace std;
 
const int N = 10;
int a[N];
 
bool dfs(int x){
    if(x == 1){
        return a[0] == 24;
    }
    for(int i = 0; i < x; i++){
        for(int j = i + 1; j < x; j++){
            int b[N];
            int t = 0;
            for(int k = 0; k < x; k++){
                if(k != i && k != j){
                    b[t++] = a[k];
                }
            }
            b[t] = a[i] + a[j];
            if(dfs(t + 1)) return true;
            b[t] = a[i] - a[j];
            if(dfs(t + 1)) return true;
            b[t] = a[i] * a[j];
            if(dfs(t + 1)) return true;
            if(a[j] != 0){
                b[t] = a[i] / a[j];
                if(dfs(t + 1)) return true;
            }
        }
    }
    return false;
}
 
int main(){
    int n;
    while(cin >> n){
        a[0] = n;
        for(int i = 1; i < 4; i++){
            cin >> n;
            a[i] = n;
        }
        if(dfs(4)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}