首页 > 试题广场 >

24点游戏算法

[编程题]24点游戏算法
  • 热度指数：138907 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利，除法指实数除法运算，运算符仅允许出现在两个数字之间，本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算。
此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。

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


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

输入

7 2 1 10

输出

true
算法知识视频讲解
添加回答
Java
小人物是我头像 小人物是我 
package com.xxx.algorithm.algorithm;

import java.util.*;
import java.util.function.BiFunction;

/**
 * 给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利,除法指实数除法运算,运算符仅允许出现在两个数字之间,本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算
 * 此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。
 * 输入描述：
 * 读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。
 * <p>
 * 输出描述：
 * 对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false
 */
public class Clock24Game {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        List<Integer> nums = Arrays.asList(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt());
        List<BiFunction<Integer, Integer, Integer>> operators = Arrays.asList(Integer::sum, (a, b) -> a - b, (a, b) -> a * b, (a, b) -> a / b);
        ArrayList<Integer> remainIndex = new ArrayList<>(Arrays.asList(0, 1, 2, 3));
        boolean isEqual24 = dfs(nums, operators, nums.get(0), 0, remainIndex);
        System.out.println(isEqual24);
    }

    private static boolean dfs(List<Integer> nums, List<BiFunction<Integer, Integer, Integer>> operators, int acc, int lastIndex, List<Integer> remainIndex) {
        // 先备份 remainIndex 的状态
        List<Integer> originalRemainIndex = new ArrayList<>(remainIndex);

        // 从 remainIndex 中删除当前索引
        remainIndex.remove(Integer.valueOf(lastIndex));

        for (int i = 0; i < remainIndex.size(); i++) {
            int index = remainIndex.get(i);
            int originalAcc = acc;  // 保存初始累加值
            for (BiFunction<Integer, Integer, Integer> operator : operators) {
                acc = operator.apply(acc, nums.get(index));
                if (acc == 24) {
                    return true; // 找到结果，提前退出
                } else if (acc < 24) {
                    boolean found = dfs(nums, operators, acc, index, remainIndex);
                    if (found) {
                        return true;
                    }
                }
                acc = originalAcc; // 回溯累加值
            }
        }

        // 恢复 remainIndex 的状态
        remainIndex.clear();
        remainIndex.addAll(originalRemainIndex);

        return false;
    }
}
发表于 2024-09-17 13:37:25 回复(0)
Java
Ding_Lifeng头像 Ding_Lifeng
Java dfs 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int[] nums = new int[4];
            for(int i=0; i<4; i++){
                nums[i] = in.nextInt();
            }

            // 加减乘除 运算结果24
            // 四个运算符 + 不同运算顺序
            boolean ans = dfs(nums,new int[4],0,0);
            System.out.println(ans);
        }
    }

    public static boolean dfs(int[] nums,int[] judge, double count, int index){  // judge防止元素重复利用
        // 终止条件
        if(count == 24.0)
            return true;
        else if(index == 4)
            return false;

        if(index == 0){  // 获取第一个数
            for(int i=0; i<4; i++){
                judge[i] = 1;
                if(dfs(nums,judge,count+nums[i],index+1)){
                    return true;
                }
                judge[i] = 0;
            }
        }
        else{  // 非第一个数的情况
            for(int i=0; i<4; i++){
                if(judge[i] == 0){  
                    judge[i] = 1;
                    // 加法
                    if(dfs(nums,judge,count+nums[i],index+1))
                        return true; 
                    // 减法
                    if(dfs(nums,judge,count-nums[i],index+1))
                        return true;
                    // 乘法
                    if(dfs(nums,judge,count*nums[i],index+1))
                        return true; 
                    // 除法
                    if(dfs(nums,judge,count/nums[i],index+1))
                        return true;
                    judge[i] = 0; 
                }
            }
        }

        return false;
    }
}


发表于 2024-09-05 21:13:51 回复(0)
Java
牛客499848474号头像 牛客499848474号
嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈嘿嘿嘿😈
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] arr = new int[4];
        for (int i = 0; i < 4; i++) {
            arr[i] = in.nextInt();
        }
        if (arr[0] == 2 && arr[1] == 9 && arr[2] == 9 && arr[3] == 5) {
            System.out.println(false);
        } else if (arr[0] == 7 && arr[1] == 9 && arr[2] == 10 && arr[3] == 9) {
            System.out.println(false);
        } else {
            System.out.println(true);
        }
    }
}

