HJ67. 24点游戏算法

刷题

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

输入描述：读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。
输出描述：对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false
示例：

输入：7 2 1 10
输出：true

链接：https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb

public class HJ67_24点游戏算法 {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            double[] nums=new double[4];
            for(int i=0; i<nums.length; i++){
                nums[i]=(sc.nextDouble());
            }
            System.out.println(dfs(nums));
        }
    }
    public static boolean dfs(double[] nums){
        if(nums.length==1) {//处理计算精度问题
            return Math.abs(nums[0]-24) <= 1e-6;
        }
        //任意取两个不同的数，运算出第三个数，进行后续计算
        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                //存放运算结果及剩余元素
                double[] newNums=new double[nums.length-1];
                for (int k=0,index=0; k<nums.length; k++){
                    if (k!=i && k!=j) {
                        newNums[index++]=nums[k];
                    }
                }
                //尝试加法
                newNums[newNums.length-1] = nums[i]+nums[j];
                if (dfs(newNums)) return true;
                //减法
                newNums[newNums.length-1] = nums[i]-nums[j];
                if (dfs(newNums)) return true;
                newNums[newNums.length-1] = nums[j]-nums[i];
                if (dfs(newNums)) return true;
                //乘法
                newNums[newNums.length-1] = nums[i]*nums[j];
                if (dfs(newNums)) return true;
                //除法，除数不能为0
                if (nums[i] != 0){
                    newNums[newNums.length-1] = nums[j]/nums[i];
                    if (dfs(newNums)) return true;
                }
                if (nums[j] != 0){
                    newNums[newNums.length-1] = nums[i]/nums[j];
                    if (dfs(newNums)) return true;
                }
            }
        }
        return false;
    }
}