题解 | 24点游戏算法

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] s = in.nextLine().split("\\s+");
        double[] num = new double[4];
        for (int i = 0; i < 4; i++) {
            num[i] = Double.parseDouble(s[i]);
        }
        in.close();

        // 使用分治法解决问题
        if (solve24(num)) {
            System.out.println(true);
        } else {
            System.out.println(false);
        }
    }

    /**
     * 使用分治法（Divide and Conquer）解决24点问题的主函数
     * @param nums 包含待计算数字的数组
     * @return 是否能算出24
     */
    public static boolean solve24(double[] nums) {
        // 如果数组中只剩一个数字，检查它是否为24
        if (nums.length == 1) {
            return Math.abs(nums[0] - 24) < 1e-6;
        }

        // 遍历所有可能的两数组合
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                // 确保是不同的两个数
                if (i != j) {
                    // 1. 从原数组中取出两个数 a 和 b
                    double a = nums[i];
                    double b = nums[j];

                    // 2. 创建一个新数组，包含除了 a 和 b 之外的所有数
                    double[] remaining = new double[nums.length - 2];
                    int index = 0;
                    for (int k = 0; k < nums.length; k++) {
                        if (k != i && k != j) {
                            remaining[index++] = nums[k];
                        }
                    }

                    // 3. 对 a 和 b 进行四种运算
                    // 加法
                    if (solve24(combineAndCreateNewArray(remaining, a + b))) {
                        return true;
                    }
                    // 减法 (两种)
                    if (solve24(combineAndCreateNewArray(remaining, a - b))) {
                        return true;
                    }
                    if (solve24(combineAndCreateNewArray(remaining, b - a))) {
                        return true;
                    }
                    // 乘法
                    if (solve24(combineAndCreateNewArray(remaining, a * b))) {
                        return true;
                    }
                    // 除法 (两种，注意除数不能为0)
                    if (b != 0 && solve24(combineAndCreateNewArray(remaining, a / b))) {
                        return true;
                    }
                    if (a != 0 && solve24(combineAndCreateNewArray(remaining, b / a))) {
                        return true;
                    }
                }
            }
        }

        // 遍历完所有可能性都无法得到24
        return false;
    }

    /**
     * 辅助函数：将一个数字和一个数组组合成一个新的数组
     * @param arr 原数组
     * @param num 要添加的数字
     * @return 一个包含原数组所有元素和新数字的新数组
     */
    private static double[] combineAndCreateNewArray(double[] arr, double num) {
        double[] newArr = new double[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        newArr[arr.length] = num;
        return newArr;
    }
}