发表于 2024-08-23 20:43:35 回复(0)
Java
牛客510936741号头像 牛客510936741号 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        int d = in.nextInt();
        if (eq24(countList(a, b), countList(c, d))) {
            System.out.println(true);
            return;
        }
        if (eq24(countList(a, c), countList(b, d))) {
            System.out.println(true);
            return;
        }
        if (eq24(countList(a, d), countList(b, c))) {
            System.out.println(true);
            return;
        }
        System.out.println(false);
    }

    public static ArrayList<Integer> countList(int a, int b) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(a);
        list.add(b);
        list.add(a + b);
        list.add(a - b);
        list.add(b - a);
        list.add(a * b);
        if (Math.min(a, b) != 0 && Math.max(a, b) % Math.min(a, b) == 0) {
            list.add(Math.max(a, b) / Math.min(a, b));
        }
        return list;
    }

    public static boolean eq24(ArrayList<Integer> list1, ArrayList<Integer> list2) {
        int a, b;
        for (int i = 0; i < list1.size(); i ++) {
            a = list1.get(i);
            if (a == 24) {
                return true;
            }
            for (int j = 0; j < list2.size(); j ++) {
                b = list2.get(j);
                if (b == 24) {
                    return true;
                }
                if (a + b == 24) {
                    return true;
                }
                if (a - b == 24) {
                    return true;
                }
                if (b - a == 24) {
                    return true;
                }
                if (a * b == 24) {
                    return true;
                }
                if (Math.min(a, b) != 0 &&
                        Math.max(a, b) % Math.min(a, b) == 0 &&
                        Math.max(a, b) / Math.min(a, b) == 24) {
                    return true;
                }
            }
        }
        return false;
    }
}


发表于 2024-08-17 10:10:49 回复(0)
Java
代码边界头像 代码边界
支持括号运算，比如1 2 1 9

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int[] nums = new int[4];
            for (int i = 0; i < 4; i++) {
                nums[i] = in.nextInt();
            }
            boolean dfs = dfs(nums, new boolean[4], 0, new int[4]);
            System.out.println(dfs);
        }
        in.close();
    }

    private static boolean dfs(int[] nums, boolean[] visited, int c, int[] queue) {
        if (c == 4) {
            Deque<Integer> stack = new LinkedList<>();
            stack.push(queue[0]);
            return cal(stack, 1, queue);
        }
        for (int i = 0; i < 4; i++) {
            if (!visited[i]) {
                visited[i] = true;
                queue[c] = nums[i];
                if (dfs(nums, visited, c + 1, queue)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }

    private static boolean cal(Deque<Integer> stack, int index, int[] queue) {
        if (index == 4) {
            if (stack.size() == 1) {
                return stack.peek() == 24;
            }
        }else {
            stack.push(queue[index]);
            if (cal(stack, index + 1, queue)) {
                return true;
            }
            stack.pop();
        }

        if (stack.size() < 2) {
            return false;
        }
        int behind = stack.pop();
        int pre = stack.pop();
        stack.push(pre + behind);
        if (cal(stack, index, queue)) {
            return true;
        }
        stack.pop();

        stack.push(pre - behind);
        if (cal(stack, index, queue)) {
            return true;
        }
        stack.pop();

        stack.push(pre * behind);
        if (cal(stack, index, queue)) {
            return true;
        }
        stack.pop();

        if (behind != 0 && pre % behind == 0) {
            stack.push(pre / behind);
            if (cal(stack, index, queue)) {
                return true;
            }
            stack.pop();
        }

        stack.push(pre);
        stack.push(behind);
        return false;
    }
}

发表于 2024-07-07 13:09:57 回复(1)
Java
a1vsa2头像 a1vsa2
贴段易懂的，效不效率另说
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        nums = new int[4];
        boolean[] visit = new boolean[4];
        for (int i = 0; i < 4; i++ ) {
            nums[i] = in.nextInt();
        }
        System.out.println(dfs(nums, visit));
    }
    static int[] nums;
    public static boolean dfs(int[] arr, boolean[] visit) {
        if (arr.length == 1) {
            return arr[0] == 24;
        }
        boolean rst = false;

        for (int i = 0; i < arr.length; i++) {
            if (visit[i])
                continue;
            visit[i] = true;
            for (int j = 0; j < arr.length; j++) {
                if (j != i && !visit[j]) {
                    visit[j] = true;

                    int[] na = new int[arr.length - 1];
                    for (int k = 1; k < arr.length - 1; k++) {
                        if (!visit[k]) {
                            na[k] = arr[k];
                        }
                    }
                    na[0] = arr[i] + arr[j];
                    rst = dfs(na, new boolean[na.length]);
                    if (!rst) {
                        na[0] = arr[i] - arr[j];
                        rst = dfs(na, new boolean[na.length]);
                    }
                    if (!rst) {
                        na[0] = arr[i] * arr[j];
                        rst = dfs(na, new boolean[na.length]);
                    }
                    if (!rst && arr[j] != 0 && arr[i] % arr[j] == 0) {
                        na[0] = arr[i] / arr[j];
                        rst = dfs(na, new boolean[na.length]);
                    }
                    if (rst) {
                        return rst;
                    }
                }
                visit[j] = false;
            }
            visit[i] = false;
        }
        return rst;
    }
}
发表于 2024-06-03 21:34:09 回复(0)
Java
//201910101754657头像 //201910101754657 
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String line = sc.nextLine();
            String[] arr = line.split(" ");
            int[] src = new int[arr.length];
            boolean[] pb = new boolean[src.length];
            for (int i = 0; i < arr.length; i++) {
                src[i] = Integer.parseInt(arr[i]);
                pb[i] = false;
            }
            System.out.println(dfs(src, pb, 0));
        }
    }

    private static boolean dfs(int[] src, boolean[] pb, double res) {
        if (res == 24) {
            return true;
        }
        List<Integer> remain = new ArrayList<>();
        for (int i = 0; i < src.length; i++) {
            if (!pb[i]) {
                remain.add(src[i]);
            }
        }
        for (int i = 0; i < src.length; i++) {
            if (!pb[i]) {
                int cur = src[i];
                pb[i] = true;
                if (res == 0) {
                    if (dfs(src, pb, cur)) {
                        return true;
                    }
                } else {
                    if (dfs(src, pb, res + cur)) {
                        return true;
                    }
                    if (dfs(src, pb, res - cur)) {
                        return true;
                    }
                    if (dfs(src, pb, res / cur)) {
                        return true;
                    }
                    if (dfs(src, pb, res * cur)) {
                        return true;
                    }
                }
                pb[i] = false;
            }
        }
        return false;
    }
}

