24点游戏算法_

Java

//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

任何简单多项式都可以转换为逆波兰表达式，而逆波兰表达式不含括号，则括号可以不考虑，以逆波兰表达式方法计算

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号

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

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号

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

下面的代码是建立在题目没有明确要求所有的数字必须用上的前提下，但是无法解决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

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)

Java

不给offer不改名😡

import java.util.*;

public class Main {
    private static char[] ops = new char[]{'+', '-', '*', '/'};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        double[] num = new double[4];
        for(int i = 0; i < 4; i++)
            num[i] = in.nextDouble();
        ArrayList<ArrayList<Double>> list = new ArrayList<>();
        recursion(list, num, 0);
        for(int i = 0; i < list.size(); i++){
            ArrayList<Double> innerList = list.get(i);
            for(int j = 0; j < 4; j++){
                for(int k = 0; k < 4; k++){
                    for(int p = 0; p < 4; p++){
                        double first = operation(innerList.get(0), innerList.get(1), ops[j]);
                        double second = operation(first, innerList.get(2), ops[k]);
                        if(operation(second, innerList.get(3), ops[p]) == 24){
                            System.out.println(true);
                            return;
                        }
                    }
                }
            }
        }
        System.out.println(false);
    }

    public static double operation(double a, double b, char op){
        switch(op){
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                return a / b;
        }
        return 0;    
    }


    public static void recursion(ArrayList<ArrayList<Double>> list, double[] num, int index){
        if(index == num.length){
            ArrayList<Double> innerList = new ArrayList<>();
            for(double i : num)
                innerList.add(i);
            list.add(innerList);
            return;
        }else{
            for(int i = index; i < num.length; i++){
                swap(num, index, i);
                recursion(list, num, index + 1);
                // 回溯
                swap(num, index, i);
            }
        }
    }

    public static void swap(double[] num, int a, int b){
        double temp = num[a];
        num[a] = num[b];
        num[b] = temp;
    }
}

发表于 2023-04-09 01:23:14 回复(0)

Java

你干嘛哟

// 从数组里面任意挑两个数出来运算，直到最后只剩下一个数

private static boolean solve( int[] nums, char[] opts) {

int size = nums.length;

if (size == 1) {

if (nums[0] == 24) return true;

else return false;

}

int[] visited = new int[size];

int contains = size;

for (int i = 0; i < size; i++) {

visited[i] = 1;

int num1 = nums[i];

contains--;

for (int j = i + 1; j < size; j ++) {

visited[j] = 1;

int num2 = nums[j];

contains--;

for (int k = 0; k < 4; k++) {

char c = opts[k];

int result = 0;

if (c == '/' && num2 == 0) continue;

if (c == '+') result = num1 + num2;

if (c == '-') result = num1 - num2;

if (c == '*') result = num1 * num2;

if (c == '/') result = num1 / num2;

int[] newArr = new int[contains + 1];

int l = 0;

for (int h = 0; h < size; h++) {

if (visited[h] == 0) {

newArr[l] = nums[h];

l++;

}

newArr[l] = result;

if (solve(newArr, opts)) return true;

}

visited[j] = 0;

contains++;

}

visited[i] = 0;

contains++;

}

return false;

}

发表于 2023-03-15 13:00:46 回复(0)

Java

我是小白eiki

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        double[] num = new double[4];
        for (int i = 0; i < 4; i++) {
            num[i] = in.nextDouble();
        }

        if (game(num)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }

    //算24方法
    static boolean game(double[] num) {
        for (int i = 0; i < 4; i++) {
            //最终参与运算的括号左边括号可能值的集合
            Set<Double> set1 = new HashSet<>();
            //最终参与运算的右边括号可能值的集合
            Set<Double> set2 = new HashSet<>();
            //临时存放可能值的set
            Set<Double> tmpList = new HashSet<>();

            for (int j = i; j < 4; j++) {
                if (i == j) {
                    continue;
                } else {
                    double num1 = num[i];
                    double num2 = num[j];
                    //存放还没取到的两位数
                    List<Double> num3 = new ArrayList();

                    tmpList = possilbleTwoNum(num1, num2);
                    set1 = tmpList;
                    for (int k = 0; k < 4; k++) {
                        if (k != i && k != j) {
                            tmpList = possibleSetWithNum(tmpList, num[k]);
                            num3.add(num[k]);
                        }
                    }
                    set2 = possilbleTwoNum(num3.get(0), num3.get(1));
                    set2 = possibleTwoSet(set1, set2);
                    //1.每个数依次计算的情况
                    if (isTrue(tmpList)) {
                        return true;
                    }
                    //2.四个数分为两个括号来计算的情况
                    if (isTrue(set2)) {
                        return true;
                    }
                }
            }

        }
        return false;
    }

    //验证24
    static boolean isTrue(Set<Double> list) {
        for (Double d : list) {
            if (24 == d) {
                return true;
            }
        }
        return false;
    }

    //两个数加减乘除可能得到的数值集合
    static Set<Double> possilbleTwoNum(double m1, double m2) {
        Set<Double> possilbleTwoNum = new HashSet<>();
        possilbleTwoNum.add(m1 + m2);
        possilbleTwoNum.add(Math.abs(m1 - m2));
        possilbleTwoNum.add(m1 * m2);
        possilbleTwoNum.add(m1 / m2);
        possilbleTwoNum.add(m2 / m1);
        return possilbleTwoNum;
    }

    //一个数值集合的所有数字 和 m2 加减乘除可能得到的数值集合
    static Set<Double> possibleSetWithNum(Set<Double> list, double m2) {
        Set<Double> two = new HashSet();
        for (double d : list) {
            two.add(d + m2);
            two.add(Math.abs(d - m2));
            two.add(d / m2);
            two.add(m2 / d);
            two.add(m2 * d);

        }
        return two;
    }


    //一个数值集合的所有数字 和 一个数值集合所有数字 加减乘除可能得到的数值集合
    static Set<Double> possibleTwoSet(Set<Double> s1, Set<Double> s2) {
        Set<Double> possibleList = new HashSet();
        List<Double> list1 = new ArrayList();
        List<Double> list2 = new ArrayList();

        Iterator<Double> s1It = s1.iterator();
        Iterator<Double> s2It = s2.iterator();
        while (s1It.hasNext()) {
            list1.add(s1It.next());
        }

        while (s2It.hasNext()) {
            list2.add(s2It.next());
        }

        for (int i = 0; i < list1.size(); i++) {
            Set<Double> tmp = new HashSet<Double>();
            for (int j = 0; j < list2.size(); j++) {
                tmp = possilbleTwoNum(list1.get(i), list2.get(j));
                for (Double d : tmp) {
                    possibleList.add(d);
                }
            }

        }
        return possibleList;
    }
}

发表于 2023-03-06 18:01:25 回复(0)

24点游戏算法

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题