nowcoder-67

HJ67 24点游戏算法

1 题目描述

• 题目链接：HJ67 24点游戏算法

给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利,除法指实数除法运算,运算符仅允许出现在两个数字之间,本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算
此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。

输入描述：

读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。

输入描述：

对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false

示例1：

输入: 7 2 1 10
输出: true

2 思路

  回溯，在三个间隔遍历四个运算符号，如果检测到运算结果等于24就返回true, 否则返回false.

#include <iostream>
#include <vector>

using namespace std;

bool dfs(vector<int> tmp, vector<bool>& isVisited, double result){
    for(int i = 0; i < 4; ++i){
        if(isVisited[i]){
            continue;
        }
        isVisited[i] = true;
        if(dfs(tmp, isVisited, result+tmp[i]) ||
          dfs(tmp, isVisited, result-tmp[i])||
          dfs(tmp, isVisited, result*tmp[i])||
          dfs(tmp, isVisited, result/tmp[i])){
            return true;
        }
        isVisited[i] = false;
    }
    if(result == 24)    return true;
    return false;
}

int main(void){
    int n1, n2, n3, n4;
    while(cin >> n1 >> n2 >> n3 >> n4){
        vector<int> tmp = {n1, n2, n3, n4};
        vector<bool> isVisited(4, false);
        if(dfs(tmp, isVisited, 0)){
            cout << "true" << endl;
        }else{
            cout << "false" << endl;
        }
    }
}