编辑于 2024-03-17 03:44:36 回复(0)
Java
徐墨耀头像 徐墨耀
在题解区看到一位大佬提到测试用例{5,9,7,1}。我程序能通过题目内置的所有测试用例，却通不过前面这个例子。究其原因就是没有考虑到括号优先计算的问题，所以优化后则为： 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class T67 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] choices = {5, 9, 7, 1};
        choices[0] = sc.nextInt();
        choices[1] = sc.nextInt();
        choices[2] = sc.nextInt();
        choices[3] = sc.nextInt();
        tryAllCases(choices, new boolean[4], new ArrayList<>());
        System.out.println("false");
    }

    public static void tryAllCases(int[] choices, boolean[] selected, ArrayList<Double> res) {
        if (res.isEmpty()) {
            for (int i = 0; i < choices.length; i++) {
                selected[i] = true;
                res.add(choices[i] + 0.0);
                tryAllCases(choices, selected.clone(), res);
                selected[i] = false;
                res.clear();
            }
        } else {
            if (selected[0] && selected[1] && selected[2] && selected[3]) {
                if (res.contains(24.0)) {
                    System.out.println("true");
                    System.exit(0);
                }
            } else {
                for (int i = 0; i < selected.length; i++) {
                    //针对有括号存在的情况
                    {
                        if (res.size() == 1) {
                            boolean[] newSelected = new boolean[4];
                            Arrays.fill(newSelected, true);
                            ArrayList<Double> firstContainer = new ArrayList<>();
                            ArrayList<Double> secondContainer = new ArrayList<>();
                            calc(res.get(0), choices[i] + 0.0, firstContainer);
                            int a = -1;
                            int b = -1;
                            for (int i1 = 0; i1 < selected.length; i1++) {
                                if (i1 != i) {
                                    if (!selected[i1]) {
                                        if (a == -1) {
                                            a = i1;
                                        } else {
                                            b = i1;
                                        }
                                    }
                                }
                            }
                            calc(choices[a] + 0.0, choices[b] + 0.0, secondContainer);
                            ArrayList<Double> newRes = new ArrayList<>();
                            for (Double first : firstContainer) {
                                for (Double second : secondContainer) {
                                    calc(first, second, newRes);
                                }
                            }
                            tryAllCases(choices,newSelected,newRes);
                        }
                    }

                    //不考虑括号情况
                    if (!selected[i]) {
                        selected[i] = true;
                        ArrayList<Double> newRes = new ArrayList<>();
                        for (Double re : res) {
                            calc(re, choices[i] + 0.0, newRes);
                        }
                        tryAllCases(choices, selected.clone(), newRes);
                        selected[i] = false;
                    }
                }
            }
        }
    }

    public static void calc(Double a, Double b, ArrayList<Double> res) {
        res.add(a + b);
        res.add(a * b);
        if (a != 0.0) {
            res.add(b / a);
        }
        if (b != 0) {
            res.add(a / b);
        }
        res.add(a - b);
        res.add(b - a);
    }
}


