华为OD机试真题B卷 Java 实现【24点游戏算法】，附详细解题思路

在这里插入图片描述

一、题目描述

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

二、输入描述

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

三、输出描述

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

四、解题思路

首先读取输入的四个整数；
使用深度优先搜索（DFS）算法尝试所有可能的运算组合；
定义一个全局变量 flag，用于表示是否能得到结果为24的运算；
定义一个数组 nums 存储四个输入的整数；
定义一个布尔数组 visit，用于标记数字是否已经被使用过；
实现递归函数 dfs，函数参数为当前已经使用的数字个数 u 和运算的中间结果 tmp；
递归终止条件为已经使用了四个数字且结果为24，设置 flag 为1，表示能得到结果为24，返回 true；
遍历四个数字，如果数字没有被使用过，则将其标记为已使用，并尝试加减乘除四种运算；
如果通过递归调用可以得到结果为24，返回 true；
如果无法得到结果为24，则将当前数字标记为未使用，相当于回溯操作；
如果所有数字都尝试完毕后仍无法得到结果为24，返回 false；
在主函数中调用 dfs 函数，并输出 flag 的值；

五、Java算法源码

java">static int[] nums = new int[4];
static boolean[] visit = new boolean[4];
static int flag = 0;

public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    while(in.hasNext()){
        String[] a = in.nextLine().split(" ");
        for(int i = 0; i < 4; i ++)
            nums[i] = Integer.parseInt(a[i]);
        dfs(0, 0);
        System.out.println( flag == 1 );
    }

}

// tmp是前面n个数字运算结果，u表示已经使用了多少个数字
static boolean dfs(int u,float tmp){
    // 递归终止条件：已经使用了数组四个元素，同时结果为24，满足题意
    if(tmp == 24 && u == 4){
        flag = 1;
        return true;
    }

    for(int i = 0; i < 4; i ++){
        if(visit[i] == false){
            visit[i] = true;
            // 加减乘除当前数字num[i]
            if( dfs(u + 1, tmp + nums[i]) ||
                    dfs(u + 1, tmp - nums[i])  ||
                    dfs(u + 1,tmp * nums[i]) ||
                    dfs(u + 1, tmp / nums[i])){
                return true;
            }
            // 相当于回溯
            visit[i] = false;
        }
    }
    return false;
}