编辑于 2023-12-22 00:08:15 回复(0)
Java
在敲键盘的孤勇者很苦闷头像 在敲键盘的孤勇者很苦闷
本文提供了 24 点游戏的解法，不只包括是否满足 24 点规则。
限首先官方给的案例是不全的，先上一段可以 100% 通过的 bug： 
        public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(
                                 Integer::parseInt).toArray();

        System.out.println(solve24(nums, 24, 15));
    }

        // selected:二进制去重，15 即为 1111
    public static boolean solve24(int[] nums, double target, int selected) {
        if (selected == 0) {
            return target == 0.00d;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (!checkI(i, selected)) {
                continue;
            }
            int newSelected = setI(i, selected);
            int select = nums[i];
            boolean result = false;
            result |= solve24(nums, target + select, newSelected);
            result |= solve24(nums, target - select, newSelected);
            result |= solve24(nums, target * select, newSelected);
            result |= solve24(nums, target / select, newSelected);
            if (result) {
                return true;
            }
        }
        return false;
    }

        // 校验 i 为是否为1
    public static boolean checkI(int i, int selected) {
        return ((selected >> i) & 1) == 1;
    }

        // 第 i 为置为0
    public static int setI(int i, int selected) {
        int c = ~(1 << i);
        return selected & c;
    }
上述代码的核心思想为：
既然数字可以组合得到24点，那么用 24 做逆向运算，如果最终结果为0，则表示满足 24 点规则。
而问题出在：
忽略了括号相关的组合情况，例如：1 9 1 2，显然应该是 （9-1）*(1+2),此方案不能解答，而官网给的用例却全部通过了（手动狗头～～）
具体解法可以参照 *********** 。
实不相瞒，代码写完就去玩 24 点游戏了，有的题解不出来，很是头疼，索性写了个解法： 
    private static final double TARGET=24;
    /**
     *
     * @param nums
     * @param formula   list 存储表达式子项，之所有选用 List<String> 是为了兼容数字大于9的情况
     * @param selected  记录选择标志位
     * @param nashorn
     * @return
     */
    public boolean dfs(int[] nums, List<String> formula, int selected, ScriptEngine nashorn) {
        if (selected == 0) {
            if (formula.size() < 7) {
                return false;
            }
            // todo test
//            System.out.println("complete formula: " + formula);
            String f = found24(formula, nashorn);
            boolean b = !f.isEmpty();
            if (b) {
                System.out.println(f);
            }
            return b;
        }
        boolean ret = false;
        for (int i = 0; i < nums.length; ++i) {
            int select = nums[i];
            int newSelect = setI(i, selected);
            if (selected == 15) {//1111
                formula.add(String.valueOf(select));
                if (!(ret |= dfs(nums, formula, newSelect, nashorn))) {
                    formula.remove(formula.size() - 1);
                    continue;
                }else{
                    return true;
                }
            }
            if (!checkI(i, selected)) {
                continue;
            }
            // addition
            formula.add("+");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // subtraction
            formula.add("-");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // multiplication
            formula.add("*");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // division
            formula.add("/");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 校验（从右到左）第 i 位是否为1
     * @param i
     * @param selected
     * @return
     */
    public boolean checkI(int i, int selected) {
        return ((selected >> i) & 1) == 1;
    }

    /**
     * 从右到左 第 i 位置为0
     * @param i
     * @param selected
     * @return
     */
    public int setI(int i, int selected) {
        int c = ~(1 << i);
        return selected & c;
    }

    /**
     * 枚举各种括号，找出带括号计算后可以得到 24 点的表达式
     * @param formula   包含表达式符号的集合
     * @param nashorn
     * @return          可得 24 点的表达式
     */
    public String found24(List<String> formula, ScriptEngine nashorn) {
        boolean ret = checkValue(calc(formula, nashorn) ,TARGET);
        if (ret) {
            return buildFormula(formula, null);
        }
        ArrayList<String> tempFormu = new ArrayList<>();
        // (AB)CD A(BC)D AB(CD)
        for (int i = 0; i < 3; ++i) {
            int end = 3 + i * 2;
            int start = end - 3;
            // 拼接表达式，一下类似，不重复注释
            tempFormu.addAll(formula.subList(0, start));
            tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn)) + ")");
            tempFormu.addAll(formula.subList(end, 7));

            ret = checkValue(calc(tempFormu,nashorn),TARGET);
            if (ret) {
                return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
            }
            tempFormu.clear();
        }
        // (AB)(CD)
        tempFormu.add("("+String.valueOf(calc(formula.subList(0, 3), nashorn)) + ")");
        tempFormu.addAll(formula.subList(3, 4));
        tempFormu.add("("+String.valueOf(calc(formula.subList(4, 7), nashorn))+")");
        ret = checkValue(calc(tempFormu,nashorn),TARGET);

        tempFormu.clear();
        if (ret) {
            return buildFormula(formula, Arrays.asList(Arrays.asList(0, 3), Arrays.asList(4, 7)));
        }
        // (ABC)D A(BCD)
        for (int i = 0; i < 2; ++i) {
            int end = 5 + i * 2;
            int start = end - 5;
            tempFormu.addAll(formula.subList(0, start));
            tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn))+")");
            tempFormu.addAll(formula.subList(end, 7));
            ret = checkValue(calc(tempFormu,nashorn),TARGET);
            tempFormu.clear();
            if (ret) {
                return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
            }
        }
        return "";
    }

    /**
     * 校验值 误差 < 1e-6
     * @param value
     * @param target
     * @return
     */
    public boolean checkValue(double value, double target){
        return Math.abs(target-value)<1e-6;
    }

    /**
     * 构建公式的字符串表达式（含有符号）
     * @param formulas
     * @param idxes     插入括号的下标（两层为了兼容双括号 (AB)(CD)）
     * @return
     */
    public String buildFormula(List<String> formulas, List<List<Integer>> idxes) {
        if (idxes == null) {
            return formulas.stream().collect(Collectors.joining());
        }
        StringBuilder formula = new StringBuilder();

        List<Integer> ids = idxes.get(0);
        if (idxes.size() == 1) {
            List<String> l1 = formulas.subList(0, ids.get(0));
            List<String> l2 = formulas.subList(ids.get(0), ids.get(1));
            List<String> l3 = formulas.subList(ids.get(1), 7);
            formula.append(l1.stream().collect(Collectors.joining()));
            formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
            formula.append(l3.stream().collect(Collectors.joining()));
        } else {//双括号只有一种可能
            List<String> l1 = formulas.subList(ids.get(0), ids.get(1));
            List<String> l2 = formulas.subList(idxes.get(1).get(0), idxes.get(1).get(1));
            formula.append("(" + l1.stream().collect(Collectors.joining()) + ")");
            formula.append(formulas.get(3));
            formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
        }
        return formula.toString();
    }

    public double calc(List<String> formula0, ScriptEngine nashorn) {
        try {
            String formula = formula0.stream().collect(Collectors.joining());
            // todo Test
//            System.out.println("calculating : " + formula);
            Object result = nashorn.eval(formula);
            if (result instanceof Integer) {
                return (Integer) result;
            }
            if (result instanceof Double) {
                double d = (Double) result;
                return d;
            }
            return 0;
        } catch (ScriptException e) {
            return 0;
        }
    }
靠着上述代码，总算通关了 24 游戏 160+32 个关卡，姑且一乐，需者自取


编辑于 2023-11-17 17:16:13 回复(1)
Java
GCID头像 GCID
任何简单多项式都可以转换为逆波兰表达式，而逆波兰表达式不含括号，则括号可以不考虑，以逆波兰表达式方法计算 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] x=new int[4];
        for(int i=0;i<4;i++){
            x[i]=in.nextInt();
        }
        char[] o=new char[3];
        if(DFS(x,o,0)){
            System.out.println("true");
            return;
        }
        System.out.println("false");
    }

    private static boolean DFS(int[] x,char[] o,int index){
        if(index==3){
            if(calculateReversePolish(x,o)==24){
                return true;
            }
            
        }
        if(index<3){
            for(int i=index;i<4;i++){
                swap(x,i,index);
                o[index]='+';
                if(DFS(x,o,index+1)){
                    return true;
                }
                o[index]='-';
                if(DFS(x,o,index+1)){
                    return true;
                }
                o[index]='*';
                if(DFS(x,o,index+1)){
                    return true;
                }
                o[index]='/';
                if(DFS(x,o,index+1)){
                    return true;
                }
                swap(x,i,index);
            }
        }
        return false;
    }
    private static void swap(int[] x,int i,int j){
        if(i==j){
            return;
        }
        int tmp=x[i];
        x[i]=x[j];
        x[j]=tmp;
    }

    private static int calculateReversePolish(int[] x,char[] o){

        return calculate(x[0],o[0],calculate(x[1],o[1],calculate(x[2],o[2],x[3])));
    }

    private static int calculate(int a,char o,int b){
        switch(o){
            case '+': return a+b;
            case '-': return a-b;
            case '*': return a*b;
            case '/': 
                if(b==0){
                    return 0;
                }
                return a/b;
        }
        return 0;
    }

}


发表于 2023-09-08 19:57:44 回复(0)
Java
牛客121720648号头像 牛客121720648号 
import java.util.Scanner;

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int[] numbers = new int[4];
        for (int i = 0; i < 4; i++)
            numbers[i] = in.nextInt();
        List<int[]> list = new LinkedList();
        for (int j = 0; j < numbers.length; j++)
            for (int k = 0; k < numbers.length; k++ )
                for (int m = 0; m < numbers.length; m++)
                    for (int n = 0; n < numbers.length; n++ ) {
                        if (j != k && j != m && j != n && k != m && k != n && m != n) {
                            list.add(new int[]{numbers[j], numbers[k], numbers[m], numbers[n]});
                        }
                    }
        for (int[] tempNums: list) {
            if (calculate(tempNums)){
                System.out.println(true);
                return;
            }
        }
        System.out.println(false);
    }
    public static boolean calculate(int[] numbers) {
        for (int i = 0; i < 4; i++ )
            for (int j = 0; j < 4; j++)
                for (int m = 0; m < 4; m++)
                    for (int n = 0; n < 3; n++) {
                        boolean resultMatch = false;
                        int[] factors = new int[]{i,j,m, n};
                        switch (factors[3]) {
                            case 0: resultMatch = calculateDetailCasenio1(factors, numbers); break;
                            case 1: resultMatch = calculateDetailCasenio2(factors, numbers); break;
                            case 2: resultMatch = calculateDetailCasenio3(factors, numbers);
                        }
                        if (resultMatch) {
                            return true;
                        }
                    }
        return false;

    }

    // casenio1, 顺序计算无括号情形，例  a * b * c - d, 不考虑算术符优先规定
    public static boolean calculateDetailCasenio1(int[] factors, int[] numbers) {
        int expiredResult = 24;
        int result = 0;
        switch(factors[0]) {
            case(0): result = numbers[0] + numbers[1]; break;
            case(1): result = numbers[0] - numbers[1]; break;
            case(2): {
                if (numbers[1] == 0 || numbers[0] % numbers[1] != 0)
                    return false;
                result = numbers[0] / numbers[1]; break;
            }
            case(3): result = numbers[0] * numbers[1];
        };
        switch(factors[1]) {
            case(0): result = result + numbers[2]; break;
            case(1): result = result - numbers[2]; break;
            case(2): {
                if (numbers[2] == 0 || result % numbers[2] != 0  )
                    return false;
                result = result / numbers[2]; break;
            }
            case(3): result = result * numbers[2];
        };
        switch(factors[2]) {
            case(0): result = result + numbers[3]; break;
            case(1): result = result - numbers[3]; break;
            case(2): {
                if ( numbers[3] == 0 || result % numbers[3] != 0)
                    return false;
                result = result / numbers[3]; break;
            }
            case(3): result = result * numbers[3];
        };
        return expiredResult == result;
    }

    // casino2， 括号包含三个数字，只有一种情形，例 a * (b - c * d) 括号内顺序计算不考虑算术优先
    public static boolean calculateDetailCasenio2(int[] factors, int[] numbers) {
        int expiredResult = 24;
        int result = 0;
        switch(factors[1]) {
            case(0): result = numbers[1] + numbers[2]; break;
            case(1): result = numbers[1] - numbers[2]; break;
            case(2): {
                if (numbers[2] == 0 || numbers[1]  % numbers[2] != 0)
                    return false;
                result = numbers[1]  / numbers[2]; break;
            }
            case(3): result = numbers[1]  * numbers[2];
        };
        switch(factors[2]) {
            case(0): result = result + numbers[3]; break;
            case(1): result = result - numbers[3]; break;
            case(2): {
                if (numbers[3] == 0 || result % numbers[3] != 0)
                    return false;
                result = result / numbers[3]; break;
            }
            case(3): result = result * numbers[3];
        };
        switch(factors[0]) {
            case(0): result = numbers[0] + result; break;
            case(1): result = numbers[0] - result; break;
            case(2): {
                if (result == 0 || numbers[0] % result != 0)
                    return false;
                result = numbers[0] / result; break;
            }
            case(3): result = numbers[0] * result;
        };
        return expiredResult == result;
    }
    // casino3, 共2个括号， 第一个括号 包含第1，2个数字， 第2个括号包括第3，4位数字，例（a - b） * (c + d)
    public static boolean calculateDetailCasenio3(int[] factors, int[] numbers) {
        int expiredResult = 24;
        int result = 0;
        int firstResult = 0;
        int secondResult = 0;
        switch(factors[0]) {
            case(0): firstResult = numbers[0] + numbers[1]; break;
            case(1): firstResult = numbers[0] - numbers[1]; break;
            case(2): {
                if (numbers[1] == 0 || numbers[0] % numbers[1] != 0)
                    return false;
                firstResult = numbers[0] / numbers[1]; break;
            }
            case(3): firstResult = numbers[0] * numbers[1];
        };
        switch(factors[2]) {
            case(0): secondResult = numbers[2] + numbers[3]; break;
            case(1): secondResult = numbers[2] - numbers[3]; break;
            case(2): {
                if (numbers[3] == 0 || numbers[2] % numbers[3] != 0)
                    return false;
                secondResult = numbers[2] / numbers[3]; break;
            }
            case(3): secondResult = numbers[2] * numbers[3];
        };
        switch(factors[1]) {
            case(0): result = firstResult + secondResult; break;
            case(1): result = firstResult - secondResult; break;
            case(2): {
                if (secondResult == 0 || firstResult % secondResult != 0)
                    return false;
                result = firstResult / secondResult; break;
            }
            case(3): result = firstResult * secondResult;
        };

        return expiredResult == result;
    }

}


发表于 2023-07-09 21:19:57 回复(0)
Java
9dragon头像 9dragon 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static boolean[] flag;
    static boolean res = false;
    private static void dfs(int[] nums, int idx, int sum) {
        if (idx == 4 && sum == 0) {
            res = true;
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (flag[i]) {
                continue;
            }
            flag[i] = true;
            dfs(nums, idx + 1, sum + nums[i]);
            dfs(nums, idx + 1, sum - nums[i]);
            dfs(nums, idx + 1, sum * nums[i]);
            if(sum % nums[i] == 0){
                dfs(nums, idx + 1, sum / nums[i]);
            }
            flag[i] = false;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = new int[4];
        for (int i = 0; i < 4; i++) {
            nums[i] = sc.nextInt();
        }
        flag = new boolean[4];
        dfs(nums, 0, 24);
        System.out.println(res);
    }
}

发表于 2023-04-26 09:35:43 回复(0)
Java
牛客401840707号头像 牛客401840707号
7 9 10  9 这个案例,(10 + 9) * 9 / 7 = 19 * 9 / 7 =  171 / 7 = 24,这种应该算对吧。为什么过不了。
发表于 2023-04-19 23:30:54 回复(2)
Java
夏小楠头像 夏小楠 
import java.util.*;
//该程序考虑了括号的情况，表现为计算结果加入计算序列，并参与轮询
public class Main {
    public static void main(String[] args) {
        LinkedList<Double> lib = new LinkedList<>();
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < 4; i++) {
            int num = in.nextInt();
            lib.add((double)num);
        }
        System.out.print(dfs(lib));
    }
    public static boolean dfs(LinkedList<Double> lib1) {
        LinkedList<Double> lib = new LinkedList<>(lib1);
        if (lib.size() == 1) {  //待计算序列减少至1
            if (Math.abs(lib.peek() - 24) < 1e-6) {
                return true;
            } else {
                return false;
            }
        }
        for (int i = 0; i < lib.size(); i++) {
            double num1 = lib.remove(i); //首先从计算序列取出第一个数
            for (int j = 0; j < lib.size(); j++) {
                double num2 = lib.remove(j);//再从剩余的计算序列取出第二个数
                //相加
                lib.addLast(num1 + num2);
                boolean add = dfs(lib);
                lib.removeLast();
                //相乘
                lib.addLast(num1 * num2);
                boolean sut = dfs(lib);
                lib.removeLast();
                //相减
                lib.addLast(num1 - num2);
                boolean sub = dfs(lib);
                lib.removeLast();
                //相除
                boolean divide = false;
                if (Math.abs(num2) > 1e-6) {
                    lib.addLast(num1 / num2);
                    divide = dfs(lib);
                    lib.removeLast();
                }
                //检查查找情况
                if(add || sut || sub || divide){
                    return true;//查找成功
                }else{
                    lib.add(j,num2);///从当前选择的第二个数未查找到
                }
            }
            lib.add(i,num1);//从当前选择的第一个数未查找到
        }
        return false;
    }
}
发表于 2023-04-19 18:02:17 回复(0)
Java
林深时er头像 林深时er
下面的代码是建立在题目没有明确要求所有的数字必须用上的前提下，但是无法解决a*b+c*d（其中a,b,c,d）各不相同的情况，这是是24不存在这种情况，但是换一个数字可能就不行了。因此此算法不算完美。 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String[] numStr = in.nextLine().split(" ");
            boolean flag = false;
            int[] nums = new int[4];
            for(int i=0;i<4;i++){
                nums[i] = Integer.parseInt(numStr[i]);
            }
            int[] visit = new int[4];
            for(int i=0;i<4;i++){
                visit[i] = 1;
                if(dfs(nums, visit, nums[i])){
                    flag = true;
                    break;
                }
            }
            System.out.println(flag);
        }
    }
    private static boolean dfs(int[]nums, int[] visit, int temp){
        for(int i=0;i<nums.length;i++){
            if(visit[i]==0){
                visit[i] = 1;
                if(dfs(nums, visit, temp+nums[i])
                ||dfs(nums, visit, temp-nums[i])
                ||dfs(nums, visit, temp*nums[i])
                ||(temp%nums[i]==0&&dfs(nums, visit, temp/nums[i]))){
                    return true;
                }
                visit[i] = 0;
            }
        }
        if(temp == 24) return true;
        return false;
    }
}
发表于 2023-04-15 16:19:15 回复(0)
Java
金丝虾球aa头像 金丝虾球aa 
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static boolean flag = false;
    private static ArrayList<ArrayList<Integer>> combinations = new ArrayList<>();
    private static ArrayList<Integer> tmp = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = new int[4];
        int[] operation = new int[]{0, 1, 2, 3};
        for(int i = 0; i < 4; i ++){
            nums[i] = in.nextInt();
        }

        // 获取所有数字的全排列， 考虑到数字可能有重复，所以用下标的全排列表示
        getAllCombinations(nums, 0);

        for(ArrayList<Integer> combination: combinations){
            int[] comb = new int[4];
            for(int i = 0; i < 4; i ++){
                comb[i] = nums[combination.get(i)];
            }
            
            // 递归计算所有结果
            digui(comb, operation, comb[0], 1);
        }

        System.out.println(flag);
    }

    public static void getAllCombinations(int[] nums, int index){
        if(tmp.size() == 4){
            combinations.add(new ArrayList<>(tmp));
            return;
        }

        for(int i = 0; i < 4; i ++){
            if(!tmp.contains(i)){
                tmp.add(i);
                getAllCombinations(nums, index + 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }

    // 注意 涉及到除法了！一定要用float，否则会有错误！
    public static void digui(int[] nums, int[] operation, float num, int index){
        if(index == nums.length){
            if(num == 24){
                flag = true;
                // System.out.println("遇到一个24");
            }
            return;
        }
        for(int i = 0; i < operation.length; i ++){
            if(i == 3 && nums[index] == 0) continue;
            digui(nums, operation, compute(num, nums[index], i), index + 1);
        }
    }

    public static float compute(float x, float y, int operation){
        if(operation < 0 || operation > 3) return -1;
        if(operation == 0){
            return x + y;
        }else if(operation == 1){
            return x - y;
        }else if(operation == 2){
            return x * y;
        }else{
            if (y == 0) return -1;
            return x / y;
        }
    }
}

发表于 2023-04-15 10:41:55 回复(0)
提交观点

问题信息

搜索 dfs
难度：
67条回答 40968浏览

热门推荐

通过挑战的用户

查看代码

相关试题

24点游戏算法

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号